T1 我是 A 题 首先分析数据生成器可以知道，所生成的三元组一定是 (A,y,z), (x,B,z), (x,y,C)(A,y,z),\,(x,B,z),\,(x,y,C)(A,y,z),(x,B,z),(x,y,C) 这三种类型之一，也就是说一定有一维被点满了。 我们从这方面入手。考虑将所有三元组分成三类，对每一类单独计算。由于每一类中有一维是全部相同的，所以问题就转化成了一个二维问题。 但分开计算的同时，我们会面临两类之间的答案存在交集的问题，也就是说，不同的类计算出来的答案可能会有重复，于是我们需要考虑去重。 我们一步步来想。 为了讲述简便，我们在下文中有一些定义： 下文中 “二...

白给 190190190 分，直接爆炸。 T1 一般图最小匹配 100100100 分变 101010 分，原因是没有删调试的 freopen，大悲。 一开始想的是先再完全图上跑最小生成树，不难证明最终选出来的边都会在最小生成树上。然后在最小生成树上找 mmm 条没有公共结点的边。 然而这是在太难打，而且 kruskal 在完全图上的时间复杂度也不是很优秀。写 prim 再加上调 DP 用了我 1.5h。 然后突然明悟，发现其实对 aaa 排序之后相邻的点之间连边得到的不仅是最小生成树，还是一条链。 这样就好打了。设 dpi,j,1/0dp_{i,j,1/0}dpi,j,1/0​ 表示前 ii...

白给 190190190 分，直接爆炸。 T1 一般图最小匹配 100100100 分变 101010 分，原因是没有删调试的 freopen，大悲。 一开始想的是先再完全图上跑最小生成树，不难证明最终选出来的边都会在最小生成树上。然后在最小生成树上找 mmm 条没有公共结点的边。 然而这是在太难打，而且 kruskal 在完全图上的时间复杂度也不是很优秀。写 prim 再加上调 DP 用了我 1.5h。 然后突然明悟，发现其实对 aaa 排序之后相邻的点之间连边得到的不仅是最小生成树，还是一条链。 这样就好打了。设 dpi,j,1/0dp_{i,j,1/0}dpi,j,1/0​ 表示前 ii...

T1 躲避技能 估分 100pts100pts100pts，实际 0pts0pts0pts。 题目大意 在 nnn 个点的树上有 mmm 个起点和终点，将其两两配对形成 mmm 个点对，使得每个点对之间的距离和最小 解题思路 枚举全排列可得 40pts，网络流可以在 O(n3)O(n^3)O(n3) 的时间复杂度内完成。 想要 A 掉这一题，需要时间复杂度在 O(nlog⁡n)O(n\log n)O(nlogn) 一下的算法。 要求最优解，我们有两个方向可以思考：一是构造最优解，如构造，一般的动态规划；二是先跑一遍任意解，并通过答案计算出最优解，如换根 DP。显然这一题更加适合后一种方法。 从...

洛谷博客观影传送门：Link 博客园观影传送门：Link 题目大意 求一棵基环树的重心。即一个点，使得树上到其距离最长的点到其的距离最短。注意，这个点不一定是一个节点，可以在树上的任意位置。输出树上到其距离最长的点到其的距离。 或者说求基环树最短的直径？（大雾 解题思路 显然，这颗基环树的直径只有两种情况：经过环和不经过环。 如果不经过环，那必定是环上某个点为根的子树的直径，这个可以用一般树上的做法做。再在所有的子树上的直径求最大值就是不经过环上的直径的答案。 重点在于环上的情况。首先我们画一个细菌一棵基环树，为了方便，我们默认这棵树上的边权为 111，实际实现时只需要考虑上边权就行了： 我...