首页 > 代码库 > Codeforces Round #279 (Div. 2)
Codeforces Round #279 (Div. 2)
A. Team Olympiad
水题英文还这么长。。。
1 #include<bits/stdc++.h> 2 #define eps 1e-9 3 #define FOR(i,j,k) for(int i=j;i<=k;i++) 4 using namespace std; 5 typedef long long LL; 6 int i,j,k,n,m,x,y,T,ans,big,cas; 7 bool flag; 8 vector <int> a[5]; 9 int num,t;10 int main()11 {12 scanf("%d",&n);13 for (i=1;i<=n;i++)14 {15 scanf("%d",&t);16 a[t].push_back(i);17 }18 num=min((int)a[1].size(),(int)a[2].size());19 num=min(num,(int)a[3].size());20 printf("%d\n",num);21 for (i=0;i<num;i++)22 {23 printf("%d %d %d\n",a[1][i],a[2][i],a[3][i]);24 }25 return 0;26 }
B. Queue
有n个人排队，每个人都有一个编号，现给出每个人前边一人的编号和后边一人的编号（如果没有人则是0），求出原来队中人的顺序（输出编号）。
模拟，因为编号只有10^6，因此可以开两个10^6的数组，a[i][0]记录编号为i的人前边的前边的人的编号，a[i][1]记录编号为i的人后边的后边的人的编号。
显然从0开始能够确定偶数位置人的顺序，然后将他们标记为-1，再根据剩下的确定奇数位置的人的顺序即可。
1 #include<bits/stdc++.h> 2 #define eps 1e-9 3 #define FOR(i,j,k) for(int i=j;i<=k;i++) 4 using namespace std; 5 typedef long long LL; 6 int i,j,k,n,m,x,y,T,big,cas,a[1000006][2],st,l[200005],r[200005],ans[200005],temp; 7 bool flag; 8 int main() 9 {10 scanf("%d",&n);11 for (i=1;i<=n;i++)12 {13 scanf("%d%d",&l[i],&r[i]);14 a[r[i]][0]=l[i];15 a[l[i]][1]=r[i];16 }17 for (st=a[0][1],j=2;st!=0;j+=2)//确定偶数位置人 18 {19 ans[j]=st;20 temp=a[st][1];21 a[st][0]=-1;//已经确定位置的人标记为-1 22 a[st][1]=-1;23 st=temp;24 }25 for (i=1;i<=n;i++) 26 if (a[l[i]][0]==0) 27 {28 st=l[i];//找到奇数位置最前边的人 29 break;30 }31 ans[1]=st; 32 j=1;33 for (;st!=0;st=a[st][1],j+=2)//确定奇数位置的人 34 {35 ans[j]=st;36 }37 for (i=1;i<n;i++) printf("%d ",ans[i]);38 printf("%d\n",ans[n]);39 return 0;40 }
C. Hacking Cypher
给一个大数（长度10^6）问能够否分割成两个数，前边的能被a整除，后边的能被b整除，所有数不能有前导零。
模拟，取模的几个性质应该都懂吧，设某个数是def，那么def=d*100+e*10+f ，def mod n = ((d mod n)*(100 mod n)+(e mod n)*(10 mod n)+f mod n) mod n
设pre[i]为前i位能否整除a，suf[j]为后j为能否整除b。先预处理出pre和suf，显然pre[i]=true 并且 suf[i+1]=true的时候就是答案。
求suf的时候就可以通过前一位的pre值判断是否有解了，因此代码中没有开suf数组。
1 #include<bits/stdc++.h> 2 #define eps 1e-9 3 #define FOR(i,j,k) for(int i=j;i<=k;i++) 4 using namespace std; 5 typedef long long LL; 6 int i,j,k,n,m,x,y,T,ans,big,cas,a,b,len,w; 7 bool flag,pre[1000005]; 8 char s[1000005]; 9 int main()10 {11 scanf("%s",s);12 scanf("%d%d",&a,&b);13 len=strlen(s);14 for (i=0;i<len-1;i++)15 {16 x=(x*10+s[i]-‘0‘)%a;17 if (x==0)18 {19 pre[i]=true;20 }21 }22 w=1;x=0;23 for (i=len-1;i>0;i--)24 {25 x=(x+w*(s[i]-‘0‘))%b;26 w=w*10%b;27 if (x==0&&pre[i-1]&&s[i]!=‘0‘)28 {29 printf("YES\n");30 for (j=0;j<i;j++)31 {32 printf("%c",s[j]);33 }34 printf("\n");35 for (j=i;j<len;j++)36 {37 printf("%c",s[j]);38 }39 printf("\n");40 return 0;41 }42 }43 44 printf("NO\n");45 return 0;46 }
D. Chocolate
给两个巧克力，尺寸分别为a1*b1,a2*b2，现在想让它们的面积相同，有两种措施：
1.吃掉其中一个巧克力的一半
2.吃掉其中一个巧克力的1/3
并且剩下每次操作后剩余巧克力尺寸是整数，问至少操作几次。。。并输出最终巧克力的尺寸
先让a1,a2,b1,b2分别不断整除2再不断整除3，直到不能整除为止，如果最终的a1*b1不等于a2*b2，则说明无解，输出-1
（假设存在有解a1,b1,a2,b2，则由题目一定有a1*b1=a2*b2，a1*b1,a2*b2一定有相同的2的因子数和3的因子数，这时让它们不断整除2整除3，直到不能整除为止，a1*b1=a2*b2仍然成立）
设s1=a1*b1，s2=a2*b2，则如果s1/gcd(s1,s2)不等于s2/gcd(s1,s2)，说明无解。
有解的时候s1‘=s2‘，一定有s1‘/gcd(s1‘,s2‘)=s2‘/gcd(s1‘,s2‘)=s1/gcd(s1,s2)=s2/gcd(s1,s2)
下面就是解这个式子：
s1*(1/2)x1*(2/3)y1 =s2*(1/2)x2*(2/3)y2 可以化简为
s1 =s2 * 2x1-x2-y1+y2 * 3y1-y2
找s1与s2关于2和3的因子数之差就能算出答案。
1 #include<bits/stdc++.h> 2 #define eps 1e-9 3 #define FOR(i,j,k) for(int i=j;i<=k;i++) 4 using namespace std; 5 typedef long long LL; 6 LL i,j,k,n,m,x,y,T,ans,big,cas,a[5],b[5],c[5],d[5],t,thr,two; 7 bool flag; 8 int main() 9 {10 for (i=1;i<=4;i++) scanf("%I64d",&a[i]);11 for (i=1;i<=4;i++)12 {13 t=a[i];14 while (t%2==0)15 {16 t/=2;17 b[i]++;//记录因子2的个数 18 }19 while (t%3==0)20 {21 t/=3;22 c[i]++;//记录因子3的个数 23 }24 d[i]=t;25 }26 if (d[1]*d[2]!=d[3]*d[4]) 27 {28 printf("-1\n");29 return 0;30 }31 thr=c[3]+c[4]-c[1]-c[2];32 if (thr>0)33 {34 t=thr;35 while (t>0&&a[3]%3==0)36 {37 a[3]=a[3]*2/3;38 t--;39 }40 while (t>0&&a[4]%3==0)41 {42 a[4]=a[4]*2/3;43 t--;44 }45 } else46 {47 t=-thr;48 while (t>0&&a[1]%3==0)49 {50 a[1]=a[1]*2/3;51 t--;52 }53 while (t>0&&a[2]%3==0)54 {55 a[2]=a[2]*2/3;56 t--;57 }58 }59 two=b[3]+b[4]-b[1]-b[2]+thr;//记得加上因除去因子3而多出来的因子2 60 61 if (two>0)62 {63 t=two;64 while (t>0&&a[3]%2==0)65 {66 a[3]=a[3]/2;67 t--;68 }69 while (t>0&&a[4]%2==0)70 {71 a[4]=a[4]/2;72 t--;73 }74 } else75 {76 t=-two;77 while (t>0&&a[1]%2==0)78 {79 a[1]=a[1]/2;80 t--;81 }82 while (t>0&&a[2]%2==0)83 {84 a[2]=a[2]/2;85 t--;86 }87 }88 printf("%I64d\n",abs(thr)+abs(two));89 printf("%I64d %I64d\n%I64d %I64d\n",a[1],a[2],a[3],a[4]);90 return 0;91 }
E. Restoring Increasing Sequence
给出严格递增的几个数，其中几个数的某几位不知道用符号?给出，输出一种方案。
分类讨论，这类题目写的好烦=。=#
首先讨论与上一位的长度（第一个数的上一位设为0）的关系，如果他们的长度相等再从头到尾递归扫描。
用dfs(i)=0表示到第i位是否需要向前边借位，比如数据：
pre=14349
now=14?4?
now的第5位的问号处只能是0，这时如果要满足题意，就一定要求now的前边4位组成的数 比 pre的前四位组成的数大，因此dfs(5)=1。
如果到递归第一个问号后仍然需要借位，则说明无解，比如：
pre=14949
now=14?49
第一个问号处dfs(3)=1，而前边两位的数不可能比pre的前两位大，因此输出NO。
其它的讨论细节乱搞一下，再乱搞乱搞。。。。还是详见代码吧：
1 #include<bits/stdc++.h> 2 #define eps 1e-9 3 #define FOR(i,j,k) for(int i=j;i<=k;i++) 4 using namespace std; 5 typedef long long LL; 6 int i,j,k,n,m,x,y,T,big,cas,last_len,len; 7 bool flag; 8 char last[10],s[10],bf[10],ans[100005][10]; 9 bool dfs(int x)//false为不需要进位，true表示需要进位 10 { 11 if (x>=len) return 1; 12 if (s[x]==‘?‘) 13 { 14 if (dfs(x+1)) 15 { 16 s[x]=last[x]; 17 if (last[x]==‘9‘) 18 { 19 s[x]=‘0‘; 20 return 1; 21 }else 22 { 23 s[x]=last[x]+1; 24 return 0; 25 } 26 }else 27 { 28 s[x]=last[x]; 29 return 0; 30 } 31 }else 32 { 33 if (s[x]>last[x]) 34 { 35 for (int i=x+1;i<len;i++) 36 { 37 if (bf[i]==‘?‘) s[i]=‘0‘; 38 } 39 return 0; 40 }else 41 if (s[x]<last[x]) 42 { 43 for (int i=x+1;i<len;i++) 44 { 45 if (bf[i]==‘?‘) s[i]=‘0‘; 46 } 47 return 1; 48 }else 49 { 50 return dfs(x+1); 51 } 52 } 53 } 54 55 56 int main() 57 { 58 scanf("%d",&n); 59 strcpy(last,"0"); last_len=0; 60 for (i=1;i<=n;i++) 61 { 62 scanf("%s",s); 63 len=strlen(s); 64 if (last_len>len) 65 { 66 printf("NO\n"); 67 return 0; 68 }else 69 if (last_len<len) 70 { 71 if (s[0]==‘?‘) s[0]=‘1‘; 72 for (j=1;j<len;j++) 73 { 74 if (s[j]==‘?‘) 75 { 76 s[j]=‘0‘; 77 } 78 } 79 strcpy(ans[i],s); 80 last_len=len; 81 strcpy(last,s); 82 }else 83 { 84 strcpy(bf,s); 85 if (dfs(0)) 86 { 87 printf("NO\n"); 88 return 0; 89 }else 90 { 91 strcpy(ans[i],s); 92 last_len=len; 93 strcpy(last,s); 94 } 95 } 96 } 97 printf("YES\n"); 98 for (i=1;i<=n;i++) 99 {100 printf("%s\n",ans[i]);101 }102 return 0;103 }
F. Treeland Tour
给一棵最多6000个结点的树，每个点有权值，求其中的一条链，使得LIS的序列和最大。
网上有人竟然枚举起点+求LIS o(N^2logN) 通过了，醉了，看来数据是很水了，在board上点开看了几个人的代码也是这样写的，不知道正解是怎样
啊，第一场做出5道题的CF比赛，第一次排名这么靠前，只是不算rating。。。截个图
Codeforces Round #279 (Div. 2)