蓝桥杯历年真题-完整版（VIP试题+C语言版）

【试题大意】 本题大意为，给出一个带权无向图，每次询问所有[l,r]区间中的编号Mod K=C的所有点，把它们连通需要的生成树的最大边权最小是多少。 【试题分析】 20%的数据是直接枚举最大边，看能否让图连通。最大边权最小这点可以启发我们二分答案；对于每个询问这么做，可以得到40%的分数。对于更大的数据，图中“最大边权最小”这一点有更好的性质：随便求一棵最小生成树，答案肯定在这个生成树上完成。那么在生成树上连边的最大权值最小是多少呢？假设我们需要让A1,A2,...,Ac 这c 个点连通，那么我们可以按任意的顺序，让A1 和A2连通，A2 和A3 连通……然后把连通需要的最大边权当成答案即可。正确性很显然：设最大的边权max 是Ai 和Ai+1 连出来的，那么答案至少为max，不然Ai 和Ai+1 连不通；而max 就够了，因为按A1~Ac 的顺序连通就是一个可行的方案。所以，我们需要在树上求两点间的最大值，这用倍增即可在对数时间完成。直接把每个询问Mod K=C 的点弄出来这么做，大约是60 分。 100 分的做法在此基础上进行一些优化：当K 很大的的时候，暴力肯定问题不大，因为点不会多； K 小的时候呢，我们可以做预处理：例如对于Mod 17，那么我们可以将所有编号分为17 类，分别是Mod17=0、1、2……16。这样，每次询问的点肯定是一类里连续的一段，对每类中相邻的点求出答案，然后用线段树等结构维护一下区间最大值就可以了。如果K 的界取Sqrt(N)，整个算法复杂度是O(Nsqrt(N)logN)，实际上可以根据实现时常数对K 的界做调整，标程用的是70。