cf训练赛
A.题目大意：给出n个数，问能否选出若干个数，使得这些数的和为m的倍数。（n<=10^6，m<=10^3）
思路：用f[i][j]表示前i个数是否能选出若干个和模m为j的数，直接DP，当f[i][0]为true时直接返回，虽然看上去是O(nm)，但我们可以发现，当n超过m时答案必为真，证明如下：每次加入一个数x，若x不能被前i-1个数表示，我们令f[i][x]=true；若x能被前i-1个数表示，则2x能被前i个数表示，以此类推，每次加入x，至少会有一个原来为false的被设为了true，否则说明我们找到了m的倍数。总复杂度O(m^2)。
#include<cstdio> inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 1000 int u[2][MN+5]; int main() { int n,m,x,i; n=read();m=read(); while(n--) { u[n&1][x=read()%m]=1; for(i=0;i<m;++i)if(u[n&1^1][i])u[n&1][i]=u[n&1][(i+x)%m]=1; if(u[n&1][0])return 0*puts("YES"); } puts("NO"); }
B.题目大意：给出一个1~n的置换，要求构造一棵n个点的树，使得树上每条边两端点编号置换后得到的边仍然出现在树中。（n<=10^5）
思路：先把置换拆成若干个循环，如果有长度为1的循环，那么其他所有点连到这个点即可，否则只有所有循环长度均为偶数且存在长度为2的循环才可以构造，选出一个长度为2的循环，其他所有点根据在循环中位置的奇偶分别连向这个循环的两个点，最后把这两个点自己连起来即可。
#include<cstdio> #include<algorithm> #include<vector> using namespace std; inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 100000 int a[MN+5],u[MN+5],cnt; vector<int> v[MN+5]; int main() { int n=read(),i,j,s,s1=0,s2=0,o=0; for(i=1;i<=n;++i)a[i]=read(); for(i=1;i<=n;++i)if(!u[i]) { for(++cnt,j=i;!u[j];u[j]=1,j=a[j])v[cnt].push_back(j); s=v[cnt].size(); if(s==1)s1=cnt; if(s==2)s2=cnt; o|=s&1; } if(!s1&&(o||!s2))return 0*puts("NO"); puts("YES"); for(i=1;i<=cnt;++i) if(s1)for(j=0;j<v[i].size();++j){if(i!=s1)printf("%d %d ",v[i][j],v[s1][0]);} else if(i!=s2)for(j=0;j<v[i].size();++j)printf("%d %d ",v[i][j],v[s2][j&1]); if(!s1)printf("%d %d ",v[s2][0],v[s2][1]); }
C.题目大意：你有n张图片，你一开始翻到第1张，每次从第i张切换到第i-1或第i+1张需要a的时间（1可以切换到n，n可以切换到1），每张图片的朝向可能不太对，如果碰见朝向不对的，你需要花b时间转过来，每次你碰见第一次看到的图片，你会花1时间看它，问在t时间内最多看多少张图片。（n<=500,000）
思路：只会有两种情况，一种先往左边翻，然后再翻到右边，另一种先翻到右边再翻到左边，若只考虑先翻右的（另一种同理），可以预处理出从第1张翻到左边每一张时的花费，从左往右枚举右端点，显然左端点也递增，拿两个指针直接统计即可，总复杂度O(n)。
#include<cstdio> #include<algorithm> using namespace std; #define MN 500000 char g[MN+5]; int n,a,b,t,ans,f[MN+5]; void solve() { int i,j,s; for(i=n;i--;)f[i]=f[i+1]+a+b*(g[i]=='w')+1; for(i=j=s=0;i<n;++i,s+=a) { s+=b*(g[i]=='w')+1; if(s>t)break; ans=max(ans,i+1); if(s+i*a<=t) { while(j<=i||s+f[j]+i*a>t)++j; ans=max(ans,i+1+n-j); } } } int main() { scanf("%d%d%d%d%s",&n,&a,&b,&t,g); solve(); for(int i=1;i<n-i;++i)swap(g[i],g[n-i]); solve(); printf("%d",ans); }
D.题目大意：一个1~n的排列一开始为1,2,3,…,n，支持两种操作：1.循环右移k位；2.交换当前第1个和第2个，第3个和第4个……保证n为偶数。（n<=1,000,000，操作数<=2,000,000）
思路：把排列编号为0~n-1，两种操作分别表示为x=(x+k)mod n，x=x xor 1，显然如果奇偶性相同，偏移量也相同，两种情况都算一下即可，复杂度O(n)。
#include<cstdio> inline int read() { int x,f=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')f=0; for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return f?x:-x; } #define MN 1000000 int ans[MN+5]; int main() { int n=read(),i,t,x,s0=0,s1=1; for(i=read();i--;) { t=read(); if(t==1)x=read(),s0=(s0+x)%n,s1=(s1+x)%n; else s0^=1,s1^=1; } for(i=1;i<=n;++i)ans[(i+(i&1?s0:s1-1)+n)%n]=i; for(i=1;i<=n;++i)printf("%d ",ans[i%n]); }
E.题目大意：给出n个数ci和一个数k，问是否对于任意的x，若确定所有x%ci，则可确定x%k。（n,k,ci<=1,000,000）
思路：显然要确定x%k的条件为k|lcm(ci)，筛法预处理后把ci和k分解质因数，对每个质因子统计一下即可。
#include<cstdio> #include<algorithm> using namespace std; inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 1000000 int f[MN+5],p[MN+5],pn,s[MN+5]; int main() { int n,k,i,j,cnt; for(i=2;i<=MN;++i) { if(!f[i])f[i]=i,p[++pn]=i; for(j=1;i*p[j]<=MN;++j){f[i*p[j]]=p[j];if(i%p[j]==0)break;} } n=read();k=read(); while(n--)for(i=read();i>1;) { for(j=f[i],cnt=0;f[i]==j;i/=j)++cnt; s[j]=max(s[j],cnt); } while(k>1) { for(j=f[k],cnt=0;f[k]==j;k/=j)++cnt; if(s[j]<cnt)return 0*puts("No"); } puts("Yes"); }