2020-2021:teams:i_dont_know_png:icpc2016-beijing-regional

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:icpc2016-beijing-regional [2020/09/18 21:23]
nikkukun 创建
+++ 2020-2021:teams:i_dont_know_png:icpc2016-beijing-regional [2020/09/19 11:44] (当前版本)
nikkukun add contest
@@ 行 11: / 行 11: @@
 ==== 题目描述 ====
+定义 $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，也就是十一位数之后没有满足条件的数。打表即可。

2020-2021/teams/i_dont_know_png/icpc2016-beijing-regional.1600435419.txt.gz · 最后更改: 2020/09/18 21:23 由 nikkukun