2020-2021:teams:hotpot:codeforces658div2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:codeforces658div2 [2020/07/22 12:53]
misakatao 创建
+++ 2020-2021:teams:hotpot:codeforces658div2 [2020/07/22 14:04] (当前版本)
喝西北风
@@ 行 1: / 行 1: @@
-(占位)
+=====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]里没出现过的数

2020-2021/teams/hotpot/codeforces658div2.1595393611.txt.gz · 最后更改: 2020/07/22 12:53 由 misakatao