A. Common Subsequence

You are given two arrays of integers a1,…,an and b1,…,bm.

Your task is to find a non-empty array c1,…,ck that is a subsequence of a1,…,an, and also a subsequence of b1,…,bm. If there are multiple answers, find one of the smallest possible length. If there are still multiple of the smallest possible length, find any. If there are no such arrays, you should report about it.

A sequence a is a subsequence of a sequence b if a can be obtained from b by deletion of several (possibly, zero) elements. For example, [3,1] is a subsequence of [3,2,1] and [4,3,1], but not a subsequence of [1,3,3,7] and [3,10,4].

Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases. Next 3t lines contain descriptions of test cases.

The first line of each test case contains two integers n and m (1≤n,m≤1000) — the lengths of the two arrays.

The second line of each test case contains n integers a1,…,an (1≤ai≤1000) — the elements of the first array.

The third line of each test case contains m integers b1,…,bm (1≤bi≤1000) — the elements of the second array.

It is guaranteed that the sum of n and the sum of m across all test cases does not exceed 1000 (∑i=1tni,∑i=1tmi≤1000).

Output
For each test case, output "YES" if a solution exists, or "NO" otherwise.

If the answer is "YES", on the next line output an integer k (1≤k≤1000) — the length of the array, followed by k integers c1,…,ck (1≤ci≤1000) — the elements of the array.

If there are multiple solutions with the smallest possible k, output any.

Example
inputCopy
5
4 5
10 8 6 4
1 2 3 4 5
1 1
3
3
1 1
3
2
5 3
1000 2 2 2 3
3 1 5
5 5
1 2 3 4 5
1 2 3 4 5
outputCopy
YES
1 4
YES
1 3
NO
YES
1 3
YES
1 2
Note
In the first test case, [4] is a subsequence of [10,8,6,4] and [1,2,3,4,5]. This array has length 1, it is the smallest possible length of a subsequence of both a and b.

In the third test case, no non-empty subsequences of both [3] and [2] exist, so the answer is "NO".
很简单的一题，就是找最短公共子序列，那么就是找相同的元素。
速度有点慢，第一次还wa了，就是桶排的数组没有清零

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<string>

using namespace std;

int barrel[1005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,x,ans=0;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            barrel[x]=1;
        }
        for(int i=0;i<m;i++)
        {
            cin>>x;
            if(barrel[x])
            ans=x;
        }
        if(ans>0)
        printf("YES\n1 %d\n",ans);
        else 
        cout<<"NO"<<endl;
        for(int i=0;i<=1000;i++)
        barrel[i]=0;
    }
    getchar();
    getchar();
}
# B. Sequential Nim
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n piles of stones, where the i-th pile has ai stones. Two people play a game, where they take alternating turns removing stones.

In a move, a player may remove a positive number of stones from the first non-empty pile (the pile with the minimal index, that has at least one stone). The first player who cannot make a move (because all piles are empty) loses the game. If both players play optimally, determine the winner of the game.

Input
The first line contains a single integer t (1≤t≤1000)  — the number of test cases. Next 2t lines contain descriptions of test cases.

The first line of each test case contains a single integer n (1≤n≤105)  — the number of piles.

The second line of each test case contains n integers a1,…,an (1≤ai≤109)  — ai is equal to the number of stones in the i-th pile.

It is guaranteed that the sum of n for all test cases does not exceed 105.

Output
For each test case, if the player who makes the first move will win, output "First". Otherwise, output "Second".

Example
inputCopy
7
3
2 5 4
8
1 1 1 1 1 1 1 1
6
1 2 3 4 5 6
6
1 1 2 1 2 2
1
1000000000
5
1 2 2 1 1
3
1 1 1
outputCopy
First
Second
Second
First
First
Second
First
Note
In the first test case, the first player will win the game. His winning strategy is:

The first player should take the stones from the first pile. He will take 1 stone. The numbers of stones in piles will be [1,5,4].
The second player should take the stones from the first pile. He will take 1 stone because he can't take any other number of stones. The numbers of stones in piles will be [0,5,4].
The first player should take the stones from the second pile because the first pile is empty. He will take 4 stones. The numbers of stones in piles will be [0,1,4].
The second player should take the stones from the second pile because the first pile is empty. He will take 1 stone because he can't take any other number of stones. The numbers of stones in piles will be [0,0,4].
The first player should take the stones from the third pile because the first and second piles are empty. He will take 4 stones. The numbers of stones in piles will be [0,0,0].
The second player will lose the game because all piles will be empty.
比较简单的一道思维题，就是找能拿到第一个不为1的人，这样他就可以掌控全局，他既可以在后面继续拿到不为1的数，又可以决定谁拿最后一个1。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<string>

using namespace std;

int barrel[1005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,x,ans,i;
        bool flag=0;
        cin>>n;
        for(i=1;i<=n;i++)
        {
        cin>>x;
        if(x!=1&&!flag)
        {
            flag=1;
            ans=i;
        }
        }
        if(flag&&ans%2)
        cout<<"First"<<endl;
        else if(!flag&&(i-1)%2)
        cout<<"First"<<endl;
        else
        cout<<"Second"<<endl;
    }
    getchar();
    getchar();
}

# C1. Prefix Flip (Easy Version)
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
This is the easy version of the problem. The difference between the versions is the constraint on n and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings a and b of length n (a binary string is a string consisting of symbols 0 and 1). In an operation, you select a prefix of a, and simultaneously invert the bits in the prefix (0 changes to 1 and 1 changes to 0) and reverse the order of the bits in the prefix.

For example, if a=001011 and you select the prefix of length 3, it becomes 011011. Then if you select the entire string, it becomes 001001.

Your task is to transform the string a into b in at most 3n operations. It can be proved that it is always possible.

Input
The first line contains a single integer t (1≤t≤1000)  — the number of test cases. Next 3t lines contain descriptions of test cases.

The first line of each test case contains a single integer n (1≤n≤1000)  — the length of the binary strings.

The next two lines contain two binary strings a and b of length n.

It is guaranteed that the sum of n across all test cases does not exceed 1000.

Output
For each test case, output an integer k (0≤k≤3n), followed by k integers p1,…,pk (1≤pi≤n). Here k is the number of operations you use and pi is the length of the prefix you flip in the i-th operation.

Example
inputCopy
5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1
outputCopy
3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1
Note
In the first test case, we have 01→11→00→10.

In the second test case, we have 01011→00101→11101→01000→10100→00100→11100.

In the third test case, the strings are already the same. Another solution is to flip the prefix of length 2, which will leave a unchanged.
模拟就好了，从后面往前将a逐渐变为b
让人做到吐血的题目，交题的时候没有把测试的代码注释掉，再debug的时候鬼使神差把错误的那行注释掉了，一直拿正确的代码在改。
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<string>

using namespace std;

int main()
{
    int t;
    cin>>t;
    string s1,s2;
    while(t--)
    {
        int n,num;
        vector<int> ans;
        cin>>n;
        num=n;
        cin>>s1>>s2;
        //cout<<endl;
        char *p1=&s1[n-1],*p2=&s2[n-1];
        while(num)
        {
            if(*p1!=*p2)
            {
                if(s1[0]==*p2)
                {
                    s1[0]=='1'?s1[0]='0':s1[0]='1';
                ans.push_back(1);
                //cout<<s1<<endl;
                }
                ans.push_back(num);
                for(int i=0;i<num;i++)
                {
                    s1[i]=='1'?s1[i]='0':s1[i]='1';
                }
                //cout<<s1<<endl;
                reverse(&s1[0],&s1[num]);
                //cout<<s1<<endl<<endl;
            }
            p1--,p2--;
            num--;
        }
        cout<<ans.size();
        for(int i=0;i<ans.size();i++)
        {
            printf(" %d",ans[i]);
        }
        cout<<endl;
    }
    getchar();
    getchar();
}