Tokio Marine & Nichido Fire Insurance Programming Contest 2020 题解
ABC 之前做过，就不写了。
D - Knapsack Queries on a tree
题意
给定一个 \(N\) 个点的完全二叉树，每个点上有一个重量为 \(W_i\)，价值为 \(V_i\) 的物品。
\(Q\) 次询问，每次询问给定 \(v,L\)，求在 \(v\) 到根路径上的物品中选出若干个（可以为 \(0\) 个）重量和不超过 \(L\) 的物品的最大价值和。
\(N < 2^{18}, Q\le 10^5, L\le 10^5\)
题解
一个朴素 DP 是，用 \(f[i][j]\) 表示在 \(i\) 到根的路径上选出重量和不超过 \(j\) 的物品的最大价值和。
直接 DP 是 \(O(NL)\) 的，需要优化。
我们考虑只处理出前 \(9\) 层节点的 DP 数组。然后对于每个询问，暴力枚举最后不超过 \(9\) 个物品的选择状态即可。
时间复杂度 \(O(Q\sqrt{N})\)。
E - O(rand)
题意
有 \(N\) 个数 \(A_1,A_2,\ldots,A_N\)，求在其中选出 \(1\) 到 \(K\) 个满足以下条件的数的方案数：
- 选择的数的 AND 和为 \(S\)；
- 选择的数的 OR 和为 \(T\)。
\(N\le 50,A_i < 2^{18}\)
题解
一个朴素的 \(3^{18}\) 的容斥是，对于所有 \(S\) 为 \(0\)，\(T\) 为 \(1\) 的位，枚举是强制选 \(0\)、强制选 \(1\) 还是没有限制。
考虑优化，发现容斥系数只与有限制的位置数量有关，于是我们考虑枚举有限制的位置。然后我们再枚举一个数 \(A_i\) 强制选择，这样我们就可以确定每一个有限制的位是填 \(0\) 还是填 \(1\)。
统计出合法的数字数量，用组合数计算即可。
时间复杂度 \(O(2^{18}N)\)。
F - Triangles
题意
二维平面上有一个以 \((0,0)\) 为左下角，\((W,H)\) 为右上角的矩形。
你需要求满足以下条件的三角形数量：
- 顶点为格点；
- 三个顶点分别在矩形的三条不同的边上，且不能在矩形的顶点上；
- 三角形内部（不包括边和顶点）的格点数不超过 \(K\)。
\(W,H,K\le 10^5\)
题解
下面我们考虑计算三个点分别为 \((0,y),(x_1,0),(x_1+d,H)\ (0 < y < H, 0 < x_1 < x_1+d < W)\) 的三角形数量，其他情况类似。
由皮克定理，设三角形面积为 \(S\)，内部格点数为 \(i\)，边和顶点上格点数为 \(b\)，则有 \[2S=2i+b-2\]
对于该三角形，有 \(2S=x_1H+dy,b=\gcd(d,H)+\gcd(x_1+d,H-y)+\gcd(x_1,y)\)。
代入皮克定理的式子，得到
\[x_1H+dy=2i+\gcd(d,H)+\gcd(x_1+d,H-y)+\gcd(x_1,y)-2\]
显然当 \(x_1H+dy >3H+2K\) 时 \(i\le K\) 不可能成立，所以有 \(dy\le 3H+2K\)。于是我们可以考虑枚举 \(dy\)，这一部分时间复杂度为 \(O((H+K)\log (H+K))\)。
根据 \(i\le K\) 写出不等式并将只与 \(d,y\) 有关的项移到右边，得到
\[x_1H-\gcd(x_1+d,H-y)-\gcd(x_1,y)\le \gcd(d,H)+2K-2-dy\]
记右式的值为 \(R\)，若 \(x_1\le \frac{R}{H}\)，则一定成立；若 \(x_1\ge \frac{R}{H}+2\)，则一定不成立。所以我们只要判断满足 \(\frac{R}{H} < x_1 < \frac{R}{H}+2\) 的 \(x_1\) 是否成立即可。这样的 \(x_1\) 只有 \(O(1)\) 个，每次判断需要求 \(\gcd\)，复杂度为 \(O(\log (W+H))\)。
所以总复杂度为 \(O((W+H+K)\log (W+H+K)\log (W+H))\)。
