Codeforces Round #110 (Div. 2)
C. Message
题意
- 给两个长度不超过2000的字符串(s,u)，仅由小写字母构成。
- 找出(s)的一个子串(t)，通过3种操作变换成字符串(u):
- 在首或尾添加一个字符;
- 删除首或尾的一个字符;
- 改变某个位置的字符。
- 求最小的操作步数。
思路
- 因为删除、插入的代价和修改的代价一样，显然找出和(u)长度一样的子串(t)可以求得最小代价。
- 显然(u)可以只匹配(s)的一个前缀或后缀，可以通过在(s)首或尾添加非字母字符。
代码
D. Suspects
题意
- 有(N(N le 10^5))个嫌疑人，其中一个是凶手。
- 每个人会有一个回答（(+a_i或-a_i)），分别表示(i)认为(a_i)是凶手和不是凶手。
- 已知全部回答中只有(m)个回答是真的，其余都是假的。
- 对于每个回答，判定嫌疑人是否在说谎，输出(Truth)或(Lie)，如果无法判断，则输出(Not defined)。
思路
- 判断一个人是否是凶手：统计认为(i)是凶手的数量(c[i])，以及认为(i)不是凶手的数量(nc[i])，则为真的回答数=$$c[i]-nc[i]+sum_{j=1}^{n}{nc[j]}$$
- 假定(i)是凶手，则([1, i))和((i, n])的人不是凶手。维护(L)的最大值，(R)的最小值，使得([1, L))和((R, n])的人不是凶手。
- 当(a_i)可能是凶手，也可能不是凶手时，就无法判断嫌疑人的回答是否撒谎。
代码
E. Cipher
题意
- 给长度不超过100的字符串(s)。
- 有两种操作，每次操作选择一个位置(p(1 le p lt |s|))：
- (++s_p, --s_{p+1})
- (--s_p, ++s_{p+1})
- 经过若干次操作，变成了串(t)，求不同的串(t)的数量。
思路
- 认真想一下的话，可以发现串的总和是不变的，两种操作想当于把1扔到相邻的位置上。
- 那么用(f[i][j])表示i个字符组成和为j的方案数即可。
代码