- 14.3
- 维护 \(cur\), \(ans\) , \(dif = cur - ans\) 。
- 每次执行 \(cur = cur + a_i, \quad dif = dif + a_i\)。
- 如果 \(cur < 0\)，则
\(dif -= cur, \quad cur = 0\)。
- 如果 \(dif > 0\)，则 \(dif = 0\)。
- 考虑将所有数都表示成 \(\sum c_i \cdot 2^i\) 的形式，其中 \(c_i = 0, 1, -1\)。
- 则所有加法和减法操作均摊只需要执行 \(O(1)\) 次。使用 set 维护这几个数即可。
- vp 了第15场
- 15.1
- 15.2
- 首先很套路的是 将奇数位反转
- 然后我们可以发现最后一位一定要相同，并且每个前缀 \(x\) 串的连续段个数要大于等于 \(y\) 的连续段个数
- 故可以使用线段树进行维护
- 然后对着大样例虚空调试，发现大样例是错的/jk，交上去直接过了/jk
- 15.3
- 开始我的想法是先把式子转换成 \((\frac{sum-1}{x} + 1) \cdot x\) 的形式，其中 \(sum = \sum_{i} a_i\)
- 然后采用根号分治解决，时间复杂度是 \(\sqrt{\sum_{i}^{n} b_i} \cdot n\) 的，很明显不足以过掉此题
- P6150 很有意思的一道思维题（很显然我太蠢了没想出来（
- 很明显我们可以枚举根节点
- 我们考虑在叶节点 \(x\) 和它的父亲 \(u\) 的情况，如果 \(x\) 需要拨弄 \(d\) 次，且我们最终要回到 \(u\) 节点，则 \(u\) 也会拨弄 \(d\) 次这是必然的
- 故我们可以一直这样，则除根节点之外的所有节点都是 12了
- 若根节点为1或者12的话则是合法的（可以停留在一个儿子节点不回来
- P10136
- 很蠢地过了许久才发现可以使用抽屉原理(这也算一个新trick)
- 考虑任意四个数中一定会有一对数对于 \(L\) 同余，则 \(L\) 的因数有可能成为答案，故枚举即可
- https://www.luogu.com.cn/training/607752#problems 口胡进度推进至 p6146
