构造!

CF1375E Inversion SwapSort

Click to Fold/Unfold

给定一个长度为 $n$ 的序列 $a$, 求 $a$ 中的所有逆序对 $(i_1,j_1),(i_2,j_2),\cdots ,(i_m,j_m)$ 的一个排列 $p$,
使得依次交换 $(a_{i_{p_1}},a_{j_{p_1}}),(a_{i_{p_2}},a_{j_{p_2}}),\cdots ,(a_{i_{p_m}},a_{j_{p_m}})$ 后序列单调不降.
$1\le n\le {10}^3$, $1\le a_i\le {10}^9$.

感觉还可以. 不过大概是因为前两天那道ssfz友好联测的D.

因为这个你需对是跟一开始的值位置相关而不是跟某时刻的值相关, 从位置角度, 考虑先用所有和 $n$ 构成逆序对的东西把 $n$ 换到最后一位, 这个是简单的, 从小到大换和 $a_n$ 构成逆序对的即可, 发现这样的好处是前面的顺序不变. 于是可以递归下去.

CF741C Arpa’s overnight party and Mehrdad’s silent entering

Click to Fold/Unfold

有 $2n$ 个人围成一圈坐在桌子边上, 每个人占据一个位子, 对应这 $2n$ 个人是 $n$ 对情侣, 要求情侣不能吃同一种食物, 并且桌子上相邻的三个人的食物必须有两个人是不同的, 只有两种食物($1$ 或者是 $2$), 问一种可行分配方式.

$n\le {10}^5$

三个人的食物中两个人不同感觉很难办啊

帮他加强限制, $2i$ 与 $2i-1$ 不是一组. 合理性在于两个匹配合成出来的图一定是二分图

感觉真的很不会构造

CF547D Mike and Fish

Click to Fold/Unfold

• 给定 $n$ 个整点.
• 你要给每个点染成红色或蓝色.
• 要求同一水平线或垂直线上两种颜色的数量最多相差 $1$.
• $n,x_i,y_i\le 2\times {10}^5$.

按照行向列连边方式建图, 然后就是给边定向让入度出度之差不大于 $1$, 这时你想到欧拉回路.

但直接跑的话不一定有欧拉回路, 考虑建一个新点向所有奇数度数点连边即可.

欧拉路定度数感觉挺典的, 但是唉.

CF449C Jzzhu and Apples

Click to Fold/Unfold

给出正整数 $n$, 你要从 $1-n$ 之间的正整数中选出尽可能多组, 每组两个数, 使得每一组的最大公约数大于 $1$; 输出能分成最多组的个数, 并按任意顺序输出每组的两个数.

$n\le {10}^5$

首先肯定要尽量让所有数都被用上, 而当一个质数的倍数有奇数个时, 留下 $2p$ 是比留下 $kp$ 优的, 所以策略就是从大到小遍历质数, 如果没被匹配的有奇数个扔掉两倍的那个.

CF1368E Ski Accidents

Click to Fold/Unfold

有一个由 $n$ 个点 $m$ 条边组成的有向无环图, 每个点出度至多为2. 您需要标记一些点(不超过 $\frac{4}{7}n$ 个). 标记一个点 $u$ 将会删除所有与 $u$ 连接的边.
您需要找到一种标记点的方案, 使得删边后的图中每一条路径至多有一条边.

• $1\le n\le 2\times {10}^5$, 并且所有数据中 $n$ 的和不超过 $2\times {10}^5$.

这谁想的到啊

于是吧所有入度为 $0$ 的点放到集合 $A$, 至少有一条来自 $A$ 的入边的点放到 $B$, 剩下的至少有一条 $B$ 的入边杀了. 显然没有长 $2$ 的了.

这为啥是对的呢? $A$ 出边至多有 $2A$ 条, $B$ 的出边至多有 $2B$ 条, 于是 $C\le 4B\le 2A$.

CF527E Data Center Drama

Click to Fold/Unfold

• 给定一张 $n$ 个点 $m$ 条边的连通无向图.
• 你需要加尽可能少的边, 然后给所有边定向, 使得每一个点的出入度都是偶数.
• 边可以是自环, 也可以有重边.
• $n\le {10}^5$, $m\le 2\times {10}^5$.

有了刚才的CF547D你是不是很容易想到欧拉回路然后定向了.

于是给每两个奇度点连一条边. 欧拉回路交替定向.

但仍然不一定合法, 如果你最后欧拉回路是奇数条会有一条边没法定向, 你就连一个自环变成偶数.