=====A - Common Subsequence=====

====问题描述====

给定两个序列$\{a_n\}$，$\{b_m\}$，求一个最小公共子序列

====数据范围====

$n,m\le 1000$

====解题思路====

如果存在$a_i=b_j$，则输出这个，否则不存在

=====B - Sequential Nim=====

====问题描述====

n堆石子排成一列，第i堆有$a_i$个。两人轮流，从最前面的一堆中拿任意个。问谁必胜。

====数据范围====

$n\le10^5$

====解题思路====

dp[i]表示从第i堆棋子开始拿的胜负结果。显然dp[n]为先手胜。若dp[i+1]为先手胜，且a[i]=1，则dp[i]为后手胜，否择dp[i]为先手胜。最后看dp[1]即可

=====C - Prefix Slip=====

====问题描述====

现有长度为n的01序列a,b。每次可以选a的一个前缀，将这个前缀的01反转，位置翻转。构造一个使a变成b的方案

====数据范围====

$n\le10^5$

====解题思路====

从最后一位开始考虑。如果$a[n]\neq b[n]$，则若$a[1]\neq b[n]$，对a前n位做一次操作，使得a[n]=b[n]；若$a[1]=b[n]$，则先对第一位做一次操作，再对前n为做一次操作。暴力维护这个操作是$O(n^2)$的，可以记一个first，一个last和一个反转了多少次。时间复杂度O(n)。

=====D - Unmerge=====

====问题描述====

给定一个2n的排列，问是否是两个长为n的序列的归并。

====数据范围====

$n\le 2000$

====解题思路====

可以证明，对原序列中的第一个数，下一个大于它的数之前的数，一定都和他在同一个序列中。用这种方法，可以将原序列拆成若干子串，每个子串一定在同一序列中。最终只需要看是否存在若干个子串，其长度之和等于n。这个直接dp就行了。时间复杂度$O(n^2)$

=====E - Mastermind=====

====问题描述====

给定一个长度为n的数列a，每个数是[1,n+1]的整数，两个正整数x,y。构造一个长度为n，每个数都是[1,n+1]的整数的数列b，使得a[i]=b[i]有x组解，改变a的顺序，a[i]=b[i]至多有y组解。

====数据范围====

$n\le10^5$

====解决方案====

显然，我们希望y-x个数中出现次数最多的尽量小。
看每个数在a中出现的次数。每次找到出现次数最多的数，选择一个位置，让其贡献x，并把出现次数减1。解决了x的问题，然后解决y-x的问题。将剩余的里出现次数最多的那个往第二多的地方覆盖，维护一个循环链表。覆盖完后剩余的标[1,n+1]里没出现过的数