7.21 Day1 贪心构造交互思维
第一天上来就吃*，没绷住
T1:Minimum OR Path
题意：一个长度为 \(n\) 的数组 \(a\) ,在位置 \(i\) 时可以移动到 \(j\) (\(j \in [i,i+a_i]\)),现在从 \(1\) 移动到 \(n\) ,一条路径的代价为经过的位置的 \(a\) 值按位或，求最小代价。
题解：对于这种位运算的题目，首先想到拆位，这道题求最小值，从高位向低位考虑，因为在钦定不选高位的情况下无法到达那就必须得选，否则一定可以不选。
T2:Another Array Problem
题意：一个长度为 \(n\) 的数组，每次操作选择两端点 \(i,j (i<j)\) 将 \(a_{[i,j]}\) 替换为 \(|a_i-a_j|\),求在任意次操作后数组求和的最大值。
题解：挺有意思的，类似构造，有一个组合构造，对同一个区间操作两次后，会得到一段 \(0\) ,这个时候可以直接赋值，所以 \(n \ge 4\) 时整个数组可以赋成最大值，而 \(n \le 3\) 时情况少得可怜，直接取 \(max\) 即可。
T3：Make it Zero
题意：有一个长度为 \(n\) 的数组 \(a\) ,每次操作要求选定一个长度为 \(n\) 的数组 \(b\) ,要求数组存在一个 \(i\) 令 \(b_{1...i}\) 的前缀和和 \(b_{i+1...n}\) 的后缀和相等，然后 \(a_i = a_i - b_i\) 最终要求将 \(a\) 数组全部变成 \(0\) 。（限制最多17次操作）
题解：比较简单的构造。首先考虑一下无解，每次减去的 \(b\) 数组总和为偶数，所以若原数组 \(a\) 总和为奇数则无解，同时若有一个数大于 \(\frac{sum}{2}\) 同样无解（显然无法配合）。至于剩下的构造很简单，次数其实最多为 \(2\) :显然有 \(1\) 就能构造好的，否则先找到一个最靠右的分界点满足前缀和小于 \(\frac{sum}{2}\) 此时后面剩的总和仍然是个偶数，显然的是此时的分界点刚好可以取到剩余量的一半，剩下的在后面拼凑即可。