本题乍看像是线段树之类的区间操作，只是由于仅仅是须要查找ip的前缀，故此事实上是使用Trie来做。
挺高难度的Trie应用，做完这道题之后说明Trie功力有一定火候了。
这里的Trie使用到了Delete函数。这是个Trie函数中最难的函数了，当然要使用数组记录的方法水掉。也是能够的。这里不水。给出delete函数。
考点难点：
1 Trie的操作函数的灵活运用。主要难点是delete函数的灵活运用
2 在叶子节点全部的group id， 删除的时候要注意，不能一气删除了，有多个group id会挂在同一颗树中
3 源ip和目的ip或许在多个叶子节点中，要使用两个vector记录全部group id，然后使用查找两集合是否有公共值的算法解之
4 ip值转换为一个整数值记录就能够了，这里使用了unsigned，只是应该是int也能够的，由于仅仅须要操作其二进制值，和整数值无关。
5 使用mask值，mask值后面的0能够无论，加速程序
全部问题考虑全。高级数据结构中包含各种小问题处理，大算法中使用到多种小算法，综合难度超过5星级。做完后非常有成就感O(∩_∩)O哈哈~。
#include#include #include #include using namespace std;const int MAX_ID = 1024;const int MAX_LINE = 32769;const int MAX_N = 15;const int ARR_SIZE = 2;const int MAX_DIGIT = 32;const int MAX_NODE = MAX_ID*MAX_DIGIT*MAX_N;unsigned gEnableIdIpMask[MAX_ID][MAX_N<<1];int gLen[MAX_ID], id;struct Node{ int n; vector id; Node *arr[ARR_SIZE];};void clearNode(Node *rt){ rt->n = 0; rt->id.clear(); for (int i = 0; i < ARR_SIZE; i++) { rt->arr[i] = NULL; }}Node pool[MAX_NODE];int poolID;void insertTrie(Node *trie, unsigned dig, unsigned mark, int id){ bitset bi = dig; int m = MAX_DIGIT - mark; for (int i = MAX_DIGIT-1; i >= m; i--) { Node *&p = trie->arr[bi[i]];//注意*&p,操作同名地址变量 if (!p)//推断成if(p)。程序崩溃。 { p = &pool[poolID++]; clearNode(p); } trie = p; } trie->n++; trie->id.push_back(id);}bool searchNode(Node *trie, unsigned dig, vector &id){ bitset bi = dig; bool flag = false; for (int i = MAX_DIGIT-1; i >= 0; i--) { trie = trie->arr[bi[i]]; if (!trie) return flag; if (trie->n) { flag = true; id.insert(id.end(), trie->id.begin(), trie->id.end()); } } return flag;}inline bool isFreeNode(Node *rt){ for (int i = 0; i < ARR_SIZE; i++) { if (rt->arr[i]) return false; } return true;}bool deleteNodeHelper(Node *trie, bitset &bi, int mask, int id, int lv = MAX_DIGIT-1)//注意lv含义。准确赋值{ if (trie) { if (mask-1 == lv)//注意：下标计算。对齐 { if (trie->n) { if (trie->n > 1) { int j = 0; for (; j < trie->n; j++) if (trie->id[j] == id) break; trie->id.erase(trie->id.begin()+j); trie->n--; } else { trie->n = 0; trie->id.clear(); return isFreeNode(trie); } } } else { if (deleteNodeHelper(trie->arr[bi[lv]], bi, mask, id, lv-1)) { trie->arr[bi[lv]] = NULL; return !trie->n && isFreeNode(trie); } } } return false;}inline void deleteNode(Node *trie, unsigned dig, unsigned mask, int id){ bitset bi = dig; int m = MAX_DIGIT - mask; //注意长度计算 deleteNodeHelper(trie, bi, m, id);}unsigned getIP(){ unsigned ip = 0; unsigned part; for (int j = 3; j >= 0; j--) { scanf("%u", &part); getchar(); ip |= part<<(j<<3); } return ip;}int main(){ char cmd; unsigned ip, mask; Node *trie = &pool[0]; clearNode(trie); poolID = 1; while (scanf("%c", &cmd) != EOF) { if (cmd == 'E') { scanf("%d", &id); scanf("%d", gLen+id); for (int i = 0; i < gLen[id]; i++) { ip = getIP(); scanf("%u", &mask); gEnableIdIpMask[id][i<<1] = ip; gEnableIdIpMask[id][i<<1|1] = mask; insertTrie(trie, ip, mask, id); } getchar(); } else if (cmd == 'D') { scanf("%d", &id); getchar(); for (int i = 0; i < gLen[id]; i++) { deleteNode(trie, gEnableIdIpMask[id][i<<1], gEnableIdIpMask[id][i<<1|1], id); } gLen[id] = 0; } else// if (cmd == 'F') { ip = getIP(); vector ipSrc, ipDes; bool src = searchNode(trie, ip, ipSrc); ip = getIP(); if (src) src = searchNode(trie, ip, ipDes); if (src) { sort(ipSrc.begin(), ipSrc.end()); sort(ipDes.begin(), ipDes.end()); bool hasSame = false; for (int i = 0, j = 0; i < (int)ipSrc.size() && j < (int)ipDes.size(); ) { if (ipSrc[i] == ipDes[j]) { hasSame = true; break; } else if (ipSrc[i] < ipDes[j]) i++; else j++; } if (hasSame) puts("F"); else puts("D"); } else puts("D"); } } return 0;}