好久没做了,今天来写一下
以前周赛的题
6.19
https://codeforces.com/contest/602/submission/211098125
6.20
枚举拿了几次左边的数,然后贪心的交替取左边右边直到只能左左或右右
https://codeforces.com/contest/354/submission/211099647
6.21
有个结论题目的操作相当于右移动x位
假设有c个操作能让s=t
如果已经s=t了,那么就有c-1个不同操作继续让s=t
假设c个操作分别是 a b c d位能让s=t
为什么呢,假设右移a位了让s=t了,那么下次只要右移b-a,c-a,c-d位也同样能保持一样,但不能移动a位了,否则就又把他翻转回去了
所以有效操作是c-1
设方程等于前i次操作让s= or != t的方案,然后状态dp就行
https://codeforces.com/contest/176/submission/211102915
6.22
dp
处理前i件衣服的最小开始处理i的时间
第i件衣服要同时满足三个条件
第一个条件:只有na个物品,所以最快是i-na开始处理第i件
第二个条件:只有nb个物品,所以最快也要等到i-nb个才能开始处理
第三个同上
因为要同时满足所以取最大值
https://codeforces.com/contest/452/submission/211104355
6.23
DP:
设f[i]为前i个字母没有字串的最小删除次数,g[i]是删除次数的方案数
首先字符串哈希可以O(1)查询两个字符串是否相等
如果当前以i结尾的字符串不是t那么直接f[i]=f[i-1],g[i]=g[i-1]继承前面的就行
如果相等了,那么就要删除了
问题来了
删除只能删除i-m+1到i的吗
不一定吧比如 ccccccccababa t=aba
当前i是最后一个字母,它不仅可以删除n-2到n的,也可以删除n-3到n-5的变成ccccccccba同样也是一个合法转移
那么还有一个问题,那个具体的j是啥范围
i-2m+2到i-m+1,因为只要在这范围删除一个字符串等于t的,那么以i结尾的字符串肯定会至少少掉一个字符导致不足以满足t的长度
https://codeforces.com/contest/1729/submission/211106883