Contest Info

practice link

Solutions

A. Ilya and a Colorful Walk

签到题。

B. Alyona and a Narrow Fridge

签到题。

C. Ramesses and Corner Inversion

签到题。

D. Frets On Fire

签到题。

E. Pavel and Triangles

签到题。

F. Niyaz and Small Degrees

题目大意：给一棵 \(n\) 个点的树，边有边权。对每个 \(x=0,\cdots,n-1\)，求出使得每个点度数不超过 \(x\)，至少要删掉多少条边。

题解：设 \(dp[u][0/1]\) 表示在 \(u\) 的子树中，除了 \(u\) 之外的点度数都不超过 \(x\)，\(u\) 的度数不超过 \(x/x+1\) 时的最小代价。转移时，以 \(dp[u][0]\) 为例，先假设所有的 \(v\) 都取 \(dp[v][0]\)，但是由于 \(u\) 的度数不能超过 \(x\)，因此需要删掉 \(deg[u]-x\) 条边，那么这些点可以优化成 \(dp[v][1]\)，但是要加上 \(w_{uv}\) 的代价，从而贡献是 \(dp[v][1]-dp[v][0]+w_{uv}\)。我们选出贡献最小的 \(deg[u]-x\) 个即可。复杂度 \(\mathcal{O}(n\log n)\)。

对于每个 \(x\)，注意到度小于等于 \(x\) 的点一定满足要求。这样对于所有 \(x\)，需要参与 \(dp\) 的点只有 \(\mathcal{O}(n)\) 个。我们只需要用一个堆维护每个度大于 \(x\) 的点连出的所有度小于等于 \(x\) 的边的边权即可，然后转移时与上面的 \(dp[v][1]-dp[v][0]+w_{uv}\) 合并起来考虑。

G. Get Ready for the Battle

题目大意：有 \(m\) 个敌人，每个敌人有 \(hp_{i}\) 滴血。给你 \(n\ge m\) 个人，要求组成 \(m\) 支军队（可以为 \(0\) 人）。随后每轮你可以用军队去攻击敌人，每支军队只能攻击一个人，但是不同军队可以攻击同一个人，敌人受到的伤害是攻击他的军队人数之和。不同的轮次中，一支军队可以攻击不同的人，但是军队的分配方式要一开始就固定。给出一种方案，使得所有敌人的 \(hp\) 小于等于 \(0\) 的轮数最小。

题解：至少要 \(\displaystyle{\lceil\frac{\sum_{i=1}^{m}hp_{i}}{n}\rceil}\) 轮。我们来构造一个这样的解。

假设开始时只有一只军队，有 \(n\) 个人。我们依次攻击每个敌人。假设当前敌人至少有 \(n\) 滴血，那么就让所有军队攻击它，否则枚举每个军队，假如人数小于等于当前敌人的 \(hp\)，那么就攻击它，否则就把这支军队拆成两支，一支是当前敌人的 \(hp\)，攻击当前的敌人，剩下的攻击下一个敌人。显然每个敌人最多拆一次，且最后一个敌人不会拆，满足题目要求。

H. Triple

题目大意：有 \(n\) 个序列，每个有 \(x\) 个 \(a_{i}\)，\(y\) 个 \(b_{i}\)，\(z\) 个 \(c_{i}\)。现在从每个序列中选出一个异或起来。对每个数问异或和为它的方案数有多少。

题解：显然 FWT。我们把每个数都异或上 \(a_{i}\)。那么 FWT 后每个位置只能是 \(x\pm y\pm z\)，我们只要求出这 \(4\) 种分别有多少个即可。

我们可以列一些方程 \[ x_{0}+x_{1}+x_{2}+x_{3}=n \] 任取一些 \(x,y,z\)，也可以得到一些方程。但是可以证明至多有 \(3\) 个（包括上面那个）是线性无关的。

我们还需要一个方程，设 \(f[b_{i}\oplus c_{i}]+=1\)，那么 \(f\) FWT 之后，每个位置有 \(x_{0}-x_{1}-x_{2}+x_{3}=f_{i}\)。这样我们就可以高消求出答案了。