Graph 题目链接 题目大意 给出一颗树，有两种操作，添加一条边，删除一条边。 每个时刻必须满足 如果有环那么环的边权异或和必须是0， 必须是联通的。 题解 也就是先求一下每个节点到根节点的异或和，然后用这些值的异或当边权求个最小生成树。 问题就是 知道一些点的点权，边权是两个点权异或，然后求最小生成树。 求最小异或值可以用字典树。 好了，比赛的时候就想到了这里，不会求了。然后考虑到了并查集，但是不会两个集合合并，也就是合并n - 1次，但是怎么求两个集合里的数各挑一个的异或最小值，然后就不会了好菜，连异或最小生成树都没听过 然后 异或最小生成树，可以这样求： 分治，从高位到低位考虑。最优肯...

Tokitsukaze and Rescue 题目链接 题目大意 给一张完全图，每个边有边权。 问删掉k条边让从1到n的最短路最长，问这个最长的距离是多少？ 边权随机，点的个数: 50 题解 做的时候，感觉到了这个题很暴力，但是没想到这么暴力。。 做的题少，主要不知道边权随机是干嘛用的。。 就是爆搜。。 跑一个最短路，枚举最短路上的边，然后删掉，继续跑最短路，继续枚举。 这样的话，复杂度是 这。。谁敢写啊。。 但是题解说由于边权随机，所以最短路径上的边的数量不是很多，这样可以过。。 #include <algorithm> #include <cstdio> #incl...

Go Running 题目链接 题目大意 一些人在跑步，从任意一个位置开始，向左或向右跑，速度都为1 m/s。 现在已经知道在ti 时刻xi位置上出现了至少一个人，问最少有多少人在跑步 题解 先说一说比赛的时候的不足: 想到了往右跑的人在任意时刻 t - x 一定是相等的。 想到了往左跑的人在任意时刻 t + x 一定是相等的。 现在就是找一些值覆盖这n个点。。 然后就不会了，感觉有点像二分图，但是一直不知道怎么搞，像是脑子死机了一样。还有对时间复杂度理解的不够，一直认为1e5跑网络流会tle，可是二分图上的网络流复杂度为n * sqrt(n) ; 然后这道题就出不来了。总之：我好菜 其实再给...

Harmony Pairs 题目链接 题目大意 S(A) 代表A的每位数之和。 求0 <= A <= B <= n 并且 S(A) > S(B) 的（A，B）对的数量。 题解 看到这道题，首先想到数位dp，然后就不会了。。 状态表示：dp[i][j][f1][f2] 表示当前是第i位（也就是前i位的状态已经计算过来了。现在往i + 1位转移）， S(A) - S(B) = j ， f1表示A与B的大小关系：A < B的时候f1是1 A == B 时 f1是0 ，A不能大于B f2表示B与N的大小关系：B < N的时候f2是1 N== B 时 f2是0 ，B不...

Josephus Transform 题目链接 题目大意 一个长度为n的排列，初始为1……n。 有m次操作： 每次操作是进行y次 k-约瑟夫变换 。 这个变换就是：先把1……n写成一个环，然后从1开始找到第k个，把这个数加到b里，把这个数在环里删去，从这个位置下一个 继续找第k个，直到数字被删完。 1<=n<=1e5 1<=m<=1e5 1<=n * m<=1e6 题解 求进行一次k-约瑟夫变换得到的排列b，可以用线段树求出来，复杂度是n*logn. 进行y次变换也就是用b排列把1……n置换y次。 怎么置换呢？ 可以发现置换满足结合律。 也就是说 对a进行两...

Portal 题目链接 题目大意 刚刚给一个无向图，边权是距离，有k个任务，每个任务是要去两个点，必须先去ai点，后去bi点。任务必须从前往后做，也就是说不能做完1任务就做3任务。现在有两个传送门可以放置，放置传送门的时候必须走到那个点放置，撤掉传送门的时候可以不在那个点。 一个传送门可以直接传送到另一个传送门，距离为0。 刚开始在1号点，问完成任务需要走过的距离最少是多少？ 点数：300，任务数：300，边数：4e4 题解 完成任务a1->b1->a2->b2->a3->b3…… 顺序肯定是这样走的。 所以不用把任务两个两个分开。 a1，b1，a2，b2，a3，...

A National Pandemic 题目链接 题目意思 给一颗树 有三种操作： 1 x y 给每个点点权都加上y - dis[x][y] （dis[x][y]是x->y路径上的边数） 2 x 如果x点的点权大于0，就把他变为0. 3 x 查询x的点权。 题解 先看第一种操作： y - dis[x][y] = y - (dep[x] + dep[y] - 2 * dep[lca]) = y - dep[x] - dep[y] + 2 * dep[lca]. 怎么实现呢？ +2*dep[lca] 可以变为给x的到根节点的路径上num都加2，计算的时候就是到根节点路径上的num和，因为x和...

如何在有序矩阵中找第k大的数？ 378. 有序矩阵中第K小的元素 题目链接 一个矩阵从左到右递增、从上到下递增怎么找第k大的数？ 1、 把矩阵变成一维然后排个序 2、 合并有序数组那样合并 3、 二分 主要说二分怎么求。 二分一个第k大是多少。 check的时候，也就是判断有没有k个数大于等于mid 比mid小的肯定在是左上角一些元素。 比如这样一个矩阵：  如果mid是12的话： 就有左上角这样一些：  这样的话就可以用n+n的时间快速统计出来有多少个数大于等于mid！！ (明明可以暴力的) int sum = 0; int j = 0; int i = n - 1; while(i &gt...

Tree 题目链接 题目大意 给一棵树，让选择一个联通的子图 满足: 度数大于k的点的数量不超过1个（小于等于1） 图是联通的。 边权和最大。 问能选出来的最大边权和是多少。 题解 树形dp dp[x][0] 表示x的子树里的点的度数都小于等于k的边权和最大值。 dp[x][1] 表示x的子树里有一个点或0个点的度数大于k的边权的最大值。 转移方程: dp[x][0]显然是儿子中最大的k - 1个dp[v][0]的和。 dp[x][1]怎么算？ 有两种情况： 当这个度数大于k的点是x的时候，dp[x][1]是所有儿子的dp[v][0]的和。 当这个度数大于k的点不是x的时候，选k - 2个儿子...

Valuable Forests 题目链接 题目大意 定义一个树的权值为它的所有顶点度数的平方和。 森林的权值为所有树的权值和。 求有n个点，带编号点的，所有的森林的权值和。 带编号意思是1-2-3 不等于 1-3-2 题解 prufer序列学习博客 大佬题解博客 看的这两篇博客学会的这道题 （其实还是有点懵逼） 可以看上面的博客，我写博客完全为了加深印象。 。。 先预处理几个数组： 定义N[i] 代表具有i个点的树有N[i]种。 根据pruper序列中的结论：一颗有n个节点的树有n的n - 2次方中形态，（因为pruper序列中每个数都可以是n个数中的任意一个）。 N[1] = 1; for...

Groundhog and Apple Tree 题目链接 题目大意 给一棵树，有边权，点权。 走过这条边的需要的hp是边权。只有hp大于等于边权的时候才能走这条边。 第一次走到这个点可以获得 ai 的hp。 也可以呆在原地不动休息，每秒hp增加1。 刚开始在1号节点，问要走完所有的点，并且回到一号节点所需要的最少的休息时间。 题解 首先，这个题肯定是考虑子树走的顺序。 因为如果走完这颗子树，可以额外获得一些 hp 在走下一棵子树的时候就会抵消掉一些，少一点等待时间。 于是，考虑怎么贪心的走。 好了，比赛的时候就到这里，不会贪心。。脑子一片混乱。感觉这个题好乱，但是看了大佬的题解之后就感觉很清...

Decrement on the Tree 题目链接 题目大意 一棵树，每次选一条路径让这条路径上的边权都减一，问最少操作多少次可以让这棵树的边权变成0？ 还有m次修改，每次给出x，y把第x条边边权变为y。 每次修改完输出答案是多少。 题解 一直以为是什么数据结构维护之类的。。是我太年轻了 每次选一条边，也就是两个点，让这两个点之间的边权都减一。 然后考虑每个点选几次 如果这个点连的边两两可以匹配，那么就不用选这个点。 怎么确定两两可以匹配完呢？ 如果最大值小于总和 - 最大值。就一定可以匹配。当然还要判断一下奇偶的情况。奇数的话 肯定是要选这个点一次的。 如果最大值大于总和 - 最大值，这个...

Kidnapper’s Matching Problem 题目链接 题目大意 给一个长度为n的数组a，长度为m的数组b，长度为k的数组s。 从a数组中选一个长度为m的连续子序列跟b数组两两匹配。 配对只能是这样配：(a[l], b[1]), (a[l + 1], b[2]), (a[l + 2], b[3]) …… 使得a[l + i - 1] ^ b[i] 能在s中选一些数异或得到。 也就是a[l + i - 1] ^ b[i] 在s的线性基里出现。 题解 还是蠢啊，干不出来 假设 a ^ b 在s的线性基里出现。 设s的线性基是D。 那么把a中消去D中的位得到a’ 把b消去D中的位得到b’...

Tokitsukaze and Colorful Tree 题目链接 题目大意 给一颗树，每个点有颜色、权值。 求 的值。 这个式子就是颜色相同的，并且u不是v的祖先，并且v不是u的祖先的权值异或完的和。 两种操作： 1 x v 把x点的权值变成v 2 x c 把x点的颜色变成c 每次操作完输出上面公式的值。 点数：1e5 颜色：1~n 权值：2的20次方 题解 离线操作， 把修改一个点的权值或颜色，变成删除一个点，增加一个点。 考虑每种颜色对答案的贡献。 为什么每种颜色每种颜色的统计呢？ 因为空间不够开n个树状数组的，并且每种颜色是独立的，不会影响另一种颜色的。 所以记录每种颜色的变化，每次...