C 和 D 比较有意思.
A Hitachi String
人口普查.
B Nice Shopping
人口普查.
C ThREE
先把能填的数字都对 $3$ 取模,记 $1\sim n$ 的整数对 $3$ 取模后,有 $k_0$ 个 $0$ , $k_1$ 个 $1$ , $k_2$ 个 $2$ .
首先容易发现对于两个距离为 $3$ 的点 $x,y$ ,它们深度的奇偶性必定不同.
不妨假定深度为偶数的点有 $t_0$ 个,深度为奇数的点有 $t_1$ 个,并且 $t_0\le t_1$ ,否则只需交换 $t_0$ 和 $t_1$ .
- 若 $t_0\le k_0$ ,就可以给深度为偶数的点全部赋值为 $0$ ,这样奇偶性不同的点权值乘积必定为 $0$ .
- 若 $k_0<t_0,k_1\le t_0\le k_0+k_1$ ,可以将所有的 $1$ 都填给深度为偶数的点,剩下的深度为偶数的点填 $0$ ,这样对于奇偶性不同的点,只可能是 $(0,0),(0,2),(1,0),(1,2)$ 这几种权值组合,积与和中至少有一者为 $0$ .
因为 $k_0 +1\ge k_1$ ,所以不会出现 $k_0<t_0<k_1$ 的情况.
因为 $k_1\ge k_2,t_0\le t_1$ ,所以不会出现 $t_0>k_0+k_1$ 的情况.
于是就证明出了只会存在上述两种情况,那么我们总能通过对应方法构造出一组合法解.
D Manga Market
考虑如果在时刻 $t$ 在商店 $i$ 购买物品,结束后立即去商店 $j$ 购买物品 .
那么 $j$ 会因为在 $i$ 处等候而额外花费 $(a_i\cdot t +b_i+1)\cdot a_j$ 的时间.
如果我们将二者交换顺序,在时刻 $t$ 在 $j$ 购买,结束后立即去 $i$ 购买, $i$ 会额外花费 $(a_j\cdot t +b_j+1)\cdot a_i$ 的时间.
若先去 $i$ 比先去 $j$ 更优,就需要满足
$$
(a_i\cdot t +b_i+1)\cdot a_j\le (a_j\cdot t +b_j+1)\cdot a_i \\
(b_i+1)\cdot a_j \le (b_j+1)\cdot a_i
$$
可以发现 $i$ 是否比 $j$ 优与当前时刻 $t$ 无关.
于是可以先对所有商店排序,得到序列 $p$ ,那么我们实际去的商店按照时间先后形成的序列一定是 $p$ 的一个子序列.
考虑 dp, 设 $dp(i,j)$ 表示考虑了序列 $p$ 的前 $i$ 家商店,去了 $j$ 家商店最少用时,转移时枚举去不去第 $i$ 家商店.
这个 dp 的状态数是 $O(n^2)$ 的,无法直接通过,需要一些优化.
注意到如果没有 $a_i=0$ 的商店,花费的时间是随去的商店数目指数级增长的,即有效的 $j$ 只会有前 $O(\log T)$ 个.
而根据我们的排序方式, $a_i=0$ 的商店一定是排在 $a_i>0$ 的商店后面的.
于是可以对 $a_i>0$ 的所有商店做一次 dp ,就只会有 $O(n\log T)$ 个状态需要计算,设这样的商店共有 $k$ 个,
然后对于每个状态 $(j,dp(k,j))$ ,贪心地将 $a_i=0$ 的商店按照 $b_i$ 从小到大依次去一遍,直到全部取完或时间超出 $T$ .
只会有 $O(\log T)$ 个状态 $(j,dp(k,j))$ ,这部分的时间复杂度也是 $O(n\log T)$ .
再加上给 $n$ 个商店排序的复杂度,总时间复杂度为 $O(n\log n+n\log T)$ .
这份代码为了偷懒,用了 map 存储 dp 值, 复杂度多了一个 $O(\log \log T)$ .
要去掉也很简单,转移时记录最大的有效的 $j$ ,每次枚举 $j$ 时只枚举到当前上限就可以了.
E Odd Sum Rectangles
假定 $n\le m$ .
先考虑 $n=m$ 的情况,在构造 $(2^{n}-1)\times (2^n-1)$ 的矩阵时,先构造出 $(2^{n-1}-1)\times (2^{n-1}-1)$ 的矩阵.
把 $(2^{n-1}-1)\times (2^{n-1}-1)$ 的矩阵在 $(2^{n}-1)\times (2^n-1)$ 的矩阵的左上角,右上角,左下角,右下角各放一个.
这样就只剩下第 $2^{n-1}$ 行和第 $2^{n-1}$ 列没有填,在 $(2^{n-1},2^{n-1})$ 这个位置填 $1$ ,其他位置填 $0$ .
用归纳法可以证明这样构造的正确性,思路是证明每一次矩阵的权值都达到了 $4^{n-1}+2^{n-1}\cdot (2^n-1)$ 这个上界.
若 $n> m$ ,就先构造一个 $(2^{n}-1)\times (2^n-1)$ 的矩阵,然后只保留前 $2^{m}-1$ 列就可以了.