成都网站建设推广投放广告的渠道有哪些

题目链接：点击打开链接

题意描述：现有一个网络中，在不同的子网之间建立转发策略，有相同的转发策略的子网之间可以互相通信

给出以下三种操作：

操作一：E  可以理解为建立标号为id的转发策略，有n个子网，这n个子网之间有相同的转发策略id

操作二：D 取消id这种转发策略

操作三、询问ipsrc与ipdst是否有相同的转发策略（当然一个ip地址可能有多种转发策略）

问题，对于每次询问，如果有相同的转发策略则输出F，否则输出D

解题思路：Trie树

1、一个子网内的IP地址有相同的前缀，其余部分可以任意，所以我们可以根据前缀确定某个ip地址位于哪个子网中（注意：一个ip地址可能位于几个子网中，大子网包含小子网）；

2、根据子网前缀建立Trie树，对于Trie中的每个节点对应一个vector保存以当前节点结束的子网有哪些。

3、用vis标记id这种转发策略是否存在

4、mark标记ipsrc位于的转发策略，便于与ipdst对比判断

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=33005;
typedef long long ll;
struct Trie{int _next[maxn][2],ct;bool vis[1055];int mark[1055];int Q;vector<int> val[maxn];void init(){ct=0;Q=1;memset(_next,0,sizeof(_next));memset(vis,false,sizeof(vis));memset(mark,-1,sizeof(mark));memset(val,0,sizeof(val));}void insert(ll ip,int len,int id){int rt=0;for(int i=31;i>=32-len;i--){int k=(ip>>i)&1;if(!_next[rt][k])_next[rt][k]=++ct;rt=_next[rt][k];}val[rt].push_back(id);}void color(ll ip){int rt=0;for(int i=31;i>=0;i--){int k=(ip>>i)&1;if(!_next[rt][k]) return;rt=_next[rt][k];int len=val[rt].size();for(int j=0;j<len;j++){if(vis[val[rt][j]])mark[val[rt][j]]=Q;}}}bool judge(ll ip){int rt=0;for(int i=31;i>=0;i--){int k=(ip>>i)&1;if(!_next[rt][k]) return false;rt=_next[rt][k];int len=val[rt].size();for(int j=0;j<len;j++)if(mark[val[rt][j]]==Q)return true;}return false;}
};
ll getIp(int a,int b,int c,int d){ll ret=0;ret |= (ll)a<<24;ret |= (ll)b<<16;ret |= (ll)c<<8;ret |= d;return ret;
}
int a,b,c,d,e,id;
char op[3];
int main(){Trie tr;tr.init();while(scanf("%s",op)!=EOF){if(op[0]=='E'){int num;scanf("%d%d",&id,&num);while(num--){scanf("%d.%d.%d.%d/%d",&a,&b,&c,&d,&e);tr.insert(getIp(a,b,c,d),e,id);}tr.vis[id]=1;}else if(op[0]=='F'){tr.Q++;scanf("%d.%d.%d.%d",&a,&b,&c,&d);tr.color(getIp(a,b,c,d));scanf("%d.%d.%d.%d",&a,&b,&c,&d);puts(tr.judge(getIp(a,b,c,d))?"F":"D");}else if(op[0]=='D'){scanf("%d",&id);tr.vis[id]=0;}}return 0;
}