Codeforces Round #110 (Div. 2)

2024-08-25 10:01:32

Codeforces Round #110 (Div. 2)

C. Message

题意

给两个长度不超过2000的字符串\(s,u\)，仅由小写字母构成。
找出\(s\)的一个子串\(t\)，通过3种操作变换成字符串\(u\):

在首或尾添加一个字符;
删除首或尾的一个字符;
改变某个位置的字符。

求最小的操作步数。

思路

因为删除、插入的代价和修改的代价一样，显然找出和\(u\)长度一样的子串\(t\)可以求得最小代价。
显然\(u\)可以只匹配\(s\)的一个前缀或后缀，可以通过在\(s\)首或尾添加非字母字符。

代码

C. Message

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\)可能是凶手，也可能不是凶手时，就无法判断嫌疑人的回答是否撒谎。

代码

D. Suspects

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

代码

E. Cipher

最新文章

热门文章