CF1715D 2+ doors
题意
有一个长度为 \(n\) 的整数数组 \(a\) ，但是他只会告诉你 \(n\) 的大小和 \(q\) 个要求，每个要求包括三个整数 \(i,j,x\) ，要求满足 \(a_i\mid a_j = x\)，其中 \(|\) 表示按位或运算
找到满足所有要求的字典序最小的数组 \(a\)
\(1 \le n \le 10^5\) , \(0 \le q \le 2 \cdot 10^5\)
分析
强制 \(1\) 为根，三种大情况：\(2\) 是 \(3\) 祖先，\(3\) 是 \(2\) 祖先，\(2\) 和 \(3\) 没有祖先关系、
有祖先关系的随便搞，其他情况就把 \(d12+d13\) 比 \(d23\) 多的部分搞成公共的。最后把多余的接到 \(1\) 上即可。
CF1707B Difference Array
题意
你有一个初始长度为 \(n\) 的有序数组 \(a\)（从小到大）。设 \(a\) 当前长度为 \(l\)，你要对 \(a\) 作差分，即令 \(b_i = a_{i+1} - a_i(1\le i < l)\)，然后将 \(b\) 数组从小到大排序，接着让 \(a_i = b_i(1 \le i < l)\)，并继续执行上述操作。
显然，每一次操作后 \(a\) 数组的长度都会减少 \(1\)；执行 \(n - 1\) 次操作之后，\(a\) 中只会剩下一个元素，
\(1 < n \le 10^5,0 \le a_i \le 5\times10^5\)。
分析
发现每次极差至少减少 \(n-1\)，于是单独处理 \(0\)，暴力即可。
CF1700D River Locks
题意
有 \(n\) 个容器，第 \(i\) 个容器容量为 \(v_i\) 升，可以容纳 \([0,v_i]\) 升的水。
满出去的水会将从容器 \(i\) 转移到容器 \(i+1\)，如果 \(i+1\) 也满了会转移得更远。满出最后一个容器的水会倒到河中。
现在要将所有容器填满。你可以选择一些容器注水，让这些容器每秒进入一升水。\(q\) 次询问，问最初所有容器都是空的，最少选择多少个容器注水使得 \(t_i\) 秒内能填满所有容器。
\(1\leq n,q\leq 2\times 10^5\)，\(1\leq v_i,t_i\leq 10^9\)。
分析
显然从左往右开。看似需要的水龙头数是 \(\lceil\frac{\sum v_i}{t}\rceil\)，但是有可能会前面没满后面就溢出了，又由于顺序开，所以每次填的都是一个前缀，因此只有开最后一个水龙头才会出现这种情况。考虑判无解，也就是求最少需要的时间，易得是 \(\max\{\lceil\frac{\sum v_j}{i}\rceil\}\)。
CF1702G1 Passable Paths (easy version)
题意
给定一棵树，问是否能通过一条简单路径（即在树上找一条路径且不重复走一条边），使其经过给定点集中的所有点。
\(1\leq n \leq 2\cdot10^5,1\leq q\leq 5\)
分析
容易发现当且仅当点集中的所有点都在同一条路径上才是 yes，随便判即可。
CF1701D Permutation Restoration
题意
有一个长度为 \(n\) ，由 \(1\) ~ \(n\) 构成的数组 \(a\) ，其中每个元素在 \(a\) 中出现且仅出现 \(1\) 次。
现在计算一个数组 \(b\) ，使得 \(b_i=\lfloor\frac{i}{a_i}\rfloor\) 。现在给出 \(b\) 数组，要求求出任意一组 \(a\) 。
注意：保证对于所给出的 \(b\) 至少有一组 \(a\) 与之对应。\(1 \le n \le 5×10^5,0 \le b_i \le n\)。
分析
容易发现每个 \(b_i\) 对应的合法 \(a_i\) 是一个区间，左端点排序后每次优先分配给右端点靠左的。
CF1689D Lena and Matrix
题意
\(t\) 组数据，每组给定一个由字符 W 或 B 组成的 \(n\times m\) 的矩阵。求这样一个点的坐标，满足其到图中任何一个 B 的最大曼哈顿距离最小。
若有多解，可任意输出一个。\(1\le t\le 10000,2\le n,m\le 1000,\sum nm\le 10^6\)
分析
曼哈顿距离转切比雪夫距离后直接做。
CF1704D Magical Array
题意
给定一个数组 \(b\)，长度为 \(n\)。
现选定 \(k\) 并构建数组 \(c_1,c_2,\dots,c_m\)，并且长度均为 \(n\)。
起初，对于任意的 \(i\in[1,m]\) 和 \(j\in[1,n]\) 有 \(c_{i_j}=b_j\)。
现有两种操作。
选定 \(i,j\) 使得 \(1< i< j< n\)。将 \(a_i\) 和 \(a_j\) 自减，将 \(a_{i-1}\) 和 \(a_{j+1}\) 自增。
选定 \(i,j\) 使得 \(1< i< j< n-1\)。将 \(a_i\) 和 \(a_j\) 自减，将 \(a_{i-1}\) 和 \(a_{j+2}\) 自增。
对 \(c_k\) 执行 \(x\) 次第二种操作。对其他的数组执行若干次（可能不同的次数）第一种操作。给出 \(c_1,c_2,\dots,c_m\)，求出 \(k\) 和 \(x\)。$ 3 \leq n \leq 10^5, 7 \leq m \leq 3 \cdot 10^5 $。
分析
构造哈希函数 \(h(a)=\sum i\cdot a_i\)，发现操作一不对哈希函数有贡献，操作二哈希函数自增，直接做即可。