2020ICPC区域赛正式赛上海个人题解（仅供参考，非官方，是比赛后写的所以队友写的部分题目skip掉，不完整，仅供交流讨论，有问题欢迎讨论）
M Gitignore
是一个模拟签到，不多说
B mine sweeper 2
这道题是关键在于“一个地雷图是一个01图，所有位置取反之后数字总和不变”这个结论，想到之后选择改变次数少的一边就好了。
这个结论可以从两个地方看出，
第一，限制次数是nm/2的，所以显然是取反
第二，数字表示的是一个二分图左边点的度数，那么显然两边是相等的。
（所以过的人多的话就要往简单的方向去想）
C sum of log
数位DP，比较套路，就是代码比较复杂，队友敲的（赵大佬tql）
D walker
先二分时间再讨论会简单一点，即便如此，我们也分了13种情况，不过我们做复杂了。
注意在先往中间跑的话随时是能折返的
然后二分我们T了两发，最后卡常卡过去了，实际上可以利用“二分100次的精度够高”来卡。
E the journet of Gear Autumn
推导公式题。定义fi为长度i的数组个数，枚举1的位置得到n2的公式，类似滚动数组维护来优化就好了。
代码很短，但是比赛的时候没有过……忘记初始化了，呜呜呜
G fibonacci
来，和我一起念“奇奇偶奇奇偶奇奇偶”
I sky garden
记住结论“外层到内层一定经过对应的直线”
维护每一层之间的距离总和,求解结束
L traveling in the grid world
胡搞题
先猜一个结论“两个点之间最多经过一个中转点”（首先做到这道题的时候时间不多了，只能假设经过一个点，而且，三个点大概率没有两个点好）
再猜一个结论，中转点一定在起点终点所连直线附近（距离直线越短，折线的距离总和越短，那么中转点显然在直线附近，又因为gcd=1的密度，只需要枚举直线下面一个点就好）
最后感谢上海大学，核桃超级好吃，题目质量很高，数据靠谱，赛后也能立马补题。
全部评论
(3) 回帖