Code A - The Fair Nut and Elevator B - Kvass and the Fair Nut C - The Fair Nut and String D - The Fair Nut and the Best Path E - The Fair Nut and Strings F - Max Mex A - The Fair Nut and Elevator 简单猜想一下，可以知道电梯在一楼是最优的，后面直接统计即可 B - Kvass and the Fair Nut 因为我们要使最小的最大，因此肯定是所有数越平均越好 求出总和，减去需要花费的，然后剩下的除以nnn (下取整) 当然，因为初始不相同的原因，我们还要提前找到所有数中最小的 最后对结果取个minminmin即可 C - The Fair Nut and String 当b出现时，后面每出现一个a都能与前面所有的合法的序列组成一个新的序列 因此每次b出现时，更新增量，a出现时更新答案 D - The Fair Nut and the Best Path 不用考虑中途没油的情况，如果中途没油，那么前面这段肯定不用选，因为少掉这段答案肯定会增加 因此题目变成了求选路径，使得所选点权-所选边权最大 类似求树的直径，树形DP即可(有一次DFS做法，笔者用了两次，笔者代码实现较丑，不建议参考) E - The Fair Nut and Strings 考虑对这kkk个字符串建一个TrieTrieTrie树，答案则是这棵树的节点个数 因此我们要最大化每层点的个数 对于第iii层 对于字符串A的第iii个字符aaa，如果a==′b′a == 'b'a==′b′ 说明如果前面全部最大的哪条路径的现节点不能选aaa，因此数量需要减111 字符串B同理 然后下一层的节点为当前层节点数量乘2,接着继续考虑下一位字符 因为只有kkk个字符串，因此每层节点最多只有kkk个 F - Max Mex 代码参考 xyz32768 线段树维护图上信息 线段树上每个节点维护[l,r][l,r][l,r]这些点权是否在一条路径上 ，如果在则节点储存该路径左端点右端点信息即可 合并时对于子节点上两条路径444个点进行判断即可，如果 dis(x,y)+dis(y,z)==dis(x,z)dis(x,y) + dis(y,z) == dis(x,z)dis(x,y)+dis(y,z)==dis(x,z) 或 dis(x,z)+dis(y,z)==dis(x,y)dis(x,z) + dis(y,z) == dis(x,y)dis(x,z)+dis(y,z)==dis(x,y)或 dis(x,y)+dis(x,z)==dis(y,z)dis(x,y) + dis(x,z) == dis(y,z)dis(x,y)+dis(x,z)==dis(y,z)或 则说333点在一条路径上，每次合并时做两次判断即可