感觉这套比赛题目比较容易，没有以前做过的某次codechef那么凶残。题目还是很有意思的，最好的是有中文翻译。
CSUB：签到题，直接从左往右扫一遍即可，维护前面出现过多少个1.
#include <cstdio> #include <cstring> #define maxn 100100 using namespace std; char s[maxn]; long long ans; int cur,T,n; int main() { scanf("%d",&T); while (T--) { scanf("%d%s",&n,s); ans=cur=0; for (int i=0; s[i]; i++) if (s[i]=='1') ans+=++cur; printf("%lld ",ans); } return 0; }
RETPO：简单找规律。注意一开始的朝向，同时根据对称性，所有的点都可以对称到第一象限来。要走弯路的话，第一个单位距离消耗3步，第二个单位距离消耗1步，第三个消耗3步，第四个1步，依次类推即可。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; long long x,y,n,ans; int T; int main() { scanf("%d",&T); while (T--) { scanf("%lld%lld",&x,&y); if (x<0) x=-x; if (y<0) y=-y; n=y-x; if (n>=0 && n<=1) ans=x+y; else { if (n<0) n=-n; if (y>x) ans=2*min(x,y)+(n/2)*4+(n&1)*1; else ans=2*min(x,y)+(n/2)*4+(n&1)*3; } printf("%lld ",ans); } return 0; }
FROGV：氺题。对于每只青蛙，f[i]保存它向右最远可以传递到那一只青蛙，假设当前我们计算第i只青蛙，对于j>i，且i可以传递信息给j，那么f[i]=max(f[j])。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 100100 using namespace std; int g[maxn],f[maxn]; int n,m,k,x,y; struct node{ int x,id; }a[maxn]; bool cmp(node n1,node n2) { return n1.x<n2.x; } int main() { scanf("%d%d%d",&n,&k,&m); for (int i=1; i<=n; i++) scanf("%d",&a[i].x),a[i].id=i; sort(a+1,a+1+n,cmp); for (int i=1; i<=n; i++) g[a[i].id]=i; f[n]=n; for (int i=n-1; i>0; i--) if (a[i+1].x-a[i].x<=k) f[i]=f[i+1]; else f[i]=i; while (m--) { scanf("%d%d",&x,&y); x=g[x],y=g[y]; if (x>y) swap(x,y); if (y<=f[x]) puts("Yes"); else puts("No"); } return 0; }
SGARDEN：数学题。对于一种置换，它里面一定构成了若干个环。所有人都回到原地的步数就是所有环长度的lcm值。由于这个lcm值很大，必须对于每个环长度进行因数分解，保存每个质数出现的次数就可。最后取模计算。
#include <iostream> #include <cstdio> #include <cstring> #include <map> #define maxn 100100 typedef long long ll; using namespace std; const int M=1000000007; int a[maxn],T,n,cur,N; bool b[maxn]; ll ans; map<int,int> ss; void dfs(int x) { if (b[x]) return; cur++,b[x]=true; dfs(a[x]); } void deal(int x) { for (int i=2; i*i<=x; i++) { if (x%i) continue; N=0; while (x%i==0) x/=i,N++; ss[i]=max(ss[i],N); } if (x>1) ss[x]=max(ss[x],1); } int main() { scanf("%d",&T); while (T--) { ss.clear(); ans=1; scanf("%d",&n); for (int i=1; i<=n; i++) scanf("%d",&a[i]),b[i]=false; for (int i=1; i<=n; i++) if (!b[i]) { cur=0; dfs(i); deal(cur); } for (int i=2; i<=n; i++) while (ss[i]--) ans=(ans*i)%M; printf("%lld ",ans); } return 0; }
DISHOWN：一看这个题目就是一个典型的并查集了。每次查找盘子的主人，然后两个主人之间的比较无非就是改变一下指针而已了，路径压缩，所有的操作都是O(1)的。
#include <iostream> #include <cstdio> #include <cstring> #define maxn 10010 using namespace std; int a[maxn],f[maxn]; int n,q,T; int father(int x) { return f[x]==x?f[x]:f[x]=father(f[x]); } int main() { int ope,x,y; scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i=1; i<=n; i++) scanf("%d",&a[i]),f[i]=i; scanf("%d",&q); while (q--) { scanf("%d",&ope); if (ope==0) { scanf("%d%d",&x,&y); x=father(x),y=father(y); if (a[x]==a[y]) { if (x==y) puts("Invalid query!"); continue; } if (a[x]>a[y]) f[y]=x; else f[x]=y; } else { scanf("%d",&x); printf("%d ",father(x)); } } } return 0; }
LEPAINT：这个题目我一开始以为我会T。没想到写了一发最最暴力的居然都A掉了。不过我觉得这个应该是被卡掉的，只是数据不够强吧。优化可以是这样的，对于物品，直接预处理它染色多少次后，为某种颜色的概率。同时，后面的区间染色就用扫描区间的方法，直接得出，直接求和即可。对于题目所说的取子集的问题，就相当于在这个范围里面每一个物品都有0.5的概率被染色。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; double f[55][111],tmp[111],ans; int L,R,n,m,c,T; int main() { scanf("%d",&T); while (T--)//10 { scanf("%d%d%d",&n,&c,&m); for (int i=1; i<=n; i++) { for (int j=0; j<c; j++) f[i][j]=0; f[i][1]=1; } while (m--)//50 { scanf("%d%d",&L,&R); for (int i=L; i<=R; i++)//50 { for (int j=0; j<c; j++) f[i][j]/=2,tmp[j]=f[i][j]; for (int j=0; j<c; j++)//100 for (int k=0; k<c; k++)//100 f[i][j*k%c]+=tmp[j]/c; } } ans=0; for (int i=1; i<=n; i++) for (int j=0; j<c; j++) ans+=f[i][j]*j; printf("%.9f ",ans); } return 0; }
GNUM：很好的一个题目。一开始我就看准了这个题目，花时间最多的一个题目。读完题目后直接想到的就是二分图取匹配。显然是T。可以建模来解。以a[i]<b[j]且满足gcd条件的点位左边点，连接源点，以a[i]>b[j]且满足gcd条件的点为右点，连接汇点。中间是gcd出现过的质数，分别连接相应的左右点，所有的边流量都是1，跑最大流即可。这个做法肯定是没有错的。但是还是有一些问题存在。点太多了。咋解决？缩点，分别把左右边的点中含有相同的质因子种类的点缩成一个点，边容量累加。再跑最大流，缩点后，点数的级别也就1000吧，可以ac。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <map> #define maxn 2002000 #define maxpri 100100 using namespace std; int pri[maxpri],pnum=0,antipri[maxpri]; int z[1888][30],Z[1888],a[1888],aa[1888]; int to[maxn],c[maxn],next[maxn],first[maxn],edge,node; int tag[maxn],d[maxn],Q[maxn],bot,top,TAG=520; int f[566666][30],Tf; bool can[maxn]; int T,n,tmp,s,t,ans,cas; map<int,int> ss,pos,Ttime;//质�对������ int gcd(int A,int B) { return B==0?A:gcd(B,A%B); } void getprim() { for (int i=2; i<maxpri; i++) { if (antipri[i]==-1) continue; pri[++pnum]=i; antipri[i]=pnum; for (int j=i+i; j<maxpri; j+=i) antipri[j]=-1; } } int addnode() { node++; first[node]=-1; return node; } void _init() { ss.clear(),pos.clear(),Ttime.clear(); edge=-1,node=0,Tf=0; s=addnode(),t=addnode(); ans=0; } void addedge(int U,int V,int W) { edge++; to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge; edge++; to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge; } void deal(int x) { Z[x]=0,tmp=a[x],aa[x]=tmp; for (int i=1; pri[i]<=tmp/pri[i]; i++) if (tmp%pri[i]==0) { z[x][++Z[x]]=pri[i]; while (tmp%pri[i]==0) tmp/=pri[i]; } if (tmp>1) z[x][++Z[x]]=tmp; for (int i=1; i<=Z[x]; i++) while (((aa[x]/z[x][i])%z[x][i])==0) aa[x]/=z[x][i]; } void buildedge() { for (int x=1; x<=n; x++) for (int y=n+1; y<=n+n; y++) if (a[x]<a[y] && gcd(aa[x],aa[y])>1) { int cur=gcd(aa[x],aa[y]); if (pos[cur]) { Ttime[cur]=Ttime[cur]+1; continue; } pos[cur]=++Tf,f[Tf][0]=0,Ttime[cur]=1; for (int i=1; i<=Z[x]; i++) if (aa[y]%z[x][i]==0) f[Tf][++f[Tf][0]]=z[x][i]; f[Tf][f[Tf][0]+1]=cur; } for (int i=1; i<=Tf; i++) { int cur=f[i][f[i][0]+1],tc=Ttime[cur],Nd=addnode();//Nd为��gcd代表��� addedge(s,Nd,tc); for (int j=1; j<=f[i][0]; j++) { if (ss[f[i][j]]==0) ss[f[i][j]]=addnode(); addedge(Nd,ss[f[i][j]],tc); } } pos.clear(),Tf=0; for (int x=1; x<=n; x++) for (int y=n+1; y<=n+n; y++) if (a[x]>a[y] && gcd(aa[x],aa[y])>1) { int cur=gcd(aa[x],aa[y]); if (pos[cur]) { Ttime[cur]=Ttime[cur]+1; continue; } pos[cur]=++Tf,f[Tf][0]=0,Ttime[cur]=1; for (int i=1; i<=Z[x]; i++) if (aa[y]%z[x][i]==0) f[Tf][++f[Tf][0]]=z[x][i]; f[Tf][f[Tf][0]+1]=cur; } for (int i=1; i<=Tf; i++) { int cur=f[i][f[i][0]+1],tc=Ttime[cur],Nd=addnode();//Nd为��gcd代表��� addedge(Nd,t,tc); for (int j=1; j<=f[i][0]; j++) { if (ss[f[i][j]]==0) continue; addedge(ss[f[i][j]],Nd,tc); } } } bool bfs() { TAG++; Q[bot=top=1]=t,d[t]=0,tag[t]=TAG,can[t]=false; while (bot<=top) { int cur=Q[bot++]; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i^1]>0 && tag[to[i]]!=TAG) { tag[to[i]]=TAG,Q[++top]=to[i],d[to[i]]=d[cur]+1,can[to[i]]=false; if (to[i]==s) return true; } } return false; } int dfs(int cur,int num) { if (cur==t) return num; int tmp=num,k; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i]>0 && d[to[i]]==d[cur]-1 && tag[to[i]]==TAG && can[to[i]]==false) { k=dfs(to[i],min(num,c[i])); if (k) num-=k,c[i]-=k,c[i^1]+=k; //if (num==0) return tmp; } if (num) can[cur]=true; return tmp-num; } int main() { getprim(); scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i=1; i<=2*n; i++) scanf("%d",&a[i]),deal(i); _init(); buildedge(); while (bfs()) ans+=dfs(s,maxn); printf("%d ",ans); } return 0; }
SEAEQ：为什么这是整场比赛通过人数最少的题目？我觉得在平时比赛这种难度的题目也就算中等吧？此题让我想去去年杭州赛的那个题。深坑呐。解法是这样的，dp预处理长度为i的排列有不超过j个逆序数对的情况有多少种！这个可以dp好好想想就知道了，剩下的就是逆推枚举了，直接枚举区间长度，位置，对于两个排列其他的位置都是全排列即可。对于题目的那个要求就是在规定区间内，每个位置的相对大小相同即可，这个只需要保证对于预处理的种类数乘一次，对于取组合数和全排列数乘以两次即可。不难理解，自己想想就很清楚了。一开始取模打成了1000000009，都怪前几天打的那场acdream，坑死啦。
#include <iostream> #include <cstdio> #include <cstring> #define maxn 502 typedef long long ll; using namespace std; const int M=1000000007; int n,e,T,ans; int sum[maxn][(maxn*maxn-maxn)/2];//�度����对� ll P[maxn],C[maxn][maxn]; int main() { P[0]=1,C[0][0]=1; for (int i=1; i<maxn; i++) P[i]=(P[i-1]*i)%M; for (int i=1; i<maxn; i++) { C[i][0]=1; for (int j=1; j<=i; j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%M; } int last=0,next; sum[1][0]=1; for (int i=2; i<maxn; i++) { next=last+i-1; sum[i][0]=1; for (int j=1; j<i; j++) { sum[i][j]=sum[i][j-1]+sum[i-1][j]; if (sum[i][j]>=M) sum[i][j]-=M; } for (int j=i; j<=last; j++) { sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-i]; if (sum[i][j]>=M) sum[i][j]-=M; if (sum[i][j]<0) sum[i][j]+=M; } for (int j=last+1; j<=next; j++) { sum[i][j]=sum[i][j-1]+sum[i-1][last]-sum[i-1][j-i]; if (sum[i][j]>=M) sum[i][j]-=M; if (sum[i][j]<0) sum[i][j]+=M; } last=next; } scanf("%d",&T); while (T--) { scanf("%d%d",&n,&e); ans=0; for (int i=1; i<=n; i++) { int cur=min((i*i-i)/2,e); cur=sum[i][cur]; ll tmp=(C[n][i]*P[n-i])%M; tmp=((tmp*tmp)%M*cur)%M; ans+=(tmp*(n+1-i))%M; if (ans>=M) ans-=M; } printf("%d ",ans); } return 0; }