2020 ICPC 济南 ¶

排名	当场过题数	至今过题数	总题数
24/546	6	8	13

A¶

solved by 2sozx

题意¶

所有操作均在 \(mod2\) 意义下，给出两个 \(n\times n\) 矩阵 \(A,B\) ，问有多少个 \(n\times n\) 的矩阵 \(C\) 满足 \(A \times C = B\cdot C\) ，前者为矩阵乘法，后者为矩阵点乘。\(n\le200\)

题解¶

可以直接将方程列出来，很容易发现 \(C\) 中每列都是相互独立的，因此对每一列单独进行计算，高斯消元即可，求出每一列的最大无关数 \(s\)，方案数即为 \(2^{n - s}\)。由于只有 \(0 ,1\) 可以用 \(bitset\) 优化，

C¶

solved by 2sozx Bazoka13 JJLeo

题意¶

数量为 \(1,2,3\) 的石子各有 \(a_1,a_2,a_3\) 堆，合并两堆石子数量为 \(x,y\) 的代价为 \((x \bmod 3)(y \bmod 3)\)，求将所有石子合并为一堆的最小代价。(\(0 \le a_i \le 10^9\))

可以发现一堆石子一旦数量变为 \(3\) 的倍数就相当于消失了，从而只需要把模 \(3\) 为 \(1\) 和 \(2\) 的石子堆中多的一方自己合成自己变为另一个，然后 \(1\) 和 \(2\) 进行合并即可，直到最后只剩下一个。

D¶

upsolved by 2sozx Bazoka13 JJLeo

题意¶

\(n\) 个人卷翻天，它们能卷出 \([l_i,r_i]\) 分，每个人一开始的计划都是卷满 \(r_i\) 分，现在想让大家不那么卷，求所有人卷的分之和最小是多少，最终方案必须满足对于每个人来说，分数不高于他的人人数不减少。

题解¶

先按 \(r_i\) 从小到大，\(l_i\) 从大到小排，设上一个人卷的分为 \(x\)（对第一个人来说，\(x=0\)），则这个人卷的分为 \(\max(x,l_i)\)。

K¶

upsolved by JJLeo

题意¶

给定序列 \(a_1,a_2,\cdots,a_n\)，设 \(f(a,S,K)\) 为 \(a_1 \oplus S, a_2 \oplus S, \cdots, a_n \oplus S\) 中第 \(K\) 小的数。

\(q\) 次询问，给定 \(L,R,K\)，求 \(\min \limits _{S = L} ^ R f(a,S,K)\)。(\(1 \le n,q \le 10^5\)，\(0 \le a_i,L,R < 2^{30}\))

题解¶

先按 \(a_1,a_2,\cdots,a_n\) 的二进制从高到低建 trie 树，处理出每个点如果接下来每一位都可以任意异或 \(0\) 或 \(1\)，那么第 \(k\) 小最小都能是多少。具体即为先将左右子树合并，右子树加一个这一位的高位 \(1\)，得到一个有序序列；然后左右子树交换，左子树加一个这一位的高位 \(1\)，得到一个有序序列，两个序列相同位置取 \(\min\) 即可。

之后每次操作从根节点开始 dfs，当前状态分为四种：0 - 既不脱离上界也不脱离下界；1 - 脱离上界；2 - 脱离下界；3 - 上下界都脱离了。

对于状态 3，答案直接为接下来随便走的第 \(k\) 小，已经预处理过。

对于其它状态：

当前位 \(L=R=0\)，则 3 种状态都可以让这一位为 \(0\)，然后状态不变；状态 1 可以额外选择让这一位为 \(1\)，然后变为状态 3。
当前位 \(L=R=1\)，则 3 种状态都可以让这一位为 \(1\)，然后状态不变；状态 2 可以额外选择让这一位为 \(0\)，然后变为状态 3。
当前位 \(L=0,R=1\)，让这一位为 \(0\)，则若状态为 2，变为3，否则状态变为 1；让这一位为 \(1\)，则若状态为 1，变为3，否则状态变为 2。
当前位 \(L=1,R=0\)，状态必然为 1 或 2（否则 \(L > R\)），如果状态为 1 只能让这一位为 \(1\)；如果状态为 2 只能让这一位为 \(0\)。

每次询问额外产生的分支不会再产生额外分支，树高 \(32\)，从而复杂度为 \(O(32^2q)\)。空间上，每个点会存储在自己祖先处，空间复杂度为 \(O(32n)\)。

\(T\) 组询问，给定 \(\texttt{01}\) 序列 \(a_0,a_1,\cdots, a_{m-1}\)，问 \([0,L]\) 中有多少整数 \(x\) 满足 \(\forall i \in [0,m-1],\operatorname{popcount}(x+i) \bmod 2 = a_i\)。(\(1 \le T \le 1000,1 \le m \le 100,0 \le L \le 10^{18}\))

题解¶

考虑枚举低 \(7\) 位，\(x\) 到 \(x+m-1\)，剩下的高位最多变化一次，且变化只和高位末尾连续 \(1\) 的奇偶有关，因此我们可以再枚举高位的状态，从而就可以知道 \(x\) 到 \(x+m-1\) 每一个数 \(1\) 的数量，并与序列 \(a_0,a_1,\cdots, a_{m-1}\) 对比判断，如果完全相同就加入答案。

需要使用数位 dp 处理上述高位状态各有多少方案，只需记录 \(1\) 的奇偶性和末尾 \(1\) 的奇偶性即可。dp 过程中只需要记录脱离上界的数量，最后再把 \(L \bmod 2^7\) 的方案数加到紧贴上界的状态中即可。

M¶

solved by JJLeo

题意¶

\(n\) 个蛋，每个蛋要煎两面，每次可以同时煎 \(k\) 个，问最少要煎几次。

2020 ICPC 济南¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

L¶

题意¶

题解¶

M¶

题意¶

题解¶

记录¶

总结¶

2020 ICPC 济南 ¶