CF 口胡笔记 2000Ct辑
¿ 如何 搞笑 高效做题 ?只需要口胡CF题就行啦！（从今天起口胡 CF 按照洛谷通过人数排序的题单
从 CF2000 Part 1 开始
目录导航：
[*]CF 2000Ct 辑
[*]CF 2100Ct 辑
CF24E XOR on Segment
[*]给定 \(n\) 个数的序列 \(a\)。\(m\) 次操作，操作有两种：
[*]求 \(\displaystyle\sum_{i=l}^r a_i\)。
[*]把 \(a_l\sim a_r\) 异或上 \(x\)。
[*]\(1\le n\le 10^5\)，\(1\le m\le 5\times 10^4\)，\(0\le a_i\le 10^6\)，\(1\le x\le 10^6\)。
思路：开 \(\log(A)\) 个线段树记录二进制下每一位是 \(0\) 还是 \(1\)。 \(A\) 代表值域。空间 \(T(2n\log(A))\) ，时间 \(T(n\log(n)\log(A))\)
CF1200E Compress Words
[*]Amugae 有 \(n\) 个单词，他想把这个 \(n\) 个单词变成一个句子，具体来说就是从左到右依次把两个单词合并成一个单词。合并两个单词的时候，要找到最大的 \(i(i\ge 0)\)，满足第一个单词的长度为 \(i\) 的后缀和第二个单词长度为 \(i\) 的前缀相等，然后把第二个单词第 \(i\) 位以后的部分接到第一个单词后面。输出最后那个单词。
不就是 kmp 裸题吗，过。
等等，我看题解好像有诈。我写一写代码
废了，写了四遍还没过
突然看到题解的一句话：
首先，这题要先注意题面。如果你把合并单词的过程理解成“单词与单词合并”，你就会被 test 4 卡掉。【调了很久才发现】
正确的理解方式是：“单词与合并完成的句子合并”哦哦哦哦哦哦原来是这样我
那复杂度不就变成 \(O(n^2)\) 了吗？寄。
哦，原来新串和原串 getnxt 的时候只用加入与新串长度相等的原串就行了，复杂度 \(T(2n)\)
展开代码#includeusing namespace std;#define ff(i,l,r) for(auto i=(l);(i)='a'&&ch='A'&&ch='0'&&ch
页:
[1]