验题人个人题解，写了除数论外的十二题。本文中不会讲述前置知识，默认大家都会，并且不会写详细的思考过程，请大家多多思考。

按个人体感难度顺序递增。

K 签到1

前置知识点：模拟

简单模拟 略 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202082

L 签到2

前置知识点：stl

stl模拟 略 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202091

E 传送门

前置知识点:bfs/dijkstra,虚结点

懒人方法，直接将数值大小相等的点建立虚结点，进入虚结点的路径长是1，出长为0建图即可。 代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202061

C 交错数组调整

前置知识点：贪心

简单手玩/直觉可知，调整后面的数永远比调整前面的数更优，贪心模拟即可。 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202051

D 赚米

前置知识点：二分，贪心

如果第二天的股价比今天高，那么今天买明天卖一定更优，二分初始值判断结果是否符合条件即可，注意中间答案很大，甚至会爆__int_128，满足条件及时返回即可。 代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202057

G 最大区间和

前置知识点:暴力枚举

将这个柿子写成前缀和的形式后，可以发现对于相同的前缀值，只有最左边的和最右边的可能是可以作为答案的左端点/右端点的，证明是显然的，略。暴力枚举即可。 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202068

J 并查集

前置知识点:启发式合并，路径压缩。

启发式合并维护nxt数组，其中nxt数组的含义是以i为开头最远连续可以到达的位置是nxt[i]，在查询时只需要进行路径压缩查询即可。nxt数组的维护类似于并查集，(所以并查集可能是可以写的？）如果合并的一个端点的和它连续的值存在于另一个集合中那么就合并即可。正确性等价于并查集。 代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202075

I 队列重组

前置知识点:树状数组，贪心

从后向前枚举每个位置，对于可以到达这个位置的所有人中，选择最近的，使用树状数组加速模拟过程。 为什么这样是对的而从前向后不是？因为从后向前比从前向后的约束更大，如果一个人可以到达后面的位置，那么他一定可以到前面的位置（听起来是废话），于是如果从前向后枚举可能导致一个人先向前，再向后走。 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202073

A 网格染色

前置知识点:网络流

先把正数全选再考虑负数的情况，如果这一行/列没被选，说明这一行/列全是负数。 对于剩下的还没被选的行/列，可以大体分为两种选择：

  • 选这一行/列中最小值
  • 选一行和一列的交点同时消除一行一列。

考虑费用流，建图时分出行和列n+m个点，每个点到汇点费用为这一行/列的最小值，为第一种选择，每一行向每一列连边，特别的，行到汇点的流量是1，列到汇点的流量是2，这是因为要保证流量一定能达到最大。第二种的费用为 这是因为选了这条边后，要将列单独向汇点的费用减去。 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202022

F 数星星

前置知识点:dfs序

如何判断是否是等差数列？对于一个结点x我们有

（这是一个直觉的柿子，我并不会证明）其中x_gcd表示的是差值的gcd，并且我们只需要算出每个点和其父亲的差值的gcd即可。 除去特殊情况:子树内全部结点相等，特殊判断，子树内全部结点全部相等如何判断呢？详见广大校赛同名题目:数星星 于是问题变成了这个柿子，只需要dfs一遍就好啦~ 如果不会，请搜索广州大学第十八届ACM大学生程序设计竞赛（同步赛）E 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202066

H elo

前置知识点:dp,数据分治

首先考虑第一种dp方式:算每个点在第i轮获胜的概率 然后考虑第二种dp方式:按值域dp，对每一个对战的块中，dp[100]表示能力值为i的人获胜概率是多少。 在数值小的时候用第一种方式，数值大的时候用第二种方式，反正跑的挺快的，很色情。 使用第二种方法可以直接通过本题，出题人没有卡，我觉得很不美丽。 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202114

B 染色之旅

前置知识点:基环树，判环，带权并查集,std

首先我们知道，基环树图可以看作是若干颗树和环组成的森林。 我们首先将问题变成环上问题和树上问题 对于环上的所有问题，大根堆模拟暴力走两遍环即可。 对于树上问题，考虑将操作离线下来后，倒叙处理，由于每个点最多被经过一次，所以经过后可以路径压缩掉，而路径压缩后实际上走过的距离，是带权并查集的板子。 再结合一下树上问题走到环结点处后可能还存在步数，那么便是环上该处理的问题，当成一次操作塞入环即可。 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202039