Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 题解
A - Hitachi String
题意
判断一个字符串 \(S\) 是否由若干个 hi 拼接而成。
\(|S|\le 10\)
题解
条件为：
- \(n\) 是偶数；
- 奇数位为
h； - 偶数位为
i。
时间复杂度 \(O(|S|)\)。
B - Nice Shopping
题意
有 \(A\) 种 A 商品，第 \(i\) 种价格为 \(a_i\)；有 \(B\) 种 B 商品，第 \(i\) 种价格为 \(b_i\)。
有 \(M\) 张优惠券，第 \(i\) 张优惠券是同时买 A 商品的第 \(x_i\) 种和 B 商品的第 \(y_i\) 种时可以优惠 \(c_i\) 元。
你需要买恰好一种 A 商品和恰好一种 B 商品，求在最多只能用一张优惠券时的最小花费。
\(A,B,C\le 10^5\)
题解
有两种情况：
- 不使用优惠券，则花费为 \(\min\{a_i\}+\min\{b_i\}\)；
- 使用优惠券，则花费为 \(\min \{a_{x_i}+b_{y_i}-c_i\}\)。
两种情况取 \(\min\) 即可。
时间复杂度 \(O(A+B+M)\)。
C - ThREE
题意
给定一棵 \(n\) 个点的树，构造一个排列 \(p\) 满足：
- 对于所有 \(i\) 到 \(j\) 的简单路径边数为 \(3\) 的 \((i,j)\)，满足 \(p_ip_j\) 和 \(p_i+p_j\) 中至少有一个是 \(3\) 的倍数。
\(n\le 2\times 10^5\)
题解
假设 \(n\) 为 \(3\) 的倍数。其他情况类似。
相当于我们要给每个点赋 \(0,1,2\) 中的一个数，每个数都恰好出现 \(\frac{n}{3}\) 次。
首先我们可以从任意点开始 DFS，将深度为奇数的点填 \(1\)，深度为偶数的点填 \(2\)。显然这样已经能满足题目中的条件。
考虑如何满足出现次数的条件。记填 \(1\) 和 \(2\) 的数量分别为 \(c_1,c_2\)，那么分两种情况：
- \(c_1,c_2\ge \frac{n}{3}\)。此时只要将多余的 \(1,2\) 填成 \(0\) 即可。
- \(\exists i\in \{1,2\},c_i < \frac{n}{3}\)。此时将 \(i\) 全部替换成 \(3\)，剩下的节点任意填即可。
时间复杂度 \(O(n)\)。
D - Manga Market
题意
有 \(n\) 个商店，从时刻 \(0\) 开始，每次你可以花费 \(1\) 个单位的时间走到任意一个商店。
若你在时刻 \(t\) 到达商店 \(i\) 并在商店 \(i\) 购物，那么你需要花费 \(a_i\times t+b_i\) 单位的时间。
所有商店会在时刻 \(T+0.5\) 关门，也就是说，如果你走到某个商店时的时刻加上需要花费的时间大于 \(T\)，那么你就无法在该商店购物。
每个商店只能购物一次。
求最多可以在多少商店购物。
\(n\le 2\times 10^5,T\le 10^9\)
题解
首先我们可以把 \(b_i\) 加上 \(a_i+1\)，这样就可以认为走路不需要时间。
然后我们可以把 \(a_i\) 加上 \(1\)，这样 \(a_it+b_i\) 就是购物结束的时刻。
假若我们依次在 \(i_1,i_2,\ldots,i_k\) 这些商店购物，这是在这些商店购物的最优顺序当且仅当对于所有 \(1\le j < k\) 都满足 \[b_{i_j}a_{i_{j+1}}\prod_{l=j+2}^{k}a_{i_l}+b_{i_{j+1}}\prod_{l=j+2}^{k}a_{i_l}\le b_{i_{j+1}}a_{i_j}\prod_{l=j+2}^{k}a_{i_l}+b_{i_j}\prod_{l=j+2}^{k}a_{i_l}\] 化简得到 \[\frac{b_{i_j}}{a_{i_j}-1}\le \frac{b_{i_{j+1}}}{a_{i_{j+1}}-1}\]
所以我们可以首先把原序列按这个式子排序。
然后我们可以 DP。用 \(f_{i,j}\) 表示前 \(i\) 个商店，去了 \(j\) 个的最小时间。
注意到若忽略 \(a_i=1\) 的商店，那么 \(j\) 只有 \(O(\log T)\) 个。
而 \(a_i=1\) 的商店一定排在最后，可以最后贪心按 \(b_i\) 从小到大依次购物。
所以时间复杂度 \(O(n\log T)\)。
E - Odd Sum Rectangles
题意
构造一个 \((2^n-1)\times (2^m-1)\) 的 01 矩阵，使得和为奇数的连续子矩阵数量最多。
\(n,m\le 10\)
题解
假设 \(n\ge m\)。令 \(H=2^n,W=2^m\)。考虑枚举 \(1\le j_1\le j_2< W\)，令 \(f(i)=S(1,i,j_1,j_2)\ (0\le i< H)\)。那么和为奇数的子矩阵数量为 \(f(i)\) 中 \(0\) 的数量乘 \(1\) 的数量。于是我们可以得到数量的上界为 \(\frac{H^2}{4}\times \frac{W(W-1)}{2}\)。
接下来我们证明这个上界是可以达到的。
假设 \(n=m\)。我们考虑用归纳证明。
当 \(n=1\) 时，我们只需要构造一个元素为 \(1\) 的 \(1\times 1\) 矩阵即可。
假设我们已经构造出了 \(n=k\) 的矩阵，我们可以按如下方式构造一个 \((2^{k+1}-1)\times (2^{k+1}-1)\) 的矩阵：
- 左上角、左下角、右上角、右下角分别用 \(n=k\) 的矩阵填充。
- 第 \(2^k\) 行 \(2^k\) 列填 \(1\)。
- 其他位置填 \(0\)。
以没有跨过第 \(2^k\) 列的两列作为 \(j_1,j_2\) 时证明比较容易。而对于跨过第 \(2^k\) 列的两列，由于构造的矩阵具有对称性，我们可以转化成第 \(2^k\) 列加上没有跨过第 \(2^k\) 列的两列之间的部分。这一部分证明也比较容易。
\(n>m\) 的情况先构造 \((2^n-1)\times (2^n-1)\) 再取前 \(2^m-1\) 列即可。因为我们证明了任意两列之间都能卡到上界，所以这样构造一定仍然能够卡到上界。
时间复杂度 \(O(2^{2\max(n,m)})\)。
F - Preserve Diameter
题意
给定一棵 \(n\) 个点的树 \(G\)。求在树 \(G\) 中加入若干条边得到的满足以下条件的图 \(H\) 的数量：
- 不存在重边和自环。
- \(H\) 的直径与 \(G\) 相等。
- 对于所有在 \(H\) 中没有直接的边相连的点对 \((u,v)\ (u\ne v)\)，满足加入边 \((u,v)\) 后会使直径长度减小。
对 \(998244353\) 取模。
\(n\le 2\times 10^5\)
题解
首先不难发现 \(H\) 的直径是唯一的，否则一定可以继续加入边。假设这条唯一的直径两个端点为 \(x,y\)。
我们考虑以 \(x\) 为根建立 BFS 树，令 \(dis_i\) 为 \(x\) 到 \(i\) 的最短路长度，那么两个点 \(u,v\) 在 \(H\) 中有边当且仅当 \(|dis_u-dis_v|\le 1\)。
直接对 \(dis_i\) 计数由于需要确定 \(x\) 而不好计数。考虑继续转化。
假设 \(G\) 的直径长度为 \(L\)。我们首先考虑 \(L\) 是偶数的情况，此时我们可以得到直径的中点 \(c\)。
可以发现 \(x,y\) 在 \(G\) 上的路径一定经过 \(c\)，这是因为 \(x,y\) 一定也是 \(G\) 的直径端点，而树上任意一条直径一定都经过直径中点。
于是我们考虑以 \(c\) 为根，给每个点赋一个标号 \(d_i\)，满足：
- \(d_c=0\)。
- 恰好存在一个点 \(x\) 满足 \(d_x=-\frac{L}{2}\)。
- 恰好存在一个点 \(y\) 满足 \(d_y=\frac{L}{2}\)。
- 对于在 \(G\) 中有边的点对 \((u,v)\)，满足 \(|d_u-d_v|\le 1\)。
可以发现一个合法的 \(H\) 一定恰好对应两种满足以上条件的标号方案。
于是我们可以 DP，记以 \(c\) 到 \(u\) 的距离为 \(dep_u\)，则我们用 \(f_{u,i,j}\) 表示对 \(u\) 的子树进行标号，\(d_v-d_u=\frac{L}{2}-dep_u\) 的点 \(v\) 数量为 \(i\)，\(d_u-d_v=\frac{L}{2}-dep_u\) 的点 \(v\) 数量为 \(j\) 时的方案数。
注意 \(i,j\) 可以与 \(2\) 取 \(\min\)。
\(L\) 为奇数时类似，只需要将直径中间的边断开后对两边分别 DP 后合并即可。
时间复杂度 \(O(n)\)。
