Codeforces Round 810 (Div. 2)

Rain

算法本质

思维、数据结构

题目大意（抽象）

在一维数轴上，有n个大块从天而降，类似于俄罗斯方块，每个大块都是正直角三角形且长边平行数轴。
现在假设第i个大块不存在，检查最后图形是否最高高度超过m。

n <= 2e5
方块位置、高度 <= 1e9

思路推演

稍加推理即可发现，最高高度一定出现于某个三角形的位置。
尝试直接求解发现困难重重，但是可以先求解出n个三角形的形状后尝试检查挪去是否可行。

求出n个三角形之后的形状相对简单，朴素的根据位置从左向右贪心即可，但是写起来稍微有点复杂。
这里介绍一个更巧妙的方法：

要想n个三角形形状能够求解，必须一定程度上规则。
玩家最后想要的是每个点的高度数组，这个数组的导数即每个点的斜率数组，继续求导即每个点的斜率加速度数组。
可以发现，每个三角形，其实只改变3个点的斜率加速度，随后即可求得。

接下来思考如果减少某个三角形，会导致什么样的结果。
定义位置p[]、初始高度h[]、n个三角形后的高度v[]。
如果挪走i，考虑j的变化，先假设i<j（这里是按位置排序的）：

• 第j个三角形高度会变成：$v_j - (h_i - (p_j - p_i))$
• 最后希望这个值≤m：$v_j + p_j - m ≤ h_i + p_i$
• 最后处理$v_j + p_j - m$的最大值即可

左侧同理。

这里注意有一个优化写法。
本身朴素来讲，需要用二分检查第i个三角形覆盖的范围，然后分别考虑覆盖点和非覆盖的点。
我们考虑处理最大值的时候，其实仅需要检查v[j] > m的情况，在v[j] > m的情况中，j点不受i点的影响时，v[j]+p[j]-m > h[i]+p[i]和v[j] > m具有同等效力，所以可以直接判断而不用分成覆盖点和不覆盖点的情况。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

XOR Triangle

算法本质

思维、数位dp

题目大意

给定一个二进制上限值n，计数三元组(a, b, c)，其a⊕b、a⊕c、b⊕c构成非退化三角形。

思路推演

显然，这是一个数位dp。
由于上限的限制，必须人为设定一个最大值c。

还需要解决的一个问题是，其游戏规则后的本质。
设a'=b⊕c、b'=a⊕c、c'=a⊕b

模拟+思考后可以发现，拆位来看：

• a b c都是0或1
  a' b' c'全0
• 其他
  a' b' c'存在2个1

而且这个部分是十分均匀的，其中a' b' c'存在2个1的情况有三种：

• 0 1 1
  由(0 1 1)和(1 0 0)转移而来
• 1 0 1
  由(1 0 1)和(0 1 0)转移而来
• 1 1 0
  由(1 1 0)和(0 0 1)转移而来

当a b c中的二进制位有以上三种情况，则这个三元组必然可行，然后开始吃屎。
注意借鉴这个题：https://www.luogu.com.cn/problem/P8766

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。