比赛链接：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("YES\n");
printf("1 %d\n",flog);
}
else
{
printf("NO\n");
}
}
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("Second\n");
}
else
{
printf("First\n");
}
}
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("%d\n",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("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
E Mastermind
待补…
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
