划水记 Day -1 (2023.12.29) 学校元旦晚会，Rick Roll 诈骗全班，感觉良好。 好久没做过绿油油的火车了，一颠一颠颠睡过去就很神秘。 Day 0 (2023.12.30) 好好好，都来北京了，早餐吃 KFC ？？？ 北京站开始随机游走。 好好好，都来北京了，中餐吃麦当劳？？？ 领了胸牌和 T 恤，回房间睡了两个小时到 15:20。晚饭吃了点烤鸭。 试机，冷身赛，统统不重要，口胡口胡就过去了。但是面了几个人，不错。 Day 1 (2023.12.31) 自助早餐吃的有点多，进考场晕乎乎的/cf 宣读比赛规则，每三个题换一次气球颜色，红蓝绿黄，逆天坏了。 开题是 $12$ 题，拿到 A 就感觉很可做，写了十分钟感觉有点细节锅了。遂看榜。发现已经 rk300+，去跟了个水到逆天的 T4。然后把离散化板子题 T2 给切了，dfs 序板子题 T3 同样是一眼秒。赛时 $00:40$ 拿到气球，在临近的座位中略有落后。这时候去补 T1，给大家表演一个狂吃四发罚时，一路红到头，开始遥遥落后。T8 的位置比较神秘，感觉比 T1 简单多了。$O(n\sqrt{n})$ 做法感觉是
D. Split Plus K 记最后相同的数为 $t$，则不难发现对于每个数 $x$，操作都形如 $t+y=x+k$，直到这个数变成 $t$，若这个数的操作次数为 $y$，则有 $(y+1)t=x+yk$，整理得 $x-t=y(t-k)$，其中 $y\ge 0$，将其改写为 $x-k=y(t-k)$，其中 $y\gt 0$，这样不难发现最优解时 $t-k$ 为所有 $x-t$ 的 $\gcd$，且所有 $t-k$ 同号。 E. Multiple Lamps 既然按下所有按钮，最终只会有编号为完全平方数的灯亮，所以可以数据分治。 $n\ge 20$ 全部点亮 $n\lt 20$ 注意每一种最终的点亮情况可以反演出按钮情况，所以可以枚举最终亮的灯。 F1. Small Permutation Problem (Easy Version) $a_1 \gt 1$ 或 $a_n \lt n$ 时无解，启发我们注意到差分只存在 $0,1,2$ 三种，开始分讨 $\Delta=a_i-a_i-1$，并记 $i-a_i=t$。 $\Delta=0$：前 $i-1$ 个数不存在 $i
Flight Routes G 既然所有单向边 $(u,v)$ 都满足 $u<v$，从原图取出点集 $[x,n]$ 就一定满足给定三角形 $[x,n-1]$ 行的限制。于是可以反过来递推，当前考虑到第 $x-1$ 行，顺次从 $x$ 到 $n$ 检查是否需要连接 $(x-1,i)$ 即可。 #include <bits/stdc++.h> using namespace std; constexpr int maxn = 750 + 10; bitset<maxn> v[maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i=1;i<n;++i) { string s; cin >> s; for (int j=i+1;j<=n;++j) if (s[j-i-1] == '1')
这是一个纯组合意义解法。 考虑已经插入了一些 $1\times2$ 的竖长方形，然后方案数就只和未放置的列数 $x$，空列组成的连通块数 $y$ 有关。 每个空连通块至少需要再填两个长方形，不妨假设它们已经放置，接下来还需要添加 $k-(n-x)-2y$ 个长方形。添加长方形，相当于将一个横长方形切一刀，能切的位置有 $2(x-y)$ 个。那么增加长方形的方案数就是 $\binom{2(x-y)}{k-(n-x)-2y}$，整理得 $\binom{2x-2y}{x-k+n}$。 将 $x$ 列拆成 $y$ 个块的方案数，插板法得到 $\binom{x-1}{y-1}$。 将 $y$ 个块放回到原矩形中的方案数，观察到原矩形有 $y$ 个块和 $n-x$ 个竖长方形共 $n-x+y$ 个位置，需要放 $y$ 个块且不允许块与块相邻。不妨考虑先任意布置 $y$ 个位置 $a_1,a_2,\cdots,a_y$，最终放回到 $a_1,a_2+1,\cdots,a_y+y-1$ 便满足条件。也就是 $\binom{n-x+y-(y-1)}{y}$，整理得 $\binom{n-x+1}{y}$。
yrq
