微软2016实习生笔试--第二题403 Forbidden

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;struct Rule           // 存放规则的结构体
{bool allow;unsigned int ip;int mask;Rule() : allow(false), ip(0), mask(32){}
};unsigned int getIp()   // 获得输入的IP地址
{unsigned int a, b, c, d;char dot;cin >> a >> dot >> b >> dot >> c >> dot >> d;return (a << 24) | (b << 16) | (c << 8) | d;
}bool solve(vector<Rule> &rules, unsigned int ip)   // 判断IP地址满足的规则
{for(auto rule : rules){if(rule.mask == 0 || (ip ^ rule.ip) >> (32-rule.mask) == 0)return rule.allow;}return true;
}int main()
{int N, M;while(cin >> N >> M){char cmd[20];char t;vector<Rule> rules(N);for(int i = 0; i < N; i++){cin >> cmd;rules[i].allow = strcmp(cmd, "allow") == 0;rules[i].ip = getIp();cin.get(t);if(t == '/')cin >> rules[i].mask;elsecin.putback(t);}bool* result = new bool[M];for(int j = 0; j < M; j++){unsigned int ip = getIp();result[j] = solve(rules, ip);}for(int i = 0; i < M; i++)cout << (result[i] ? "Yes" : "No" )<<endl;delete[] result;}return 0;
}

前缀匹配问题，可以用前缀树来解决。因此，可以利用前缀树来确定哪些规则可以适用于一个IP。

Trie Approach

于是有了下面的想法：

1. 规则集利用前缀树描述
2. 前缀树每个结点记录，到本结点是否为一个规则，规则要求的动作是什么，规则的序号。
3. 对于一个IP，遍历前缀树，找到所适用规则中序号最小的，返回该规则的要求，若没有适用规则，返回允许。
4. 一个IPv4的地址大小为32bit，也就是可以在常量时间找到适用规则。

至此，剩下的问题就是如果建立前缀树，由于题意要求，最早匹配原则，树的建立可以这样做：

1. 若插入新规则i时，该规则的前缀路径上已有规则j, 则规则j的序号一定比i小，也即，规则i被j屏蔽，直接丢弃i即可。
2. 注意第一条中，当规则i和j等长时，也适用。

#include <iostream>
#include <cstring>using namespace std;class Trie     // 建立规则集的前缀树
{
private:struct TrieNode   // 前缀树节点{int order;   // 定义规则的序号TrieNode* children[2];   // 连接下一前缀树节点TrieNode() : order(0){children[0] = children[1] = NULL;}};TrieNode *root;
public:Trie() : root(new TrieNode()){}void addRule(unsigned int ip, int mask, int order)  // 添加规则{TrieNode* pos = root;for(int i = 1; i <= mask; i++){if(pos->order)    // 当前缀路径上已有规则时，直接返回，丢弃当前要插入的规则return;int bit = (ip >> (32-i)) & 1;if(!(pos->children[bit])){TrieNode* newNode = new TrieNode();pos->children[bit] = newNode;}pos = pos->children[bit];}if(!(pos->order))pos->order = order;}int query(unsigned int ip)   // 查询ip满足的规则{TrieNode *pos = root;int order = 1;for(int i = 1; i <= 32; i++){if(pos->order)order = pos->order;int bit = (ip >> (32-i)) & 1;if(!(pos->children[bit]))break;pos = pos->children[bit];}return order;}
};inline unsigned int getIp()  // 得到输入的IP
{unsigned int a, b, c, d;char dot;cin >> a >> dot >> b >> dot >> c >> dot >> d;return (a << 24) | (b << 16) | (c << 8) | d;
}int main()
{int N, M;Trie rule;while(cin >> N >> M){char cmd[20];char t;for(int i = 1; i <= N; i++){int mask = 32;cin >> cmd;unsigned int ip = getIp();cin.get(t);if(t == '/')cin >> mask;elsecin.putback(t);int order = i;if(strcmp(cmd, "allow"))order *= -1;rule.addRule(ip, mask, order);}int *result = new int[M];for(int j = 0; j < M; j++){unsigned int ip = getIp();result[j] = rule.query(ip);}for(int i = 0; i < M; i++)cout << (result[i] > 0 ? "Yes" : "No") <<endl;delete[] result;}return 0;
}