Educational Codeforces Round 154 (Rated for Div. 2)

· · 个人记录

https://codeforces.com/contest/1861

A. Prime Deletion

因为 1 到 9 的每个数恰好出现一次，所以 13 和 31 恰好有一个满足条件。

B. Two Binary Strings

要求存在一个 i 使得 a_ia_{i+1}=b_ib_{i+1}=01。充分性显然。必要性只需要说明一次操作不会使不合法的 i 变得合法。

C. Queries for the Array

设 f_i 是长度为 i 的前缀是否排序，则只要满足 f_0=f_1=1，且 1 在 0 之前就有解（构造直接前面全相等，后面变小就行）。所以每次遇到 1 的时候判断是否有 0，然后将 f 全变成 1；其余操作的时候维护 0 的个数即可。

D. Sorting By Multiplication

假设只能乘正数，那么每次操作只能减少一对相邻递减的数，答案就是相邻递减的数对个数。

乘 0 显然没必要，因为可以变成前缀或者后缀乘 \infty。如果乘了负数，那么最后答案一定是前面一段负数后面一段正数，枚举分界点，操作次数就是前面的递增个数加后面的递减个数加 1。

两种情况取较小即可。

E. Non-Intersecting Subpermutations

假设给定一个数组，那么求它的代价可以贪心：从前往后每找到一个不相交的满足条件的子段就选上。

时间复杂度 $O(nk)$。 #### F. Four Suits 先考虑求一个人的答案。 枚举这个人选择的花色，那么所有这个花色的牌应当尽可能分给他，这样一定最优（如果他分到了其他花色的牌，并且其余人分到了该花色，那么交换一下不会变劣）。问题变成给其他人分配使得最大值最小。 假设二分答案 $x$，那么我们要做一个最大匹配，左边是 $n-1$ 个人，右边是四种花色，之间的边的容量是 $x-a_{i,j}$，点的容量分别是 $b'_j$（分给第一个人之后的剩余牌数）和 $k-\sum_{j=1}^4a_{i,j}$（$k$ 是每个人应该拿到的牌数）。如果有左边的完美匹配则说明答案 $\le x$。 最大流等于最小割，而因为右边的点数是常数，计算最小割可以先枚举右边割掉的点，之后对于左边的每个点就是独立的，可以割掉左边和中间的较小值。 对每个点分别求的时间复杂度是 $O(n^2\log C)$，但是可以发现求最小割中 $O(n)$ 的因子来源于计算形如 $\sum_{i=1}^n\min\{0,c\cdot x-u_i\}$ 的项，而这可以直接对 $u_i$ 排序后二分，因此时间复杂度变成了 $O(n\log n\log C)$。