杂题乱做3

CF1503D Flip the Cards

鸽了很久，也攒了挺多题，总之从刚做的开始写。
首先，不能同时有 $a_i\le n,b_i\le n$ ，因为这样就会存在另一组 $a_j>n,b_j>n$ ，这两组显然构不成题目中的偏序关系。

钦定原序列中 $a_i,b_i$ 中较小的为 $c_i$ ，较大的为 $d_i$ ，我们发现答案序列肯定是一个前缀 $k$ 对所有 $1\le i\le k$ 满足交换后 $a_i\le n,b_i>n$ ，对所有 $k<i\le n$ 满足 $a_i>n,b_i\le n$ ，即 $c$ 序列单峰， $d$ 序列单谷。
考虑将原序列按 $c$ 升序排序，答案序列相当于将这个序列撕成两个按 $d$ 降序的子序列，再拼起来。

此时应该可以一车 $\log$ 用 ds 优化 dp 了，但是有优秀而好写的线性做法。我们对排序后的 $d$ 序列做前缀 $\min$ 和后缀 $\max$ ，如果存在 $\min\limits_{i=1}^kd_i>\max\limits_{j=k+1}^nd_j$ ，则前后两个部分互不干扰，因此我们将这样的段分开来做。然后，我声称这样的段划分方案是唯一的，因此直接划分，然后分类讨论分成的哪一段翻转即可，写法非常简单。

关于为什么是唯一的：
假设分出的一段是 $[l,r]$ ，则 $d_l$ 一定不是区间 $\max$ ，不然会单独划分为另一段。假设区间 $\max$ 的位置为 $m$ ，如果区间合法，则 $[l,m)$ 区间必然满足 $d$ 单调递减，且划分时这些必然都划分到 $l$ 所在的一段。
若 $m$ 不为 $r$ ，我们的划分保证存在 $m<n\le r$ 使得 $d_{m-1}<d_n$ ，因此区间 $[m,n]$ 内所有 $d_i\ge d_n$ 的 $i$ 都选入 $m$ 序列，其余选入 $l$ 序列。
然后我们发现刚才的性质可以继续扩展，即：若 $n<r$ ，则存在 $p$ 使得 $d_p>\min\limits_{i=l}^nd_i$ ，因此区间 $[n,p]$ 内所有 $d_i\ge d_p$ 的 $i$ 都选入 $m$ 序列……
于是我们发现划分方案是唯一的。

$\texttt{code}$

CF1500C Matrix Sorting

首先先给行之间两两匹配，可以使用哈希解决，有多个相同的从上至下匹配，如果无法匹配说明无解。
然后，全局排好序相当于 $n-1$ 对相邻行的上下关系都满足，因此我们一组一组考虑。
观察到每一列至多操作一次，所有对于每一组，我们考虑每一列对其关系的影响，如果 $b_{i,j}<b_{i+1,j}$ ，那么按第 $j$ 列排序后可以修正第 $i$ 组的关系，我们从第 $j$ 列向第 $i$ 组关系连边。若 $b_{i,j}>b_{i+1,j}$ ，那么按第 $j$ 列排序会打乱第 $i$ 组关系，我们从第 $i$ 组关系向第 $j$ 列连边。然后，这张图的拓扑序状物的倒序就是一组解，特别的，因为只要有一列能修正第 $i$ 组关系就能将其排好序，因此我们将组的入度设为 $1$ 。
最后，如果一组入读没有清零（即没有列将其还原），一开始也不满足，则无解。

$\texttt{code}$

P6900 [ICPC2014 WF] Sensor Network

（2023.11.29 模拟赛T1）
首先点对之间的距离只有 $O(n^2)$ 个，我们枚举作为答案的点对，记录其距离 $l$ 。然后枚举哪些点到这两个点的距离都小于等于 $l$ ，并按在其连线段的哪一侧（叉积的符号）划分。

建出的图（贺了一张，挂了找我）

然后在已选的距离大于 $l$ 的点之间连边，观察到同侧的点两两之间距离一定小于等于 $l$ ，因此连出的是一张二分图，跑最大独立集即可。时间复杂度 $O(n^2\times (n^2 \sqrt n))=O(n^{4.5})$ 。因为跑不满（枚举点对、最大独立集都是），所以还是跑得比较快的。
补充一下，二分图最大独立集输出方案时，是 A 点集里和源点联通的，以及 B 点集里和源点不连通的。这题还要记得特判 1。

$\texttt{code}$

P7372 [COCI2018-2019#4] Slagalica

（2023.11.28 模拟赛T3）
感觉评不了黑。首先，我们发现 T x y R x y R x y 三步可以交换 (x+1,y) 和 (x+1,y+1)。然后，通过将想交换的两个转到菱形上方，我们得到了交换任意邻项两个的方法。因此我们学会了构造任意大小的环。于是将 $k$ 分解质因数，然后将 $nm$ 个点划分成组，分别对应 $k$ 每个质因数的最高次幂即可。

$\texttt{code}$

P5037 抓捕

有网瘾？电电就好！
没怎么写过点权最短路就写了下。简单题，注意到点权最短路中一个点第一次被访问到时就是最优方案，因此当松弛时直接判一个点是否被访问过即可，单次最短路的复杂度为 $O(n \log n + m)$ 。

$\texttt{code}$

P8518 [IOI2021] 分糖果

（2023.11.24 模拟赛）
扫描线对每盒糖果单独做，将区间操作转化为时间上的后缀加。

$\texttt{code}$

CF1515F Phoenix and Earthquake

感觉挺神秘的，，不是很会这种题。。
结论是随便构造一棵生成树，只要 $sum_{a_i}\le k\times(n-1)$ 就一定有解。
构造方法是从叶子往根做，如果一个叶子 $i$ 的 $a_i\ge k$ ，那么直接合并，剩下的部分依然满足性质；否则放到最后做这个，相当于砍掉这个叶子，砍掉了一个节点但值减少不到 $k$ ，依然满足性质；并且最后合并时一定合法，这是由 $sum$ 保证的。
因此构造长度 $n-1$ 的答案序列，随便 $dfs$ 生成树，叶子大于等于 $k$ 就加上其权值 $-k$ 并放在答案序列前面，否则放在后面。