首页 > 代码库 > Codeforces Round #423 （Div. 2）A B C D
Codeforces Round #423 （Div. 2）A B C D
A. Restaurant Tables
题意是一个点单人座有a个双人座有b个，有n组人，每组人有一个或两个人。当一个人时优先坐单人座的没有就坐没有人坐的双人座，然后才是在已经坐了一人的双人座，还没有就拒绝为他服务。当两个人时，只坐双人座的没有就拒绝服务。问这个店要拒绝服务多少人。
直接模拟下就行了。
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 using namespace std; 5 6 int main(){ 7 int n,a,b,flag = 0,num,ans= 0; 8 cin>>n>>a>>b; 9 for(int i = 1; i <= n; i ++){ 10 cin>>num; 11 if(num==1){ 12 if(a>0)a--; 13 else if(a==0){ 14 if(b>0)b--,flag++; 15 else if(b==0&&flag>0)flag--; 16 else if(b==0&&flag==0)ans++; 17 } 18 }else if(num==2){ 19 if(b>0)b--; 20 else if(b==0)ans+=2; 21 } 22 } 23 cout << ans << endl; 24 return 0; 25 }
B. Black Square
题意是有n行m列，让W变成B，使的所以的B组成一个正方形，求最小的改变数，没有就输出-1，一开始我以为B会有两个以上的区域，看了别人的代码才发现不是这么一回事，
B所在的区域最多只有一个区域，这样求下出先B的最大i，最小i，最大j，最小j，max((di-mi),(dj-mj))就是最小的正方形边长了，只要边长小于n或者m就是-1，这样就求出答案了。
还是要多刷题多思路，加油！
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 int n,m,di,dj,mi=1e9,mj=1e9; 6 char str[110][110]; 7 8 int main(){ 9 scanf("%d %d",&n,&m); 10 for(int i = 0; i < n; i ++)cin>>str[i]; 11 int ans = 0; 12 for(int i = 0; i < n; i ++){ 13 for(int j = 0; j < m; j ++){ 14 if(str[i][j]==‘B‘){ 15 ans++; 16 di=max(di,i),mi=min(mi,i); 17 dj=max(dj,j),mj=min(mj,j); 18 } 19 } 20 } 21 if(!ans){ 22 puts("1"); 23 return 0; 24 } 25 26 int k = max((di-mi),(dj-mj))+1; 27 printf("%d\n",k>n||k>m?-1:k*k-ans); 28 return 0; 29 }
C. String Reconstruction
题意：有n个字符串，每个字符串出现了k次，每次出现的位置时是ki,求完整的字符串，要求字典最小。一开始直接暴力了，时间超限了。
后来想想，n个字符串可以让他们分别标记为1，2，3...n，这样每输入i字符串的k次位置时，可以用数组保存下。
当然，有些字符串出现的位置可以相同，这样可以让数组储存长度最大的那个字符串。
输出时，可以定义一个变量p，它的作用代表已经输出了p个字符。当然，之前输入位置时要先计算下可以输出的最大字符串记为Max，
然后定义一个i用来扫描数组，
（一）当a[i]=0,且i>p时说明当前已经输出了p个字符，现在要输出第i个字符，由于a[i]没有被标记就直接输出字符a，因为是求字典最小的，所以就直接输出a了。
（二）当a[i]=0,且i<=p时，说明第i个位置没有被标记，又因为i<=p，就直接扫描下一个位置了。
（三）这个就是最重要的了。到这步就说明第i个位置已经被标记了，先取出它的值（代表了第几个字符串），然后在算下长度len，
①当i+len-1<=p时（-1是因为要输出len个字符的话是从i开始的）说明第i个位置代表的字符串已经被输出了，比如前面输出了abcde，现在要从第3个位置输出cd，由于之前输出了，就直接扫描下一个位置就行了，
②当i+len-1>p时，就输出a[i]代表的字符串从第p-i+1开始输出就行，比如前面输出了abcdef，现在要从第4个位置输出defgh，由于前面输出了def，所以现在直接输出gh就行了。
所以用线性的时间就可以做出来了，一时头脑发热就想出来了，加油！
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <vector> 5 using namespace std; 6 const int MAX = 2e6+10; 7 int a[MAX]; 8 vector<string> vs; 9 int main(){ 10 int n,Max = 0,k,num; 11 scanf("%d",&n); 12 for(int i = 1; i <= n; i ++){ 13 string s; 14 cin >> s; 15 vs.push_back(s); 16 scanf("%d",&k); 17 for(int j = 1; j <= k; j ++){ 18 scanf("%d",&num); 19 if(a[num]==0){ 20 a[num]=i; 21 }else if(vs[a[num]-1].length() < s.length()){ 22 a[num] = i; 23 } 24 if(num+s.length()-1 > Max){ 25 Max = num+s.length()-1; 26 } 27 } 28 } 29 int i = 1,p=0; 30 while(i <= Max){ 31 if(a[i]==0&& i>p){ 32 printf("a"); 33 i++;p++; 34 }else if(a[i]==0&&i<=p){ 35 i++; 36 }else{ 37 int ans = a[i]; 38 int len = vs[ans-1].length(); 39 40 if(i+len-1<=p){ 41 i++;continue; 42 }else if(i+len-1>p){ 43 string ss = vs[ans-1].substr(p-i+1,len); 44 cout << ss; 45 p = i+len-1; 46 i++; 47 } 48 } 49 } 50 return 0; 51 }
D. High Load
题意是有n个节点，其中有k个输出节点，输出节点要连接输出网络，所以可以把它看出只连接一个节点的节点，其它节点只要要连接两个节点,要求出输出节点最远的两个的最小距离，并输出所有节点的连接情况。
想好好久也想不出，看了大牛的才发现这题是多么的简单，可以把一个节点当成最中心节点，然后在它上连接K个节点就行，一直连下去。
下图是 n=7,k=3的情况，看了这图就应该可以秒做这到题目了。
直接贴代码:
1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4 5 int main(){ 6 int n,k; 7 cin>>n>>k; 8 int h = (n-1)/k; 9 if((n-1)%k==0) printf("%d\n",2*h); 10 else if((n-1)%k==1)printf("%d\n",2*h+1); 11 else printf("%d\n",2*h+2); 12 for(int i = 2; i <= k+1; i ++)printf("1 %d\n",i); 13 for(int i = k+2; i <= n; i ++)printf("%d %d\n",i-k,i); 14 return 0; 15 }
Codeforces Round #423 （Div. 2）A B C D