微软2016校园招聘4月在线笔试 B. 403 Forbidden 题解
最后编辑于: 2016-04-09初步解
顺序查找已经建立的规则，能够通过低级测试用例，对于规模较大的测试用例会出现超时。
#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include"stdlib.h"
void split(std::string& s, std::string delim,std::vector< std::string >* ret)
{
size_t last = 0;
size_t index = s.find_first_of(delim, last);
while (index != std::string::npos) {
ret->push_back(s.substr(last, index-last));
last = index + 1;
index=s.find_first_of(delim, last);
}
if (index-last > 0) {
ret->push_back(s.substr(last, index - last));
}
}
int main(void)
{
int N, M;
std::cin >> N >> M;
std::vector<std::string> rules;
std::vector<bool> rule_ctx;
while(N--)
{
std::string rule;
std::cin >> rule;
std::string rule_text;
std::cin >> rule_text;
std::string bin_addr("");
if(rule_text.find('/') == std::string::npos)
{
std::vector<std::string> rule_info;
split(rule_text, ".", &rule_info);
for(size_t i = 0; i < rule_info.size(); ++i)
{
bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string( );
}
}
else
{
std::vector<std::string> rule_meta_info;
split(rule_text, "/", &rule_meta_info);
std::vector<std::string> rule_info;
split(rule_meta_info[0], ".", &rule_info);
for(size_t i = 0; i < rule_info.size(); ++i)
{
bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string( );
}
bin_addr = bin_addr.substr(0, atoi(rule_meta_info[1].c_str()));
}
rules.push_back(bin_addr);
if(rule[0]=='a')
{
rule_ctx.push_back(true);
}
else
{
rule_ctx.push_back(false);
}
}
while(M--)
{
bool is_match = false;
std::string bin_addr("");
std::string req;
std::cin >> req;
std::vector<std::string> rule_info;
split(req, ".", &rule_info);
for(size_t i = 0; i < rule_info.size(); ++i)
{
bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
}
for(size_t i = 0; i < rules.size(); ++i)
{
int len = rules[i].size();
if (bin_addr.substr(0, len) == rules[i])
{
is_match = true;
if(rule_ctx[i] == true)
std::cout << "YES" << std::endl;
else
std::cout << "NO" << std::endl;
break;
}
}
if(!is_match)
std::cout << "YES" << std::endl;
}
return 0;
}
优化解
既然顺序查找会超时，考虑使用树结构来进行查找。类似于字典树，编码为二进制形式的ip地址使用二叉树形式，左儿子为0，右儿子为1。
#include<iostream>
#include<climits>
#include<string>
#include<vector>
#include<bitset>
#include"stdlib.h"
typedef struct TreeNode *Node;
struct TreeNode
{
int flag;
Node Left;
Node Right;
};
Node createNode(int flag)
{
Node T = new TreeNode;
T->Left = T->Right = NULL;
T->flag = flag;
return T;
}
void split(std::string& s, std::string delim,std::vector< std::string >* ret)
{
size_t last = 0;
size_t index = s.find_first_of(delim, last);
while (index != std::string::npos) {
ret->push_back(s.substr(last, index-last));
last = index + 1;
index=s.find_first_of(delim, last);
}
if (index-last > 0) {
ret->push_back(s.substr(last, index - last));
}
}
int main(void)
{
int N, M;
std::cin >> N >> M;
Node rule_header = createNode(-1);
std::vector<bool> rule_ctx;
size_t rule_cnt = 0;
bool default_rule = true;
while(N--)
{
std::string rule;
std::cin >> rule;
std::string rule_text;
std::cin >> rule_text;
std::string bin_addr("");
int mask = 0;
if(rule_text.find('/') == std::string::npos)
{
std::vector<std::string> rule_info;
split(rule_text, ".", &rule_info);
for(size_t i = 0; i < rule_info.size(); ++i)
{
bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
}
}
else
{
std::vector<std::string> rule_meta_info;
split(rule_text, "/", &rule_meta_info);
std::vector<std::string> rule_info;
split(rule_meta_info[0], ".", &rule_info);
for(size_t i = 0; i < rule_info.size(); ++i)
{
bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
}
bin_addr = bin_addr.substr(0, atoi(rule_meta_info[1].c_str()));
if(atoi(rule_meta_info[1].c_str()) == 0)
default_rule = false;
else
mask = atoi(rule_meta_info[1].c_str());
}
Node rule_node = rule_header;
int level_cnt = 0;
for(size_t i = 0; i < bin_addr.size(); ++i)
{
if(bin_addr[i] == '0')
{
if(rule_node->Left == NULL)
{
rule_node->Left = createNode(-1);
}
rule_node = rule_node->Left;
}
else
{
if(rule_node->Right == NULL)
{
rule_node->Right = createNode(-1);
}
rule_node = rule_node->Right;
}
if((mask > 0) && (++level_cnt == mask))
break;
}
if(rule_node->flag == -1)
rule_node->flag = rule_cnt;
if(rule[0]=='a')
{
rule_ctx.push_back(true);
}
else
{
rule_ctx.push_back(false);
}
rule_cnt++;
}
while(M--)
{
size_t first_match = INT_MAX;
std::string bin_addr("");
std::string req;
std::cin >> req;
std::vector<std::string> rule_info;
split(req, ".", &rule_info);
for(size_t i = 0; i < rule_info.size(); ++i)
{
bin_addr += std::bitset<8>(atoi(rule_info[i].c_str())).to_string();
}
Node search = rule_header;
for(size_t i = 0; i < bin_addr.size(); ++i)
{
if (bin_addr[i] == '0')
{
if (search->Left == NULL)
break;
if (search->Left->flag != -1)
first_match = search->Left->flag < first_match ? search->Left->flag:first_match;
search = search->Left;
}
else
{
if (search->Right == NULL)
break;
if (search->Right->flag != -1)
first_match = search->Right->flag < first_match ? search->Right->flag:first_match;
search = search->Right;
}
}
if(first_match == INT_MAX)
std::cout << (default_rule ? "YES":"NO") << std::endl;
else
std::cout << (rule_ctx[first_match] ? "YES":"NO") << std::endl;
}
return 0;
}