首页 > 代码库 > Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
运气好，分到的房里我最先开始Hack C题，Hack了12个，听说F题沙雕莫队但我不会，最后剩不到15分钟想出E题做法打了一波结果挂了，最后虽然上分了但总有点不甘心。
A.Neverending competitions
题目大意：某人从家里飞出去再飞回来再飞出去再飞回来……，现在给你N张他用过的机票（N<=100），保证合法但顺序打乱了，问他现在家还是在外面。
思路：n%2问题……没看清题目保证在外地必然飞回家，写了判断出入度。
#include<cstdio> inline int read() { int x=0;char c; while((c=getchar())<‘0‘||c>‘9‘); for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=(x<<3)+(x<<1)+c-‘0‘; return x; } int main() { int n=read(),x,a=0;char s[10]; scanf("%s",s);x=(s[0]*1000+s[1])*1000+s[2]; while(n--) { scanf("%s",s); if((s[0]*1000+s[1])*1000+s[2]==x)++a; if((s[5]*1000+s[6])*1000+s[7]==x)--a; } puts(a?"contest":"home"); }
B.Code obfuscation
题目大意：一篇文章，碰见第一个没碰过单词就把所有这个单词替换成a，第二个就替换成b，给一个长度不超过500的小写字母串，问是否可能是某篇文章加密得到的。
思路：拿个变量存用到哪个字母了呗……手速题
#include<cstdio> inline int read() { int x=0;char c; while((c=getchar())<‘0‘||c>‘9‘); for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=(x<<3)+(x<<1)+c-‘0‘; return x; } #define MN 500 char s[MN+5]; int main() { int i,x=‘a‘; scanf("%s",s); for(i=0;s[i];++i) { if(s[i]>x)return 0*puts("NO"); if(s[i]==x)++x; } puts("YES"); }
C.Table Tennis Game 2
题目大意：给出a,b,k，问(a,b)最多被分解为几个(k,x)或(x,k)（x<k）的和，若无解输出-1。
思路：判断是否有解然后输出a/k+b/k就行了，怎么判断有解就变成了本场比赛最大的hack点，正确做法是(a<k&&b%k!=0)||(b<k&&a%k!=0)就无解，错误做法有a/k+b/k>0就有解，a<k且b<k时无解等。
#include<cstdio> #include<algorithm> using namespace std; inline int read() { int x=0;char c; while((c=getchar())<‘0‘||c>‘9‘); for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=(x<<3)+(x<<1)+c-‘0‘; return x; } int main() { int k,a,b,ans; k=read();a=read();b=read(); if(a<k&&b%k)return 0*puts("-1"); if(b<k&&a%k)return 0*puts("-1"); printf("%d",a/k+b/k); }
D.Artsem and Saunders
题目大意：N<=100,000，给出[1,n]到[1,n]的映射f(x)，求[1,n]到[1,m]的映射g(x)和[1,m]到[1,n]的映射h(x)，使得任意x属于[1,m]g(h(x))=x，任意x属于[1,n]h(g(x))=f(x)。
思路：观察发现对于每组相等的f(x)的x，必须要有一个满足x=f(x)，这些x全部映射到[1,m]中一个再映射到f(x)就行了。
#include<cstdio> inline int read() { int x=0;char c; while((c=getchar())<‘0‘||c>‘9‘); for(;c>=‘0‘&&c<=‘9‘;c=getchar())x=(x<<3)+(x<<1)+c-‘0‘; return x; } #define MN 100000 int a[MN+5],c[MN+5],p[MN+5],pn; int main() { int n=read(),i; for(i=1;i<=n;++i)if((a[i]=read())==i)p[c[i]=++pn]=i; for(i=1;i<=n;++i)if(!c[a[i]])return 0*puts("-1"); printf("%d\n",pn); for(i=1;i<=n;++i)printf("%d ",c[a[i]]);puts(""); for(i=1;i<=pn;++i)printf("%d ",p[i]); }
E.Tree Folding
题目大意：一颗树，每次选一个点，把与他相连的两条同长的链并成一条（链上不能向其他地方连），问最后能否把树并成一条链，能的话求出最短链长。
思路：我瞎yy了一个做法，不会证明，请随意意会。求出每个点作为根时他每个儿子的子树深度，如果深度的种数超过2则无解，若全部都不超过2则答案为每个点为根时得到的两种深度相加中的最小值，算深度可以DP O(n)求出以1为根的情况然后O(1)移动根。
#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 200000 struct edge{int nx,t;}e[MN*2+5]; int h[MN+5],en,d[MN+5],d1[MN+5],d2[MN+5],c[MN+5],g; inline void ins(int x,int y) { e[++en]=(edge){h[x],y};h[x]=en; e[++en]=(edge){h[y],x};h[y]=en; } void cal(int x,int d) { if(!d1[x])d1[x]=d;else if(d1[x]!=d) if(!d2[x])d2[x]=d;else if(d2[x]!=d)g=1; } void pre(int x,int f) { for(int i=h[x];i;i=e[i].nx)if(e[i].t!=f) { pre(e[i].t,x); if(d[e[i].t]>=d[x])c[x]=d[x],d[x]=d[e[i].t]; else if(d[e[i].t]>c[x])c[x]=d[e[i].t]; cal(x,d[e[i].t]); } ++d[x];++c[x]; } void dfs(int x,int f,int fd) { if(f)cal(x,fd); for(int i=h[x];i;i=e[i].nx)if(e[i].t!=f) dfs(e[i].t,x,max(fd+1,d[x]==d[e[i].t]+1?c[x]:d[x])); } int main() { int n=read(),i,ans; for(i=1;i<n;++i)ins(read(),read()); pre(1,0);dfs(1,0,0); if(g)return 0*puts("-1"); for(ans=d1[1]+d2[1],i=2;i<=n;++i)ans=min(ans,d1[i]+d2[i]); while(ans%2==0)ans/=2; printf("%d",ans); }
Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)