2020-2021:teams:farmer_john:2020.7.27
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020.7.27 [2020/08/02 15:45] jjleo [题解] |
2020-2021:teams:farmer_john:2020.7.27 [2020/08/02 15:46] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 22: | 行 22: | ||
| 我们设$t$为形如$abcd \cdots$的字符串，并保证任何时刻两字符串均满足$s=tu,p=t$，其中$u$可为空。显然$n=1,2$的解满足该条件。\\ | 我们设$t$为形如$abcd \cdots$的字符串，并保证任何时刻两字符串均满足$s=tu,p=t$，其中$u$可为空。显然$n=1,2$的解满足该条件。\\ | ||
| 设$t$尾部字符的下一个字母为$x$。\\ | 设$t$尾部字符的下一个字母为$x$。\\ | ||
| - | 考虑$n->2n+1$的变换，，$s=txuxx,p=tx$即满足条件，其中$tx$贡献一个子序列，而$tu$中有$n$个$t$的子序列，因此$tuxx$贡献两个子序列。\\ | + | 考虑$n->2n+1$的变换，，$s=txuxx,p=tx$即满足条件，其中$tx$贡献一个子序列，而$tu$中有$n$个$t$的子序列，因此$tuxx$贡献$2n$个子序列。\\ |
| - | 同理有$n->2n+2$的变换，，$s=txxuxx,p=tx$，证明同上。 | + | 同理有$n->2n+2$的变换，，$s=txxuxx,p=tx$，证明同上。\\ |
| - | 根据这个变换以$n=1$或$n=2$为起点，构造出符合条件的长度为$O(\log n)$的字符串。 | + | 根据这个变换即可以$n=1$或$n=2$为起点，构造出符合条件的长度为$O(\log n)$的字符串。 |
| =====CF Fake News (hard)===== | =====CF Fake News (hard)===== | ||
| ====题意==== | ====题意==== | ||
2020-2021/teams/farmer_john/2020.7.27.1596354307.txt.gz · 最后更改: 2020/08/02 15:45 由 jjleo
