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)

Problem J

Solved by ultmaster. 02:05 (+)

Problem K

Solved by kblack. 00:24 (+)

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