题目传送门：Codeforces 1572
B Xor of 3
先说一下自己想的不完整的思路。发现每一次操作都不会改变1的个数的奇偶性，即\(0,2\rightarrow 0\)或\(1,3\rightarrow 3\)，所以显然的一个无解判断就是，若1的个数为奇数则无解。
考虑一个极大的1连通块，若它的大小为偶数，那么一定可以通过这个连通块旁边的0来把整个连通块都变成0，对于单个的1，也可以通过两次操作使1向后挪两位。所以，对于两端存在偶数大小连通块的情况，已经有了解法。然而这个解法显然不能适用于所有情况。
考虑正解，对于\(n\)为奇数的情况，如此操作一定可以：\(1,3,\cdots,n-2,n-4,n-6,\cdots,1\)。
证明：因为每次操作\(i\)时，一定可以保证\(i\)之前的1的个数为偶数，而由于总数是偶数，所以在操作\(n-2\)时一定可以使后三位变成0，依次回推即可证明。
对于\(n\)为偶数的情况，考虑将其转化成奇数（这一步很关键且没有想到），找出某一个奇数长度的前缀\([1,p]\)使得前缀1的个数为偶数，就转化成了奇数的情况，对于后半部分，长度也是奇数，1的个数也为偶数，类似操作即可。如果未找到此前缀可以将原串翻转，若还未找到则无解。
Submission
C Paint
首先有一个显然的观察，若要将\([a,b,a]\)染成统一颜色，\([a,a,a]\)要比\([a,b,b]\rightarrow [a,a,a]\)节省1个步骤。
想到区间DP，设\(dp[i][j]\)表示将\([i,j]\)染成统一颜色的最大节省步骤数，可以发现一个区间想要次数尽量少，一定是染成其两端的颜色更优，且染成任意一端的颜色的步骤数应该是相同的。由此转移就是
\(dp[i][j]=\max(dp[i+1][j],\max(1+dp[i+1][k-1]+dp[k][j])\ a_k=a_i )\)
前者表示不节省，后者表示因为\(a_i=a_k\)，所以可以将\([k,j]\)全染成\(a_k\)然后就可以利用上面的观察，发现可以多节省一个步骤。
最终答案就是\(n-1-dp[1][n]\)，时间复杂度\(\mathcal O(20n^2)\)。
Submission