2020-2021:teams:farmer_john:2020.7.27
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020.7.27 [2020/08/02 15:25] jjleo [题解] |
2020-2021:teams:farmer_john:2020.7.27 [2020/08/02 15:46] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| =====CF Marmots (easy)===== | =====CF Marmots (easy)===== | ||
| ====题意==== | ====题意==== | ||
| + | 给出$250$个点，问符合随即均匀分布还是泊松分布。 | ||
| ====题解==== | ====题解==== | ||
| + | ？？？ | ||
| =====CF Marmots (medium)===== | =====CF Marmots (medium)===== | ||
| ====题意==== | ====题意==== | ||
| + | 求出简单版本中两种分布对应的参数。 | ||
| ====题解==== | ====题解==== | ||
| + | ？？？ | ||
| =====CF Fake News (medium)===== | =====CF Fake News (medium)===== | ||
| ====题意==== | ====题意==== | ||
| + | 构造两个字符串$s,p$，满足$s$有恰好$n$个子序列等于$p$，要求两者长度均不超过$200$。$(n \le 10^6)$ | ||
| ====题解==== | ====题解==== | ||
| + | 当$n=1$时，$s=a,p=a$满足条件，当$n=2$时，$s=abb,p=ab$满足条件。\\ | ||
| + | 我们设$t$为形如$abcd \cdots$的字符串，并保证任何时刻两字符串均满足$s=tu,p=t$，其中$u$可为空。显然$n=1,2$的解满足该条件。\\ | ||
| + | 设$t$尾部字符的下一个字母为$x$。\\ | ||
| + | 考虑$n->2n+1$的变换，，$s=txuxx,p=tx$即满足条件，其中$tx$贡献一个子序列，而$tu$中有$n$个$t$的子序列，因此$tuxx$贡献$2n$个子序列。\\ | ||
| + | 同理有$n->2n+2$的变换，，$s=txxuxx,p=tx$，证明同上。\\ | ||
| + | 根据这个变换即可以$n=1$或$n=2$为起点，构造出符合条件的长度为$O(\log n)$的字符串。 | ||
| =====CF Fake News (hard)===== | =====CF Fake News (hard)===== | ||
| ====题意==== | ====题意==== | ||
| + | 给定一个字符串，问所有本质不同子串出现次数的平方和。 | ||
| ====题解==== | ====题解==== | ||
| + | 后缀自动机模板题。 | ||
| =====CF Send the Fool Further! (medium)===== | =====CF Send the Fool Further! (medium)===== | ||
| ====题意==== | ====题意==== | ||
2020-2021/teams/farmer_john/2020.7.27.1596353134.txt.gz · 最后更改: 2020/08/02 15:25 由 jjleo
