2014西安站
- F - Color
- I - International Collegiate Routing Contest
F - Color
题目链接：http://codeforces.com/gym/100548/attachments
题意：给 N N 个位置填颜色，且相邻的位置不能填同样的颜色，有
我也不是很懂怎么容斥的T_T，大概就是说：
选出的这
换句话说就是：可能填 K K 种，可能填
而我们要的就是可能填
i i 种颜色不选的公式为：
然后就是后面容斥的时候，会频繁地用到 CiK C K i 因此用递推式先预处理一哈，最后再乘一哈是在 M M 种颜色中选的哪
//#include"bits/stdc++.h"
#include"cstdio"
#include"iostream"
using namespace std;
const int maxn=1e6+5;
typedef long long LL;
const LL MOD=1e9+7;
LL N,M,K;
LL fac[maxn]= {1,1},inv[maxn]= {1,1},invf[maxn]= {1,1};
LL Ck[maxn]= {1};
LL ksm(LL a,LL b,LL mod)
{LL res=1,base=a;while(b){if(b&1)res=(res*base)%mod;base=(base*base)%mod;b>>=1;}return res;
}
void Init(int n)
{for(int i=2; i<=n; i++){fac[i]=fac[i-1]*i%MOD;inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;}invf[n]=ksm(fac[n],MOD-2,MOD);for(int i=n-1; i>=2; i--)invf[i]=invf[i+1]*(i+1)%MOD;
}
LL C(LL n,LL m)
{m=min(m,n-m);LL res=1;for(LL i=n; i>n-m; i--)res=(res*i)%MOD;res=(res*invf[m])%MOD;return res;
}int main()
{Init(maxn-5);int T;cin>>T;for(int Case=1; Case<=T; Case++){scanf("%I64d%I64d%I64d",&N,&M,&K);cout<<"Case #"<": ";for(LL i=1; i<=K; i++)Ck[i]=Ck[i-1]*(K-i+1)%MOD*inv[i]%MOD;//预处理C(K,i) LL ans=0;for(LL i=0;i*(K-i)%MOD*ksm(K-1-i,N-1,MOD);if(i&1)ans-=tp;else ans+=tp;ans%=MOD;}ans=(C(M,K)*ans%MOD+MOD)%MOD;cout< I - International Collegiate Routing Contest
题目链接：http://codeforces.com/gym/100548/attachments
参考这位童鞋的博客：https://blog.csdn.net/u013849646/article/details/52238850
题意：说一哈样例是啥意思，比如第二个 0.0.0.0/1 0.0.0.0 / 1 ，前面四个数就是表示子网掩码啥的，反正就是个 0 0 ~
比如要是斜杠后面的是 0 0 说明前
第二个样例就是固定了前
然后这题的思路就是把每个地址都转换成 2 2 进制然后放进字典树里面，这道题要是给我说了字典树我也很无语，因为那后面随便变的我不知道怎么处理，而这题很机智的就是在固定不动的最后一位那里打个标记，相当于说是个单词结尾，而查找的时候，遇到打标记的地方就停了，哇我感觉这个很机智
然后代码最关键的地方就是查找答案的时候，查找函数是有返回值的，返回值为
这个地址映射的值感觉有点不好怎，本来想从高位到低位正常的这样赋值的，但是不好继承上一次的value
#include"bits/stdc++.h"
using namespace std;
const int maxn=1e6+5;
typedef long long LL;
int ch[maxn<<5][2],vis[maxn<<5];
vectorint > >Ans;
int tot;
void Insert(LL v,int lim)
{int u=0;for(int i=31;i>=32-lim;i--){int c=1&(v>>i);if(ch[u][c]==-1){ch[u][c]=++tot;vis[tot]=0;}u=ch[u][c];}vis[u]=1;//表示一个单词的末尾
}
int query(int u,LL v,int lim)//lim表示走到了第几层，也是表示前lim位是固定的
{if(u==-1)return 0;//没有儿子了，说明这条路走到头了 if(vis[u])return vis[u];//如果找到个单词的末尾，那么他后面的都是阔以覆盖的，说明肯定有路，就直接返回1了 if(lim==32)return vis[u];int p1=query(ch[u][0],v<<1,lim+1);int p2=query(ch[u][1],v<<1|1,lim+1);if(p1&&p2==0)//如果右边没有路，那么右边就是一个答案 {Ans.push_back(make_pair(v<<1|1,lim+1)); }else if(p1==0&&p2){Ans.push_back(make_pair(v<<1,lim+1));}return p1|p2;//两条路中有一条就行，就说明说阔以往下继续走的
}
void print(LL v,int lim)
{v<<=32-lim;int t1=(v>>24);int t2=(v>>16)^(t1<<8);int t3=(v>>8)^(t1<<16)^(t2<<8);int t4=v^(t1<<24)^(t2<<16)^(t3<<8);cout<"."<"."<"."<"/"<int main()
{int T;cin>>T;for(int Case=1;Case<=T;Case++) {tot=0;Ans.clear();memset(ch,-1,sizeof ch);memset(vis,0,sizeof vis);int N;cin>>N;for(int i=1;i<=N;i++){LL t1,t2,t3,t4;int lim;scanf("%lld.%lld.%lld.%lld/%d",&t1,&t2,&t3,&t4,&lim);LL v=(t1<<24)+(t2<<16)+(t3<<8)+t4;Insert(v,lim);}cout<<"Case #"<":"<if(N==0){cout<<1<cout<<"0.0.0.0/0"<continue;}query(0,0,0);cout<for(int i=0;i 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！