Warning: session_start(): open(/tmp/sess_b3f2da60bab668ea1b5dea42757a7592, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== Codeforces Round #656 (Div. 3) ======
====== [A] Three Pairwise Maximums ======
===== 题意 =====
水。
===== 解法 =====
水。
====== [B] Restore the Permutation by Merger ======
===== 题意 =====
同样的两个 1-n 排列随意穿插在一起，让你还原
===== 解法 =====
这个直接记录每个元素的第一次出现 ...
====== [C] Make It Good ======
===== 题意 =====
求一个序列的最长好后缀。
把后缀序列看成一个 deque，如果能从按值小到大 pop 那么是好的。
===== 解法 =====
从后往前看，直接记录上升下降后的第一次上升在哪，在这里断开。
====== [D] a-Good String ======
===== 题意 =====
递归定义一个 a-好 串，只需满足以下情况之一：
* 长为 1，全为 a
* 长 > 1，前一半全为 a，后一半是 a+1-好 串
* 长 > 1，后一半全为 a，前一半是 a+1-好 串
问最少修改多少个元素可使得给出的串成为一个 'a'-好串
===== 做法 =====
像线段树那样区间 DP 即可。
记 dp[i][j] 为标号为 i 的区间成为 j-好串 的代价
记 DP[i][j] 为标号为 j 的区间全改成 j 的代价
则：
* dp[u][i] = min(DP[u * 2][i] + dp[u * 2 + 1][i + 1], dp[u * 2][i + 1] + DP[u * 2 + 1][i])
* DP[u][i] = DP[u * 2][i] + DP[u * 2 + 1][i]
====== [E] Directing Edges ======
===== 题意 =====
给一个图，有些边无向，有些边有向。问能否为所有无向边确定方向，使得确定完后的图是 DAG。有解输出方案。
===== 解法 =====
直接无视无向边，仅根据有向边进行拓扑排序，然后直接按照拓扑序确定无向边的方向。
====== [F] Removing Leaves ======
===== 题意 =====
给一棵树，每次可选同父亲的 k 个叶结点将其删除，问最多可进行多少次。
===== 解法 =====
不会做。
====== [G] Columns Swaps ======
===== 题意 =====
给一个 2*n 的矩阵，你每次操作可以翻转一列的元素（上下交换），问最少多少次使得上下两侧均为 1-n 的排列。
===== 解法 =====
直接跑个 2-SAT 就能过了吧。