首页 > 代码库 > 10.8 noip模拟试题
10.8 noip模拟试题
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 longusing 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 longusing 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 110using 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 210using 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 1010using 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\n",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 1510using 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\n",ans); return 0;}/*5 5 11 22 42 33 54 5*/
10.8 noip模拟试题