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的方案数即可。
代码