1.花
（flower.cpp/c/pas）
【问题描述】
商店里出售n种不同品种的花。为了装饰桌面，你打算买m支花回家。你觉得放两支一样的花很难看，因此每种品种的花最多买1支。求总共有几种不同的买花的方案？答案可能很大，输出答案mod p的值。
【输入格式】
一行3个整数n，m，p，意义如题所述。
【输出格式】
一个整数，表示买花的方案数。
【输入输出样例1】
|
flower.in |
flower.out |
|
4 2 5 |
1 |
见选手目录下的flower / flower1.in与flower / flower1.out
【输入输出样例1说明】
用数字1,2,3,4来表示花的种类的话，4种花里买各不相同的2支的方案有(1,2)、(1,3)、(1,4)、(2,3)、(2,4)、(3,4)，共6种方案，模5后余数是1。
【输入输出样例2】
见选手目录下的flower / flower2.in与flower / flower2.out
【数据范围】
对于30%的数据，n,m≤10
对于50%的数据，n,m≤1000
对于80%的数据，1≤m≤n≤50,000
对于100%的数据，1≤m≤n≤1,000,000，p≤1,000,000,000
暴力
/* 求组合数取膜 因为有÷ 显然直接摸是搞不定的 开始用扩展欧几里得写了逆元 后来发现不互质的时候无解 这样求不出逆元.... 然后想用欧拉定理 情况差不多 而且吧 边乘边%会导致答案错误 在这里发现了问题的关键.... 好吧我是蒟蒻写到这才发现.. 举个栗子 比如 C(8,7) (8*7*6*5*4*3*2)/(1*2*3*4*5*6*7)%7 本来7 7可以约掉 但是%一下就成0了... 换思路 直接暴力质因数分解吧 先筛下素数 然后分解的时候加个特盘什么的 能卡过去 最后两个点都0.8s */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000010 #define ll long long using namespace std; int n,m,p,a[maxn],x,y,ans=1,prime[maxn],num,P[maxn]; bool f[maxn]; void gcd(ll a,ll b){ if(b==0){x=1;y=0;return;} gcd(b,a%b);ll tmp=x;x=y;y=tmp-a/b*y; } void Get(){ for(int i=2;i<=1000000;i++){ if(f[i]==0)prime[++num]=i,P[i]=num; for(int j=1;j<=num;j++){ if(i*prime[j]>1000000)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } } } ll qm(ll a,ll b,ll c){ ll r=1; while(b){ if(b&1)r*=a,r%=c; b>>=1;a*=a;a%=c; } return r; } void Insert1(ll x){ for(int i=1;i<=num;i++){ if(x%prime[i]==0){ ll cnt=0; while(x%prime[i]==0)x/=prime[i],cnt++; a[i]+=cnt; } if(x==1)break; if(f[x]==0){ a[P[x]]++;break; } } } void Insert2(ll x){ for(int i=1;i<=num;i++){ if(x%prime[i]==0){ int cnt=0; while(x%prime[i]==0)x/=prime[i],cnt++; a[i]-=cnt; } if(x==1)break; if(f[x]==0){ a[P[x]]--;break; } } } int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); cin>>n>>m>>p;Get(); for(int i=2;i<=n;i++)Insert1(i); for(int i=2;i<=m;i++)Insert2(i); for(int i=2;i<=n-m;i++)Insert2(i); for(int i=1;i<=num;i++){ if(a[i]>0)ans=ans*qm(prime[i],a[i],p)%p; if(a[i]<0){ gcd(qm(prime[i],-a[i],p),p); ans=ans*x%p; } } cout<<ans<<endl; return 0; }
XXX（数学公式）
/* 然后身边学过数竞的孩子说求阶乘里有几个素数有别的方法 n!里p的个数=n/p+n/p*p+n/p*p*p.....知道p==n 知道这个就快了嘛 嗖嗖的..... */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000010 #define ll long long using namespace std; ll n,m,p,a[maxn],x,y,ans=1,prime[maxn],num,P[maxn]; bool f[maxn]; void Get(){ for(int i=2;i<=1000000;i++){ if(f[i]==0)prime[++num]=i,P[i]=num; for(int j=1;j<=num;j++){ if(i*prime[j]>1000000)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } } } ll qm(ll a,ll b,ll c){ ll r=1; while(b){ if(b&1)r*=a,r%=c; b>>=1;a*=a;a%=c; } return r; } int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); cin>>n>>m>>p;Get(); for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=n){ a[i]+=n/P; P*=prime[i]; } } for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=m){ a[i]-=m/P; P*=prime[i]; } } for(int i=1;i<=num;i++){ ll P=prime[i]; while(P<=n-m){ a[i]-=(n-m)/P; P*=prime[i]; } } for(int i=1;i<=num;i++) ans=ans*qm(prime[i],a[i],p)%p; cout<<ans<<endl; return 0; }
2.圆桌游戏
（game.cpp/c/pas）
【问题描述】
有一种圆桌游戏是这样进行的：n个人围着圆桌坐成一圈，按顺时针顺序依次标号为1号至n号。对1<i<n的i来说，i号的左边是i+1号，右边是i-1号。1号的右边是n号，n号的左边是1号。每一轮游戏时，主持人指定一个还坐在桌边的人（假设是i号），让他向坐在他左边的人（假设是j号）发起挑战，如果挑战成功，那么j离开圆桌，如果挑战失败，那么i离开圆桌。当圆桌边只剩下一个人时，这个人就是最终的胜利者。
事实上，胜利者的归属是与主持人的选择息息相关的。现在，你来担任圆桌游戏的主持人，并且你已经事先知道了对于任意两个人i号和j号，如果i向j发起挑战，结果是成功还是失败。现在你想知道，如果你可以随意指定每轮发起挑战的人，哪些人可以成为最终的胜利者？
【输入】
第一行包含一个整数n，表示参加游戏的人数；
接下来n行，每行包含n个数，每个数都是0或1中的一个，若第i行第j个数是1，表示i向j发起挑战的结果是成功，否则表示挑战结果是失败。第i行第i列的值一定为0。
【输出】
一行，包含若干个数，表示可能成为最终胜利者的玩家的标号。标号按从小到大的顺序输出，相邻两个数间用1个空格隔开。
【输入输出样例1】
|
game.in |
game.out |
|
3 0 1 0 0 0 1 0 1 0 |
1 3 |
见选手目录下的game / game1.in与game / game1.out
【输入输出样例1说明】
先指定2号向3号发起挑战，3号离开；再指定1号向2号发起挑战，2号离开。此时1号是最终胜利者。
先指定1号向2号发起挑战，2号离开；再指定1号向3号发起挑战，1号离开。此时3号是最终胜利者。
无论如何安排挑战顺序，2号都无法成为最终胜利者。
【输入输出样例2】
见选手目录下的game / game2.in与game / game2.out
【数据规模与约定】
对于30%的数据，n≤7
对于100%的数据，n≤100
暴力
/*暴力30*/ #include<iostream> #include<cstdio> #include<cstring> #define maxn 110 using namespace std; int n,g[maxn][maxn],f[maxn]; bool Can[maxn]; void Dfs(int now){ if(now==n){ for(int i=1;i<=n;i++) if(f[i]==0)Can[i]=1; } for(int i=1;i<=n;i++) if(f[i]==0){ int x=i+1; if(x==n+1)x=1; while(f[x]==1){ x++; if(x==n+1)x=1; } if(g[i][x]==1){ f[x]=1;Dfs(now+1);f[x]=0; } else{ f[i]=1;Dfs(now+1);f[i]=0; } } } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&g[i][j]); Dfs(1); for(int i=1;i<=n;i++) if(Can[i]==1)printf("%d ",i); return 0; }
正解dp
/* 正解dp吧 很巧妙地思路 关键是转化成比较好操作的题目 先把环拆成链 定义状态f[i][j] 表示i到j能不能都死掉 最后答案就是f[i][i+n]==1的 初始化 f[i][i+1]=1 然后区间dp 小区间到大区间 并且判断谁杀了谁 */ #include<cstdio> #define maxn 210 using namespace std; int n,g[maxn][maxn],f[maxn][maxn],c[maxn]; int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&g[i][j]); for(int i=1;i<=n;i++) c[i]=c[i+n]=i; for(int i=1;i<=n*2;i++) f[i][i+1]=1; for(int i=2*n;i>=1;i--) for(int j=i+1;j<=n*2;j++) for(int k=i;k<=j;k++) if(f[i][k]&&f[k][j]&&(g[c[i]][c[k]]||!g[c[k]][c[j]])){ f[i][j]=1;break; } for(int i=1;i<=n;i++) if(f[i][i+n])printf("%d ",i); return 0; }
3.兔子
（rabbit.cpp/c/pas）
【问题描述】
在一片草原上有N个兔子窝，每个窝里住着一只兔子，有M条路径连接这些窝。更特殊地是，至多只有一个兔子窝有3条或更多的路径与它相连，其它的兔子窝只有1条或2条路径与其相连。换句话讲，这些兔子窝之前的路径构成一张N个点、M条边的无向连通图，而度数大于2的点至多有1个。
兔子们决定把其中K个兔子窝扩建成临时避难所。当危险来临时，每只兔子均会同时前往距离它最近的避难所躲避，路程中花费的时间在数值上等于经过的路径条数。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造避难所的方式，使最后一只到达避难所的兔子所花费的时间尽量少。
【输入】
第一行有3个整数N，M，K，分别表示兔子窝的个数、路径数、计划建造的避难所数。
接下来M行每行三个整数x,y，表示第x个兔子窝和第y个兔子窝之间有一条路径相连。任意两个兔子窝之间至多只有1条路径。
【输出】
一个整数，表示最后一只到达避难所的兔子花费的最短时间。
【输入输出样例1】
|
rabbit.in |
rabbit.out |
|
5 5 2 1 2 2 3 1 4 1 5 4 5 |
1 |
见选手目录下的rabbit / rabbit1.in与rabbit / rabbit1.out
【输入输出样例1说明】
在第2个和第5个兔子窝建造避难所，这样其它兔子窝的兔子最多只需要经过1条路径就可以到达某个避难所。
【输入输出样例2】
见选手目录下的rabbit / rabbit2.in与rabbit / rabbit2.out
【数据规模与约定】
对于30%的数据，N≤15，K≤4；
对于60%的数据，N≤100；
对于100%的数据，1≤K≤N≤1,000，1≤M≤1,500
暴力
/*暴力30*/ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1010 using namespace std; int n,m,k,f[maxn][maxn],c[maxn],ans=0x7fffffff; bool vis[maxn]; void Solve(){ int r=0; for(int i=1;i<=n;i++){ int mx=0x3f3f3f3f; for(int j=1;j<=c[0];j++) mx=min(mx,f[i][c[j]]); r=max(r,mx); } ans=min(ans,r); } void Dfs(int now){ if(now==k+1){ Solve(); return; } for(int i=1;i<=n;i++) if(vis[i]==0){ vis[i]=1;c[++c[0]]=i; Dfs(now+1); c[0]--;vis[i]=0; } } void Floyed(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } int main() { freopen("rabbit.in","r",stdin); freopen("rabbit.out","w",stdout); scanf("%d%d%d",&n,&m,&k); int u,v; memset(f,127/3,sizeof(f)); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); f[u][v]=f[v][u]=1; } for(int i=1;i<=n;i++)f[i][i]=0; Floyed();Dfs(1); printf("%d ",ans); return 0; }
正解二分
/* 正解二分（好吧很容易想到） 只不过Judge的时候不好想 而且怎么用上那个度>=3的点不超过1个呢 不妨把这个点看成中心的点 上下的出去的要么是链 要么是连回来的环 嗯这就好办了 先预处理所有连出去的的长度以及是不是环 然后二分答案 算出最少搞几个窝 judge的时候注意 中心不一定选 所以我们枚举第一个选的在哪条路上 在枚举位置 这么这条路来说 如果是链 除去头上的枚举的s 以及最后的t 中间p[i].len-s-t要覆盖 而且每个区间长度是 2*t+1 再加上开始选的那个 如果是环 上面的情况在-(t-s)这是连回来的 靠近中心的那部分点 他们可以从中心到达最开始枚举的那个窝 剩下的那些类似的处理 长度是+s 而不是-s了 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 1510 using namespace std; int n,m,k,num,head[maxn],r[maxn],cnt,root,f[maxn],ans; struct node{ int len,cir; }p[maxn]; struct edge{ int v,pre; }e[maxn*2]; void Add(int from,int to){ num++;e[num].v=to; e[num].pre=head[from]; head[from]=num; } void Dfs(int now,int from){ p[cnt].len++; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(v==from)continue; if(f[v]==0){ f[v]=1;Dfs(v,now); } else if(v==root)p[cnt].cir=1; } } int Cal(int len,int t){ if(len<=0)return 0; return (len-1)/(2*t+1)+1; } bool Judge(int t){ int mx=0x3f3f3f3f; for(int i=1;i<=cnt;i++){ for(int s=0;s<=t&&s<=p[i].len;s++){ int tot=0; if(p[i].cir==0)tot=Cal(p[i].len-s-t,t); else tot=Cal(p[i].len-s-t-(t-s),t); tot++; for(int j=1;j<=cnt;j++){ if(i==j)continue; if(p[j].cir==0)tot+=Cal(p[j].len+s-t,t); else tot+=Cal(p[j].len+s-t-(t-s),t); } mx=min(mx,tot); } } return mx<=k; } int main() { freopen("rabbit.in","r",stdin); freopen("rabbit.out","w",stdout); scanf("%d%d%d",&n,&m,&k); int u,v;root=1; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); Add(u,v);Add(v,u); r[u]++;r[v]++; if(r[u]>=3)root=u; if(r[v]>=3)root=v; } f[root]=1; for(int i=head[root];i;i=e[i].pre){ int v=e[i].v; if(f[v]==0){ f[v]=1;cnt++; Dfs(v,root); } } int l=0,r=0x3f3f3f3f; while(l<=r){ int mid=(l+r)/2; if(Judge(mid)){ r=mid-1;ans=mid; } else l=mid+1; } printf("%d ",ans); return 0; } /* 5 5 1 1 2 2 4 2 3 3 5 4 5 */