联合省选2021 游记
Day1
爆炸了爆炸了，考场上不知道怎么回事。T1 啥都没想到，人傻了。
大众分 200，我 66 + ?，太好笑了。
所以思维基本是没有提升。总不全是考场 debuff 的锅吧！
不过怎么说呢，我也不后悔这些日子学数数。
【听天由命.jpg】
怎么办啊我好废啊 类目啊
qy：不要患得患失
那…… 好呗
Day2
A 了 T1，结果赛后一测发现正解没锅，暴力锅了！！！我暴力的 20 分呐！！！没了 /dk
所以两天都没有大众分。总分大概 hcy 一天的分都没有。（upd：是真的，但是 hcy 挂分了，听他在对面哀怨的和 dst 说“我好菜我菜死了”的时候 我 难 受 极 了）
qy 并不打算放我们回去学 whk 的样子，又要开始冲刺夏令营了！！
并不知道 SC 的出题风格。已经被 noip 和联合省选搞晕了，完全 joi(sc) 的风格嘛。
接下来的路也不知道怎么走，就做 joi 和填坑吧，whk 自己上心，数学自己学。还有早睡，困死了困死了猝死了
题解。
D1T1. 卡牌游戏
最多翻 m 次，最小化极值——容易想到把 a 和 b 都拍在数轴上，枚举值域左端点，满足下面两个限制的情况下，最小化右端点：
- 删去的前缀和后缀中 a 的出现次数不超过 m
- 没有正反面同时被删的事件发生
有单调性，双指针即可。O(nlogn)。有解无解的细节还挺多的，CCF 完全可以卡死一堆漏考虑的程序…… 就这？上 UOJ 挨 hack 吧！
D1T2. 矩阵游戏
构造题，你要想到的是先随便构造一个值域没有限制的 A（抱歉…… 我连这一步都没想到……），然后通过行列加减来使其合法，相邻加减号不同（这样不改变四个格子的和）。但是仅这样还不够，因为形成的不等式形如 a_{i, j} \pm r_i \pm c_j \geq 0，分类讨论太烦啦！不如让行列加减如下：
行：1
2
3
4
5+-+-+
-+-+-
+-+-+
-+-+-
+-+-+
列则刚好错开：1
2
3
4
5-+-+-
+-+-+
-+-+-
+-+-+
-+-+-
本质其实很平凡，就是你一开始就注意到有 nm 个变量但只有 (n - 1)(m - 1) 个方程，缺 n + m - 1 个方程，即如果确定了一行一列就确定了整个矩阵，而行列的操作就做了这件事。
D1T3. 图函数
复杂度 $n^3$ 就离谱好吧，$n^3$ 跑 $1000$ CCF 少爷机是不是膨胀力？依稀记得 CSP2020 时 $1e6$ 离散化 被卡 痛失那 $35pts$ CCF 卡常之仇我与你不共戴天！！！
其实删到 $x$ 时 $x$ 能到达 $y$ 等价于 $x$ 走 $[x, n]$ 的导出子图边能到达 $y$。因为 $x$ 前面的点如果没被删掉，意味着经过它也到不了 $y$。
设 $g_{x, y}$ 表示 $x$ 能否通过 $[x, n]$ 到达 $y$
$ans = \sum g_{i, j} \& g_{j, i}$
考虑 $g_{x, y}$ 表示最多删除多少边使得 $x$ 能通过 $[x, n]$ 到达 $y$
$ans = \sum \min(g_{i, j}, g_{j, i})$
我们想得到 $g$！
枚举删除的边显然不行。
考虑 floyd，从大到小枚举并加入中转点 $k$，此时所有 $g_{i, j} (i \leq k)$ 路径都是 $\geq i$ 的。
D2T1. 宝石
想了很久（wtcl），哦可以倍增 + 二分 + 主席树！
不会 windows 手动开栈空间，虽然没有因为这个丢分但要记录一下方法：在 devc++ 的工具一栏，在「编译时加入以下命令」处加上1
-Wl,--stack=1024000000
数字以 B 为单位。
ubuntu 则是1
ulimit -s 1024000
数字以 KB 为单位。
D2T2. 滚榜
真是很简单的题啊…… 暴力稍微改改就能 AC 了，可惜考场上没时间…… 主要思维太慢了！！！ 简直光速退役好么……
对于一种排名的 $a_i$ 序列，$b$ 每次尽量小的选，看贡献和是否不超过 $m$
$b_i = b_{i - 1} + \max(0, a_{i - 1} - a_i)$
$\sum b_i = \sum \max(0, a_{i - 1} - a_i) (n - i + 1)$
那么 dp，$f_{s, i, j}$ 表示选了集合 $s$ 的人，最后一个是 $i$，贡献和为 $j$，的排列方案数。
空间 $5e7$，时间 $6e8$，但可以 AC。
D2T3. 支配
咕咕咕