====== The 2016 ACM-ICPC Asia Beijing Regional Contest ====== [[https://vjudge.net/contest/394138|比赛链接]] ===== A - Harmonic Matrix Counter ===== Upsolved by nikkukun. ==== 题目描述 ==== 定义 $A_{n \times m}$ 是和谐矩阵，当且仅当对任意位置 $(i, j)$ 有： - $A_{i, j} \in \{0, 1\}$ - $A_{i, j} \oplus A_{i, j + 1} \oplus A_{i, j - 1} \oplus A_{i - 1, j} \oplus A_{i + 1, j} = 0$ 给定参数 $n, m$，你需要求字典序第 $k$ 小的、大小为 $n \times m$ 的和谐矩阵上某个位置的数，或说明不存在这样的矩阵。 ==== 解题思路 ==== 要发现一个性质：如果第一行的 $m$ 个数确定了，那么后面的所有数都是确定的。因此可以设第一行的 $m$ 个数为未知量，用最后一行 $m$ 个数之间的约束关系得到 $m$ 个异或方程组，求解即可得到答案。 考虑方程中的 $s$ 个自由变元及其提供的解数，显然可以依次给这变元赋值 $0, 1, \ldots, 2^s - 1$（二进制表示），因此若 $k > 2^s$ 则是无解的。有解情况下，只要如上赋值即可得到每个字典序的值。 实际上，高斯消元中，自由元是哪些完全可以换一下（考虑消元过程可以把行上下移动），只要保证方程的 $s$ 个自由元已经确定，那么剩余部分就是固定的。 具体的操作是，按未知数从大到小消元（即消成上三角矩阵沿水平翻转的形式，这样子非自由变量对应的未知数就会尽可能靠后，相当于自由变量位置靠前），这样我们便解决了这个问题。 ===== C - Asa's Chess Problem ===== Solved by Potassium. ==== 题目描述 ==== ==== 解题思路 ==== ===== C - Asa's Chess Problem ===== Solved by Potassium. ==== 题目描述 ==== ==== 解题思路 ==== ===== D - What a Beautiful Lake ===== Solved by nikkukun. 水题不表。 ===== E - What a Ridiculous Election ===== Solved by Potassium. 水题不表。 ===== F - What a Simple Research ===== Solved by qxforever. 水题不表。 ===== H - A New Ground Heating Device ===== Upsolved by qxforever. 题目与题意[[.:qxforever:circleunion#%E9%97%AE%E9%A2%98_2|见此]]。 ===== I - A Boring Problem ===== Solved by Potassium. ==== 题目描述 ==== ==== 解题思路 ==== ===== K - JiLi Number ===== Solved by nikkukun & qxforever. ==== 题目描述 ==== 定义 $f(i)$ 为 $i$ 的十进制表示中 $1$ 的个数，求有多少个不超过 $n$ 的数 $p$，使得 $\sum _{i=1}^p f(i) = p$，且其中最大的数是多少。 ==== 解题思路 ==== 根据 $1$ 均衡的出现频率和数位长度，直接猜测样例里出现的就是最大的 JiLi Number，也就是十一位数之后没有满足条件的数。打表即可。 ===== 赛后总结 ===== ==== nikkukun ==== ==== qxforever ==== ==== Potassium ====