2020-2021:teams:manespace:noi2011_阿狸的打字机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:noi2011_阿狸的打字机 [2020/05/09 21:47] iuiou 创建 |
2020-2021:teams:manespace:noi2011_阿狸的打字机 [2020/05/09 21:49] (当前版本) iuiou [引自洛谷] |
||
|---|---|---|---|
| 行 18: | 行 18: | ||
| | | ||
| 我们把纸上打印出来的字符串从 1 开始顺序编号，一直到 n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 (x,y)(其中 1≤x,y≤n,1≤x,y≤n)，打字机会显示第 x 个打印的字符串在第 y 个打印的字符串中出现了多少次。 | 我们把纸上打印出来的字符串从 1 开始顺序编号，一直到 n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 (x,y)(其中 1≤x,y≤n,1≤x,y≤n)，打字机会显示第 x 个打印的字符串在第 y 个打印的字符串中出现了多少次。 | ||
| + | |||
| + | ===== 涉及知识点 ===== | ||
| + | |||
| + | ac自动机，dfs序，树状数组，树上差分 | ||
| ===== 分析 ===== | ===== 分析 ===== | ||
| 行 26: | 行 30: | ||
| 1 不接受任何暴力，一不小心就t qaq | 1 不接受任何暴力，一不小心就t qaq | ||
| + | |||
| 2 trie树如果多加了一个0号节点，BIT维护的序列就要+1(被坑死了555) | 2 trie树如果多加了一个0号节点，BIT维护的序列就要+1(被坑死了555) | ||
| + | |||
| 3 这tm太难了，<del>不愧是NOI</del>，怎么想得到这么多技巧和数据结构…… | 3 这tm太难了，<del>不愧是NOI</del>，怎么想得到这么多技巧和数据结构…… | ||
2020-2021/teams/manespace/noi2011_阿狸的打字机.1589032068.txt.gz · 最后更改: 2020/05/09 21:47 由 iuiou
