首页 > 代码库 > Codeforces Round #394 (Div. 2) 解题报告
Codeforces Round #394 (Div. 2) 解题报告
开始补题，今天下午virtual参赛，过了ABC，D题因为一点小错误而没能在比赛时间中AC，时间到了之后几分钟就发现了问题所在，略有遗憾。之后一直冥思苦想E题，在提示下终于明白，真的是给这样组合题画风的题目跪了，只能说继续加油，扩展思路吧。
A题
题目地址
只有奇偶数个数相差小于等于1时可以，需要特判不能使二者均为0的情况。
参考代码
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 typedef unsigned long long ull; 7 int a,b; 8 int main() 9 { 10 scanf("%d %d",&a,&b); 11 int re=abs(a-b); 12 if(re<=1&&(b!=0||a!=0)) 13 printf("YES\n"); 14 else 15 printf("NO\n"); 16 17 }
B题
题目地址
分别根据给出的数据算出二者各点之间的距离，由于数据量小，只需逐个比较，看是否有情况完全匹配上，如果有，则可能是相同的。
参考代码：
1 int a[55],b[55],c[55],d[55]; 2 int main() 3 { 4 scanf("%d %d",&n,&L); 5 int i; 6 for(i=0;i<n;i++) 7 scanf("%d",&a[i]); 8 a[n]=a[0]; 9 for(i=0;i<n;i++) 10 scanf("%d",&b[i]); 11 b[n]=b[0]; 12 for(i=0;i<n;i++) 13 { 14 c[i]=(a[i+1]-a[i]+L)%L; 15 d[i]=(b[i+1]-b[i]+L)%L; 16 } 17 int j; 18 for(i=0;i<n;i++) 19 { 20 for(j=0;j<n;j++) 21 { 22 if(c[j]!=d[(i+j)%n]) 23 break; 24 } 25 if(j==n) 26 {printf("YES\n");return 0;} 27 } 28 printf("NO\n"); 29 return 0; 30 }
C题
题目地址
我的做法是dp，想法是非常简单基础的递推，写起来比较麻烦但思路并不复杂，想到怎么递推就直接翻译到代码上。具体递推方法参见代码，应该已经比较清晰了。（写成这样一遍过也是挺开心的）
参考代码
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 typedef unsigned long long ull; 7 const int INF=1000000; 8 char code[60][60]; 9 int a[5]; 10 int n,m; 11 int tmp; 12 int ci[55][3][3][3]; 13 bool c[4]; 14 int re(char x) 15 { 16 if(x>=‘0‘&&x<=‘9‘) 17 return 1; 18 else if(x==‘#‘||x==‘*‘||x==‘&‘) 19 return 2; 20 else return 3; 21 } 22 void cnt(int j) 23 { 24 for(int i=0;i<5;i++) 25 a[i]=INF; 26 for(int i=0;i<=m/2;i++) 27 { 28 tmp=re(code[j][i]); 29 // if(j==0) 30 // printf("j=%d tmp=%d\n",j,tmp); 31 a[tmp]=min(a[tmp],i); 32 if(i>=1) 33 {tmp=re(code[j][m-i]); 34 // if(j==0) 35 // printf("j=%d tmp=%d\n",j,tmp); 36 a[tmp]=min(a[tmp],i);} 37 } 38 } 39 void chu(int x) 40 { 41 for(int i=0;i<2;i++) 42 { 43 for(int j=0;j<2;j++) 44 { 45 for(int s=0;s<2;s++) 46 { 47 ci[x][i][j][s]=INF; 48 } 49 } 50 } 51 // ci[x][0][0][0]=0; 52 } 53 int main() 54 { 55 // memset(c[]) 56 scanf("%d %d",&n,&m); 57 int i; 58 for(i=0;i<n;i++) 59 { 60 scanf("%s",code[i]); 61 } 62 chu(0); 63 cnt(0); 64 ci[0][0][0][1]=a[3]; 65 ci[0][0][1][0]=a[2]; 66 ci[0][1][0][0]=a[1]; 67 // printf("%d %d %d\n",ci[0][1][0][0],ci[0][0][1][0],ci[0][0][0][1]); 68 for(i=1;i<n;i++) 69 { 70 cnt(i); 71 chu(i); 72 // if(i==2) 73 // printf("a1=%d\n",a[1]); 74 ci[i][0][0][1]=min(ci[i-1][0][0][1],ci[i-1][0][0][0]+a[3]); 75 ci[i][0][1][0]=min(ci[i-1][0][1][0],ci[i-1][0][0][0]+a[2]); 76 ci[i][1][0][0]=min(ci[i-1][1][0][0],ci[i-1][0][0][0]+a[1]); 77 ci[i][1][1][0]=min(ci[i-1][1][1][0],min(ci[i-1][0][1][0]+a[1],ci[i-1][1][0][0]+a[2])); 78 ci[i][1][0][1]=min(ci[i-1][1][0][1],min(ci[i-1][0][0][1]+a[1],ci[i-1][1][0][0]+a[3])); 79 ci[i][0][1][1]=min(ci[i-1][0][1][1],min(ci[i-1][0][0][1]+a[2],ci[i-1][0][1][0]+a[3])); 80 ci[i][1][1][1]=min(ci[i-1][1][1][1],min(ci[i-1][1][1][0]+a[3],min(ci[i-1][1][0][1]+a[2],ci[i-1][0][1][1]+a[1]))); 81 // printf("i=%d %d\n",i,ci[i][1][1][1]); 82 } 83 // printf("!!!~~%d\n",ci[1][0][1][1]); 84 // printf("~~~%d\n",ci[1][1][0][1]); 85 // printf("~~~%d\n",ci[2][1][1][1]); 86 printf("%d\n",ci[n-1][1][1][1]); 87 }
D题
题目地址
个人感觉这道题的难度都不及C题……由于ci彼此不同，贪心的做法就是保证按已给出的ci大小顺序使ci最小程度的单调递增，那么当然就是尽可能地使ci相邻之间只增加1。无法做到这一点的情况只有若要满足此bi已经小于l，这时赋给bi以l即可，而如果有bi已经大于了r，那么无论怎么调整也无法实现符合条件，即不成立。
参考代码：
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 typedef unsigned long long ull; 7 const int MAXN=100005; 8 int n,l,r; 9 int st; 10 int a[MAXN],c[MAXN],re[MAXN],res[MAXN]; 11 int tem; 12 int jia; 13 int main() 14 { 15 scanf("%d %d %d",&n,&l,&r); 16 int i; 17 for(i=0;i<n;i++) 18 { 19 scanf("%d",&a[i]); 20 } 21 for(i=0;i<n;i++) 22 { 23 scanf("%d",&tem); 24 c[tem]=i; 25 } 26 res[c[1]+1]=re[1]=l; 27 for(i=2;i<=n;i++) 28 { 29 jia=0; 30 // if(a[c[i]]>=a[c[i-1]]) 31 // { 32 jia=a[c[i]]-a[c[i-1]]+1; 33 // } 34 re[i]=re[i-1]+jia; 35 if(re[i]<l) 36 re[i]=l; 37 if(re[i]>r) 38 { 39 // printf("%d\n",re[i]); 40 printf("-1\n"); 41 return 0; 42 } 43 res[c[i]+1]=re[i]; 44 } 45 // printf("%d\n",re[n]); 46 if(re[n]<=r) 47 {for(i=1;i<=n;i++) 48 printf("%d ",res[i]);} 49 // else 50 // printf("-1"); 51 printf("\n"); 52 return 0; 53 }
E题（%%%）
构造法，利用了2的1到n次幂次之和<2的n+1次幂。
如果有某一点入度大于4显然是不成立的，若不然，依次构造即一定可以构造出来。
具体构造就是使边的长度从2^30逐渐变小。
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 typedef unsigned long long ull; 7 int dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}}; 8 int n; 9 int rudu[35]; 10 int x[35],y[35]; 11 int tem1,tem2; 12 vector <int> ver[35]; 13 bool vi[35]; 14 void dfs(int num,int xx,int yy,int len,int from) 15 { 16 vi[num]=true; 17 x[num]=xx; 18 y[num]=yy; 19 int i; 20 int j=0; 21 for(i=0;i<ver[num].size();i++) 22 { 23 if(vi[ver[num][i]]==true) 24 continue; 25 if(j+from==3) 26 j++; 27 dfs(ver[num][i],xx+dir[j][0]*len,yy+dir[j][1]*len,len/2,j); 28 j++; 29 } 30 } 31 int main() 32 { 33 scanf("%d",&n); 34 int i; 35 for(i=0;i<n-1;i++) 36 { 37 scanf("%d %d",&tem1,&tem2); 38 ver[tem1].push_back(tem2); 39 ver[tem2].push_back(tem1); 40 rudu[tem1]++;rudu[tem2]++; 41 } 42 for(i=1;i<=n;i++) 43 { 44 if(rudu[i]>4) 45 { 46 printf("NO\n"); 47 return 0; 48 } 49 } 50 memset(vi,false,sizeof(vi)); 51 dfs(1,0,0,1<<30,-1); 52 printf("YES\n"); 53 for(i=1;i<=n;i++) 54 { 55 printf("%d %d\n",x[i],y[i]); 56 } 57 return 0; 58 59 }
Codeforces Round #394 (Div. 2) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。