2020/07/19 -- 2020/07/25 周报

CF 1381A1 Prefix Flip (Easy Version)

• 分类：思维
• 题意：给定一个01字符串，每次可以选择一个$x$，然后操作。操作方法为把该字符串的$x$前缀全部反转（0变成1, 1变成0），然后翻转（首尾交换）。目标是使该字符串变成另外一个01字符串。要求给出翻转方案。字符串的长度为$n（n \leq 1000）$，操作次数不超过$3n$。
• 思路：很明显是要从后往前满足。考虑第$i$个位置，如果已经一样了就可以不用管，如果不一样那么它将会由第一个位置得到。所以如果第一个位置和当前一样，首先要操作前缀1使得第一个和点前$i$的不一样，然后再操作前缀$i$就可以满足$i$了。

CF 1382D Unmerge

• 分类：dp 背包
• 简要题意： 询问是否可以将原序列分成两个长度相等的序列（相对顺序不变），使得按照归并排序里的merge操作过后，还是原序列。
• 解法： 依次寻找当先序列中的最大数，记录其到结尾的长度，并截断。最后转换成背包问题，判断是否存在一些长度的和恰好为n。

Clam and Fish

分类：思维

题目大意：有$n$个笼子，里面可能有（1）空（2）蛤蜊*1（3）鱼*1（4）鱼*1和蛤蜊*1。有四种操作：（1）把蛤蜊做成饲料供后边的笼子来使用（2）用饲料捕捉鱼（3）如果笼子有鱼，可直接捕捉鱼（4）什么都不做。问最多可以捕捉多少鱼？

思路：题目可能比较长，但其实矛盾点就是在蛤蜊*1的笼子应该是拿去作饲料还是拿去捕捉鱼。这里有两种解法。

比赛的时候我使用倒序读取，need记录目前所需的饲料。碰到空笼子则need++，碰到有蛤蜊的笼子分两种情况（1）need==0时用于捕捉鱼（2）need!=0时用于做饲料。有鱼的笼子全部捉鱼即可。

第二种是顺序读取，贪心把所有的蛤蜊做成饲料，最后把剩下的饲料/2，一半用于做饲料，一半用于捉鱼。

无

* CF 658

无