CodeForces - 1382A Common Subsequence
题意：找出两个数组中的一个相同的数，若无输出NO,若有，输出YES并输出这个数。
AC代码：
#include<bits/stdc++.h> using namespace std;typedef long long ll;const int maxn=0x3f3f3f3f; const int N=1010;#define mem(a,b) memset(a,b,sizeof(a))int a[N],b[N]; int book[N]; int main() {int t;scanf("%d",&t);while(t--){memset(book,0,sizeof(book));int n,m,flag=0,u;scanf("%d%d",&n,&m);for(int i=0; i<n; i++){scanf("%d",&a[i]);book[a[i]]=1;}for(int i=0; i<m; i++){scanf("%d",&b[i]);if(book[b[i]]==1)flag=1,u=b[i];}if(flag)printf("YES\n1 %d\n",u);elseprintf("NO\n");} }
CodeForces - 1382B Sequential Nim
题意：有n堆石子，每次取石子只能按顺序堆中取走，至少拿一个石子，最多把这堆拿完，不能操作的算输。
思路：只需要判断从开始连续为1个石子的堆数即可，当连续为1个石子的堆数为奇数时，后手胜，反之先手胜，特判一下，如果n堆全是1，那么奇数先手胜，偶数后手胜。
AC代码：
#include<bits/stdc++.h> using namespace std;typedef long long ll;const int maxn=0x3f3f3f3f; const int N=100100;#define mem(a,b) memset(a,b,sizeof(a))int main() {int t,n;scanf("%d",&t);while(t--){int num=0,x,flag=0;scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d",&x);if(x==1&&flag==0)num++;else flag=1;}if(num==n){if(num%2)printf("First\n");else printf("Second\n");}else if(num%2==0)printf("First\n");else printf("Second\n");} }
CodeForces - 1382C1 Prefix Flip (Easy Version)
题意：输入两个长度为n的01字符串 str1 和 str2 ，操作：选择长度为 i 的前缀，全部取反并逆置，问能否在3n个操作以内使 str1 和 str2 相等，输出操作次数以及每次操作所选择的前缀i。
思路：如果str1[i]!=str2[i],先取前缀 i，然后再取前缀1，然后再取前缀 i 即可，长度最大为3n。
AC代码：
#include<bits/stdc++.h> using namespace std;typedef long long ll;const int maxn=0x3f3f3f3f; const int N=1010;#define mem(a,b) memset(a,b,sizeof(a))char str1[N],str2[N]; int ans[3*N];int main() {int t,n;scanf("%d",&t);while(t--){int num=0,x,flag=0;scanf("%d",&n);scanf("%s%s",str1,str2);for(int i=0; i<n; i++){if(str1[i]!=str2[i]){ans[num++]=i+1;ans[num++]=1;ans[num++]=i+1;}}printf("%d",num);for(int i=0;i<num;i++)printf(" %d",ans[i]);printf("\n");} }
CodeForces - 1382C2 Prefix Flip (Hard Version)
题意：输入两个长度为n的01字符串 str1 和 str2 ，操作：选择长度为 i 的前缀，全部取反并逆置，问能否在2n个操作以内使 str1 和 str2 相等，输出操作次数以及每次操作所选择的前缀i。
思路：把str1串变成全0序列的操作记录下来存到a[]数组中。把str2串也变成全0序列的操作记录下来存到b[]数组中，把a[]数组正序输出，b[]数组倒序输出即可。
AC代码：
#include<bits/stdc++.h> using namespace std;typedef long long ll;const int maxn=0x3f3f3f3f; const int N=101000;#define mem(a,b) memset(a,b,sizeof(a))char str1[N],str2[N]; int ans[2*N]; int a[N],b[N];int main() {int t,n;scanf("%d",&t);while(t--){int num=0,x=0,y=0;scanf("%d",&n);scanf("%s%s",str1,str2);str1[n]='0';str2[n]='0';for(int i=1; i<=n; i++){if(str1[i]!=str1[i-1])a[x++]=i;if(str2[i]!=str2[i-1])b[y++]=i;}printf("%d",x+y);for(int i=0;i<x;i++)printf(" %d",a[i]);for(int i=y-1;i>=0;i--)printf(" %d",b[i]);printf("\n");} }