2018 ACM-ICPC China Shanghai Metropolitan Invitational Contest

Problem A

Solved by zerol. 01:21 (+)

题意：求一条直线，至少经过 N 个点中的 N * k 个点，$(0.1 \leqslant k \leqslant 0.9)$。

题解：随机挑两个点，如果有解，那么有 $\frac{1}{k^2}$ 的概率恰好落在答案所在的直线上。当然这是不考虑点重复的情况，事实上这样就能 AC。但是比如 n = 10000，k = 0.1，有 998 个点在同一个点上，另外恰好有一组 1000 个点共线，那么概率会很低。所以如果随机到的两个点一样的话，必须重新在剩下的点里随机，即便这样命中率也只有约 $0.1 \times 0.1 \times 0.0002$。

Problem B

Solved by ultmaster. 00:10 (+)

Problem D

Solved by kblack. 00:36 (+1)

裸几何规律，温暖的签到。

Problem F

Solved by ultmaster. 01:06 (+1)

Problem H

Solved by kblack. 03:01 (+1)

题意：区间平方膜 2018，区间求和。

题解：一个数不断平方膜 2018，最多 4 次后就会进入长度是 6 的约数的循环节，于是将序列分为两类数分别考虑。 对于循环内的数，直接记录当前即平方5次内的所有和，平方操作即是对数列的位移操作，可以懒标记维护。 对于循环外的数，暴力递归到叶子节点，手动平方，一旦进入循环就删掉特殊标记，转化为上一种维护方式。

Problem I

Solved by zerol. 03:34 (+1)

题意：给一个矩阵，每次可以对一个数 +1 或 -1（不能为负），问最少几次使得每行之和相等，每列之和相等。

题解：枚举每行的和，然后建图，每行以及每列是一个点，行（列）如果不够和就连源（汇），超过则连汇（源），行列之间的边费用为 1，有一个方向（代表 -1）有容量限制（因为元素不能为负）。对每行的和的所有可能值进行三分跑费用流。

zerol: 鉴于数据范围很小，kblack 给出了指导性意见——网络流，在 ultmaster 读错题的情况下给出了正确的建图方法，然后蜜汁 TLE，然后加了个三分就过了。然而还有更加简单的做法。

Problem J

Solved by ultmaster. 02:05 (+)

Problem K

Solved by kblack. 00:24 (+)

裸矩阵乘法，温暖的签到。