The 48th ICPC Asia Jinan Regional Contest
题目思路比较直接，代码量略大，要注意比赛节奏
| ID | Difficulty (0-5) | Topic | Status | Code |
|---|---|---|---|---|
| A | 1 | Brute Force | Solved | |
| B | 3 | Sqrt Decomposition, Knapsack on Tree | Upsolved | |
| C | 4 | Constructive Algorithms | ||
| D | 0 | Brute Force | Solved | D.cpp |
| E | 3 | Network Flow, Bipartite Graph Matching | Solved | E.cpp |
| F | 4 | Divide and Conquer, Data Structures | ||
| G | 2 | Disjoint Set Union | Solved | G.cpp |
| H | 3 | Suffix Array | Upsolved | |
| I | 1 | Constructive Algorithms | Solved | I.cpp |
| J | 5 | Math | ||
| K | 2 | Two Pointers, Data Structures | Solved | K.cpp |
| L | 4 | Dynamic Programming, Data Structures | ||
| M | 2 | Convex Hull | Solved | M.cpp |
D. Largest Digit
两个区间长度之和大于 $9$ 答案一定是 $9$，否则暴力。
E. I Just Want… One More…
给定一个二分图，问有多少种方式添加一条边（连接左右）使得匹配数 $+1$ 。
网络流求最大匹配，对于残量网络，$S$ 联通的点数乘 $T$ 联通的点数就是答案。
二分图上跑 Dinic (也就是Hopcraft) 复杂度是 $O(m\sqrt{n})$ 的。
G. Gifts from Knowledge
给定一个 $r$ 行 $c$ 列的 01 矩阵，对每一行选择是否进行反转。
求选择一些行进行反转方案数（允许不选择任何行），使得每一列至多有一个 1 。
反转第 $i$ 行：$b_{i, 1}, b_{i, 2}, \cdots, b_{i, c} \to b_{i, c}, b_{i, c-1}, \cdots, b_{i, 1}$ 。
每个 $1$ 只有在当前列和对称列两种选项（特殊处理 $c$ 奇数中间的情况）
如果两个 $1$ 对称，那么这两个 $1$ 所以在的行反转情况必须一致（要么都反转要么都不）。
如果两个 $1$ 位于同一列，那么一个所在的行不反转 $\Leftrightarrow$ 另一个反转。
这是个等价关系，对每行建立反转和不反转两个点，并查集维护连通块，同一行的两个点连通无解。
考虑两行之间的关系，要么四个点都不连通，要么一定是分成两组连通。
因此连通块的情况是完全对称的，假设最终有 $2x$ 个连通块，答案是 $2^x$ 。
时间复杂度 $O(n\alpha(n))$ 。
I. Strange Sorting
给一个排列，每次可以选一个逆序对，将这两个位置作为端点的区间排序。
构造至多 $\lfloor\frac{n}{2}\rfloor$ 次操作将排列排序。
从前往后扫，每次遇到 $a_i\neq i$，就找最大的 $j$ 满足 $a_i>a_j$, 容易发现 $i,i+1$ 一定都在 $a[i\cdots j]$ 中。
所以每次都能让两个数字归位，只需要至多 $\lfloor\frac{n}{2}\rfloor$ 次。复杂度 $O(n^2)$ 。
*K. Rainbow Subarray
给定数组 $a_1,a_2,\dots,a_n$ 和一个常数 $k$ 。
称区间 $[l,r]$ 是好的，需要满足 $a_i+1=a_{i+1}\ \forall i\in[l,r)$ 。
你可以进行至多 $k$ 次操作，每次操作可以让一个数字 $+1$ 或 $-1$ 。
使得操作后，最大化最长的好区间长度。
首先令 $a_i’=a_i-i$ ，好的区间性质等价于所有 $a_i’$ 相同。
把一组数变成一样的最小代价是都变成中位数。
枚举区间左端点，另一个单调的指针维护右端点。
用对顶堆维护当前数集，如果可以扩张右端点就扩展，否则跳过这个左端点。
总扩张/删除次数 $O(n)$ ，复杂度 $O(n\log n)$ 。
M. Almost Convex
给定点集 $S$ 满足任意三点不共线。
定义一个多边形是 $S$ 的近似凸包，当且仅当其满足：
- 多边形的顶点 $\subseteq S$ ；
- $S$ 中的所有顶点要么在多边形上要么在多边形内。
定义 $S$ 的所有近似凸包中顶点数最少的为 $R$ 。
求有多少个 $S$ 的近似凸包 $Q$ ，满足 $|Q|\le |R|+1$ 。
$R$ 就是 $S$ 的凸包，$Q$ 是凸包一条边向里面凹进去一个点。
按每个点进行极角排序，扫一圈如果相邻的两个点都是凸包顶点，答案 $+1$ 。
复杂度 $O(n^2\log n)$ 。
The 48th ICPC Asia Jinan Regional Contest