区块链技术博客
www.b2bchain.cn

Codeforces Round #658 (Div. 2)的讲解

这篇文章主要介绍了Codeforces Round #658 (Div. 2)的讲解,通过具体代码讲解7648并且分析了Codeforces Round #658 (Div. 2)的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了Codeforces Round #658 (Div. 2)的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7648.html。具体如下:

比赛链接:https://codeforces.com/contest/1382

A.Common Subsequence

题意

给你两组数,问你有没有相同 的书,有的话,输出最短的那组(大家都知道,1是最小的)

AC

#include<bits/stdc++.h> using namespace std; #define LL long long const LL N=50005; int a[1005],b[1005]; int main() {     int t;     scanf("%d",&t);     while(t--)     {         int n,m;         memset(a,0,sizeof(a));         scanf("%d%d",&n,&m);         int x;         for(int i=1;i<=n;i++)         {             scanf("%d",&x);             a[x]++;         }         int flog=0;         for(int i=1;i<=m;i++)         {             scanf("%d",&x);             if(a[x])             {                 flog=x;             }         }         if(flog)         {             printf("YESn");             printf("1 %dn",flog);         }         else         {             printf("NOn");         }     }     return 0; } 

B.Sequential Nim

题意:

两个人玩区石子游戏,有n堆,第i堆有a[i]个,每个人只能按堆的顺序拿,就是前面这堆没有拿完,不能拿下一堆。谁先不能拿就输了。

思路:

谁先遇到大于1的石子堆,谁就一定不会输,因为大于1的石子堆,我可以选择全拿完和留一个,这两种状态结果是互斥的,必定会有一个状态的必胜态,所以只要判断到大于1的数前面的1的数量就行,若是全1的情况,那就轮流拿,单独判断一下就行。

#include<bits/stdc++.h> using namespace std; #define LL long long const LL N=50005; int a[1005],b[1005]; int main() {     int t;     scanf("%d",&t);     while(t--)     {         int n;         scanf("%d",&n);         int num=0,flog=0;         int x;         for(int i=1;i<=n;i++)         {             scanf("%d",&x);             if(x==1&&flog==0)             {                 num++;             }             if(x>1)             {                 flog=1;             }         }         if((num%2==1&&flog)||(num%2==0&&flog==0))         {             printf("Secondn");         }         else         {             printf("Firstn");         }     }     return 0; } 

C2 Prefix Flip (Hard Version)

题意;

给你两个长度相同的01字符串a,b,有一种操作,我们可以把一个字符串长度为x的前缀拿出来,把0,1互换,(就像是异或一下)然后再把这个前缀翻转(掉个头)放回到原字符串中,问我们通过几次这种操作把a转换为b。操作数小于2*n;

思路:

因为我们每次拿的都是前缀,那么也就是说,后面的不会动了,那么我们可以从后往前来,遇到不同的,就判断a开头位置和b当前位置(因为不同就要进行”异或“然后翻转,会把第一个数翻转到当前位置上,所以判断a第一个位置和b当前位置)
如果第一位置和当前位置相同,要把第一位置单独转一下,(因为相同,异或再转过来就不同了)记录一下每次翻转的位置就是答案。
C1可以暴力模拟,C2就要有技巧的记录用当前所翻转的区间,然后也是模拟。

AC

#include<bits/stdc++.h> using namespace std; #define LL long long const LL N=100005; char a[N],b[N]; int ans[2*N]; int main() {     int t;     scanf("%d",&t);     while(t--)     {         int n;         scanf("%d",&n);         scanf("%s%s",a,b);         int num=0;         int l=0,r=n-1;         int flog=0;         int fz=0;         for(int i=n-1;i>=0;i--)         {              if(flog==0)             {                 if((b[i]!=a[r]&&fz%2==0)||(fz%2&&b[i]==a[r]))                 {                     if((b[i]==a[l]&&fz%2==0)||(b[i]!=a[l]&&fz%2))                     {                         ans[num++]=1;                     }                     ans[num++]=i+1;                     fz++;                     flog=1;                     l++;                 }                 else                 {                     r--;                 }             }             else             {                 if((b[i]!=a[l]&&fz%2==0)||(b[i]==a[l]&&fz%2))                 {                     if((b[i]==a[r]&&fz%2==0)||(b[i]!=a[r]&&fz%2))                     {                         ans[num++]=1;                     }                     ans[num++]=i+1;                     fz++;                     flog=0;                     r--;                 }                 else                 {                     l++;                 }             }         }         printf("%dn",num);         for(int i=0;i<num;i++)         {             printf("%d ",ans[i]);         }         if(num)printf("n");     }     return 0; } 

D. Unmerge

比赛打着当时没看,直接睡了,其实也是挺水的题

题意

给你一个长度为2n的数组,为你是不是由两个为n的数组构成的。
构成原理
假设两个数组a,b,长度分别是n,m;
每次取两个数组的最小值到新数组。
最后新数组长度为(n+m)
比如a(3,1),b(2,4)
a+b=(2,3,1,4).

思路

其实就是一个小背包,我们可以发现每次去数,只能取到下一个大于当前数的位置,那么我们记录一下这些数的数量,记录完了之后,我们可以选择每个区间取或者不取,取就放a数组,不取就放b数组,最后我们只需要判断能不能构成长度为n的a数组就行(因为给出的数组长度为2*n)

AC

#include<bits/stdc++.h> using namespace std; #define LL long long const LL N=100005; int dp[4005]; int a[4005]; int v[4005]; int main() {     int t;     scanf("%d",&t);     while(t--)     {         int n;         scanf("%d",&n);         int tot=0,k=1;         for(int i=1;i<=2*n;i++)         {             scanf("%d",&a[i]);             if(a[i]>a[k])             {                 v[++tot]=i-k;                 k=i;             }         }         v[++tot]=2*n+1-k;         memset(dp,0,sizeof(dp));         dp[0]=1;         for(int i=1;i<=tot;i++)         {             for(int j=n;j>=v[i];j--)             {                 dp[j]=max(dp[j-v[i]],dp[j]);             }         }         if(dp[n])         {             printf("YESn");         }         else         {             printf("NOn");         }     }     return 0; } 

E Mastermind

待补…

本文地址https://www.b2bchain.cn/7648.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » Codeforces Round #658 (Div. 2)的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们