2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
easy: ACEGHK
medium-easy: BJL
medium: D
?????: I
A.
B.
C.
对 \(R[],C[]\) 分别按奇偶性分段。
网！
D.
考虑 check 一个串，枚举右走对应的前缀 pre，下走对应的后缀 suf。
把每行反串拼接中间连特殊字符，建 SA，能 match 上 pre 的后缀 rk 是个区间。
把每列拼接中间用特殊字符连接，建 SA，能 match 上 suf 的后缀 rk 是个区间。
问题转化为：矩形内数点。
E.
倒着递推出每个位置的范围。
F.
树 hash
G.
排名的增量为新来的人里面比 1 号选手厉害的人数。
线段树维护区间最小值。
H.
第一种情况是挤在一个矩形内，面积/2即可。
第二种情况在不同的矩形，先对每 A > B 的矩形交换 A，B，若两个矩形分别为 \(a*b,c*d(a<b,c<d)\)，那么答案为 \(min(a,b) * min(c,d)\)，按 A 排序，枚举第一维被谁卡住，求后缀极大值。
炸精度。
I.
好难。
J.
注意到 type 3 最多摆放 50 个。
\(dp[i][j]\) 表示考虑前 \(i\) 个位置，恰放 \(j\) 个 type 3，type 2 最多能放几个。
枚举 \(i,j\) 用 type 1，尝试替换，type 2 即可。
K.
线段树维护区间矩阵乘。区间修改为交换行和行，列和列。
L.
先考虑每条“边”都要建的 case。
“边” & 工人的二分图，跑匹配？
给每类工人建个中间点，最大流，ok，边少了。
生成树怎么办？环上怎样选择环长 - 1条边？
建一个中间源点限制流向“环上的边”点流量不超过环长 - 1。最大流为 \(n-1\) 即可。
