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 C
Unsolved.
EOJ 3407。样例都没改。
ultmaster：因为做过，所以判断在现场不能做。
Problem D
Solved by kblack. 00:36 (+1)
裸几何规律，温暖的签到。
Problem E
Upsolved by ultmaster.
题意：有一种循环回文子串：把字符串的某一个后缀移到前面若构成的新字符串是一个回文串，就称循环回文串。求原字符串在修改最多两个字符的情况下的最长循环回文子串，要求长度为奇数。
题解：以一个点为中心，用二分 + hash 的方法，可以求出以该点为中心，修改最多 0 个、1 个或 2 个的最长回文子串。然后把这个信息转化成以 $i$ 结尾的修改 0 个、1 个或 2 个的最长回文奇数串；以 $i+1$ 为开头的修改 0 个、1 个或 2 个的最长回文偶数串。可以发现循环回文串就是前面一个奇数和后面一个偶数拼起来。所以枚举前后的修改次数，两边拼起来就可以。奇偶可以互换，所以还要倒过来再做一遍（偶数回文串如果结果偏左或者偏右的话，倒过来的时候还要偏移）。注意也有可能只有一个奇数，如果姿势不好可能要特判。
ultmaster：这题我要背大锅。kblack 的 hash 敲了半天终于差不多敲对了已经意识模糊了。然后我贡献了一个假得不行的做法，还提出了一个其实完全用不到的 API 需求。然后比赛的剩余时间在就要丢掉的绝望和轮换调试 API 和假做法中度过。其实如果 kblack 的意识还在线的话，或许是有希望的。但是或许时间也不大够了。赛后进行了对拍，花了一个半小时修复了若干个 bug，才艰难地通过随机数据。
Problem F
Solved by ultmaster. 01:06 (+1)
题意：有一个网格，然后有若干个圆去覆盖。求没有被覆盖到的点的数量。
题解：由于询问数量少、行列数量也不大，直接枚举行，然后在列上标记覆盖范围就好了。ultmaster 一开始想上线段树，然后经过 zerol 的提醒，发现线段树也不要。只要一个扫描线就好了。然后扫描线也调不出来（到底是有多惨？），甚至还打印了，最后发现 $n$ 和 $m$ 搞错了。然后修 bug 修了一半（初始化没修），WA1。
Problem G
Unsolved.
Seems similar to EOJ 2842.
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 (+)
题意：求 $n$ 以内能被各位数字之和整数的数的数量。
题解：枚举各位数字之和 $p$，然后维护两个量：一个是当前数模 $p$，还有一个是当前各位数字之和。最后可行条件是当前数为 0 且各位数字之和等于 $p$。
ultmaster: 惊！全队居然没有一个人会数位 DP。kblack 说数位 DP 复杂度不对，大家都信以为真。在没有题可以上的情况下，ultmaster 上机打了个暴搜，发现答案多得一批。绝望。然后经过 zerol 提醒，发现好像不同测试数据之间的计算是可以重用的！然后写得倒是很快。通过跟表手动对拍发现了一个 bug，避免了一个 WA。
Problem K
Solved by kblack. 00:24 (+)
裸矩阵乘法，温暖的签到。