"难金"的 ICPC 南京赛点，究竟有多难

南京赛点历来是强队云集之地，在南京赛点拿金牌可谓是难上加难。

下面我们来看看 2019 年南京的题目。由于是现场参赛的，也就没有了代码分享。

Problem A

题意：蛇形矩阵中有

个位置是有价值的，价值是位置上的数位和，每次询问一个子矩阵中的价值总和。

题解：蛇形矩阵，给出坐标求位置上的数，可以直接

通过分类讨论出来。

只需要知道他是从内往里第几圈就能算出来。

得到了每一个位置的价值，就变成了一个二维数点问题，直接树状数组维护一下就好了。

Problem C

题解：毫无营养的分块打表

Problem D

题意：给定一个

，每一次等概率从一个点走向其连向的每个点或者停在原地，第

次操作会造成

的伤害，求总伤害的期望值。

题解：如果每次操作都只会造成

的伤害，令

代表节点

相连的所有点（包括

），到终点的期望伤害就是

，移项之后就可以算出值。

现在第

次操作会造成

的伤害，但我们可以将其拆成路径上每个点到终点的路径之和。这样，令

代表此时到终点的期望伤害，则

。同样，移项后计算出答案。

Problem E

题目：求

题解：枚举gcd，莫比乌斯反演然后杜教筛。

,把

求和移到最后就是等比数列，交换

得

，后部分杜教筛，前部分数论分块。

Problem F

题意：给出一个全排列，第

次操作，

，每次可以从

所在全排列中的附近

个位置选择一个

数作为

，要求字典序最大的，求这样的数列非

数有几个。

题解：产生这个数列的方式，显然是贪心，每次在全排列中的附近

个位置选择一个

且最大的数。

于是就发现，当前的数列非

个数就是当前数所在位置在全排列中的附近

个位置选择一个

且最大的数的数列中非

数量

。

直接用

维护一下窗口的数，二分查找就能得到每一个数周围满足要求的数，然后从小往大递推一下就好了。

Problem H

题意：在一个存在负权边的图中，依次加入六条给定起点终点的边，使得加入的边边权尽量小，且加入之后不存在负权环。

题解：每一次加入一条边，用

算出两点之间的距离，取反作为边权加入图。