10 24（+第14场补题）

• 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