Day -6
我以为是今天比赛，然而我发现没收到比赛邮件，然后我看了看日期，才发现原来是下周。
Day 0
在上学，根本没法上 APIO 的课。
Day 1
比赛终于开始了，然而今天要做核酸，不过还好，核酸在下午做，比赛在上午。很快就到了 9:00，比赛开始了。
T1
开幕棋盘格连通块问题，而且还是限制数据存储方式的。
题目大意： 在 ( 2 n + 1 ) × ( 2 n + 1 ) (2n+1)\times (2n+1) (2n+1)×(2n+1) 的棋盘格中每一格只能存 100 个字节，一共遍历 n n n 轮，第 i i i 轮遍历左上角为 ( [ 1 , 2 n ? 2 k ? 1 ] , [ 1 , 2 n ? 2 k ? 1 ] ) ([1,2n-2k-1],[1,2n-2k-1]) ([1,2n?2k?1],[1,2n?2k?1]) 的大小为 3 × 3 3\times 3 3×3 的矩阵，每次只能看到矩阵内存储的信息，然后修改最左上角一格。
我在每次遍历时把整个棋盘格中下一次遍历不到的内容全都存到了角落里，直到最后一次整个棋盘格都在第一格，然后再运算得出答案，这题我得了 14 分。
T2
这题的剧情好像是第一题的续集。
题目大意： 已知有 n n n 个点 m m m 条边的有向图，在动态加点的过程中求什么时候第 1 个点到第 k k k 个点中有任意一点可以成环。
我只写了 DFS 暴力，最后几分钟试图写 BFS 优化一些，结果没调试完，得了 12 分。
T3
这场比赛我大部分得分都在这题，这确实是很精彩的一题。
题目大意： 构造一个任意长度的排列，使得该排列有 k k k 个上升子序列。
对于前 10 % 10\% 10% 的数据，直接从 k ? 2 k-2 k?2 写到 0 0 0 就正好有 1 个空序列和 k ? 1 k-1 k?1 个长度为 1 的子序列了。
然后，我发现了长度为
s
s
s 的连续上升序列的非空子序列的个数为
∑
i
=
1
s
C
s
i
\sum\limits_{i=1}^s C_s^i
i=1∑s?Csi?
又由二项式定理
(
a
+
b
)
n
=
∑
i
=
0
n
C
n
i
a
i
b
n
?
i
(a+b)^n=\sum\limits_{i=0}^n C_n^ia^ib^{n-i}
(a+b)n=i=0∑n?Cni?aibn?i
得出
∑
i
=
1
s
C
s
i
=
2
s
?
1
\sum\limits_{i=1}^s C_s^i=2^s-1
i=1∑s?Csi?=2s?1
故原问题就变成了构造一个长度为
n
n
n 的序列
s
s
s，使得
k
?
1
=
∑
i
=
1
n
∑
j
=
1
s
i
C
s
i
=
∑
i
=
1
n
(
2
s
i
?
1
)
=
∑
i
=
1
n
2
s
i
?
n
k-1=\sum_{i=1}^n \sum_{j=1}^{s_i}C_s^i=\sum_{i=1}^n\left(2^{s_i}-1\right)=\sum_{i=1}^n 2^{s_i}-n
k?1=i=1∑n?j=1∑si??Csi?=i=1∑n?(2si??1)=i=1∑n?2si??n
即
∑
i
=
1
n
2
s
i
=
k
+
n
?
1
\sum_{i=1}^n 2^{s_i}=k+n-1
i=1∑n?2si?=k+n?1
我本来想的是枚举
n
n
n 使得
p
o
p
c
o
u
n
t
(
k
+
n
?
1
)
=
n
\mathrm{popcount}(k+n-1)=n
popcount(k+n?1)=n，结果发现这样的数很难找到，于是我就改为
p
o
p
c
o
u
n
t
(
k
+
n
?
1
)
≤
n
\mathrm{popcount}(k+n-1)\leq n
popcount(k+n?1)≤n，然后将位权较大的位数拆分成位权较小的位数。
然后我试着在连续的排列中交换一个元素，结果失败了。
最终得分
| T1 | T2 | T3 |
|---|---|---|
| 14.00 | 12.00 | 63.19 |
