付诺の小站

树题目大意 给一棵根为$1$的有根树，点$i$具有一个权值$a_i$。 定义一个点对的值$f(u,v)=max(a_u,a_v)×\vert a_u−a_v\vert$。 你需要对于每个节点$i$，计算 $ans_i=∑_{u∈subtree(i),v∈subtree(i)}f(u,v)$ ，其中$subtree(i)$表示$i$的子树。 请你输出 $⊕(ans_i \mod 2^{64})$ ，其中 $⊕$ 表示$XOR$。 解题思路 容易联想到启发式合并，顺着这个思路，思考怎么计算将一个数合并进一个集合对答案的贡献。假设要在当前集合$S$放进一个数$x$，对于小于$x$的数，贡献应该为$\sum_{u\in S,\ u\lt x}(x-u) \cdot x$；对于大于等于$x$的数，需要引进两个变量$ts$和$sum$，其中$ts = \sum_{u\in S, \ u \ge x}u^2$，$sum=\sum_{u\in S, \ u\ge x}u$，那么此时的贡献就为$ts - sum \cdot x$。(关于如何想到这一点，对于$S$中 ...

天天爱跑步题目大意 给定一棵$n(1\le n \le 10^5)$个节点的基环树，求经过第$i(1\le i \le n)$个节点的最长简单路径。 解题思路 首先，如果给出的是一棵简单树，则直接做两遍$dfs$，再加个换根$dp$直接秒。对于这道题，我们需要思考环会造成的影响。 先考虑非环点，那么这个点一定会是一个以环上点为根的子树上的节点，这就相当于一棵简单树，但是呢，在这里我们需要先预处理出每个环上点不往以它为根的子树走所能走的最长距离$g_i$。既然不能往子树走，那么自然只能往其他环上点以及它们的子树上走。所以，先预处理出每个环上点能往子树走的最大距离$mxd_i$。假设我们求出了每个环上点的$mxd$，那么点$j$的$g_j = max(\vert i - j\vert + mxd_i)(i \in S)$，$S$表示环上点的集合。对于这种有环以及有绝对值的式子，直接断环成链会好写很多，断环成链后官方题解用的双指针，笔者这里用的是单调队列，难度上感觉差不多。（因为总体代码冗长，笔者就不再讲解细节，只介绍一下大致思路。不会的算法可以去学，用到的也只是些简单算法。） 求 ...

[猫咪们狂欢](Problem - 7488 (hdu.edu.cn))题目大意 有$n$只猫咪和两棵大小为$n(1\le n\le 1000)$的树。每只猫咪有一个编号$1\sim n$，每棵树的节点编号也是$1\sim n$。在$n$只猫咪中，有$k$只猫咪是狂欢猫。狂欢猫会开派对，而其他猫咪则会睡觉。 每条树的边有一个狂欢值。如果某条边连接的两个节点上都待有狂欢猫，那么这条边的狂欢值就会被计入总狂欢值。要求安排这些猫咪，使得最大化狂欢猫总狂欢值，并输出这个最大值。 解题思路 考虑对从源点向每一个狂欢猫的编号建一个边权为$0$的边，再从所有的狂欢猫编号向汇点建一个边权为$0$的边。对于第一棵树中两端点可被狂欢猫覆盖的边建一个虚拟点，从源点向这个虚拟点建一个边权为狂欢值的边，再从这个虚拟点向所需的狂欢猫的节点建一个边权为正无穷的边，表示这条边不能被割。对于第二棵树也是同样的道理，从狂欢猫的节点向虚拟点建边权正无穷的边，再从此点向汇点建边权为狂欢值的猫。 这样通过建图就将题目转换成了最小割模型，最后跑一遍最小割即可。 参考代码123456789101112131415161718192 ...

旅行题目大意 给定一棵$n(1 \le n \le 2 \times 10^5)$个节点的树，每个结点都有一个类型$c_i(1 \le c_i \le n)$和权值$w_i(1 \le w_i \le n)$，定义一条链有权值当且仅当起始点的类型相同，且权值为起始点的权值和。求取任意条不相交的链的权值和最大的值。 解题思路 对于每个节点，考虑有一条链覆盖它和没有链覆盖它对应的最大的子树权值和。没有链覆盖时，直接将所有子树的$dp$值相加即可；被链覆盖时，考虑用线段树合并维护每种类型所对应的链上的子树的$dp$值的和。在进行线段树的合并的时候，是对两棵树的节点取最值，这样就成功维护了$dp$值。 参考代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include <bits/stdc ...

Challenge NPC 2题目大意 给定$n(1 \le n \le 5 \cdot 10^5)$个点$m(0 \le m \le n - 1)$条边的无环森林，求它补图上的哈密尔顿路径，如果没有，输出$-1$。 解题思路 考虑对每棵树进行遍历，发现当树的深度大于$3$时，可以一步走完；当树的深度小于等于$3$的时候，可以分两步走完。当且仅当只有一棵树，且这棵树的深度小于等于$3$时没有哈密尔顿路径，因为无法将其分成两部分。 所以，对于每一棵树，首先求出它的一条直径，并存储这棵树上各个点的深度，若深度大于$3$，则先将偶数深度的点存入数组，再将奇数深度的点存入数组；若深度小于等于$3$，则分别存入对应的$vector$，最后加入答案的时候保证中间有其他的点即可。 参考代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include <bits/stdc++.h>#define ...

Rigged Games题目大意 给定一个长度为$n(1 \le n \le 10^5)$的$01$字符串以及两个整数$a$和$b(1 \le a, b \le 10 ^ 5)$，$1$表示这一小局$team \ A$获胜，$0$则表示$team \ B$获胜。当一个$team$获胜$a$小局后，记作获胜一大局，并将小局比分清空。获胜$b$大局后则赢得最终胜利。问将这个字符串以第$i(1 \le i \le n)$位作为起点开始循环时，最终获胜的队伍是不是$team$，若是输出$1$，否则输出$0$。 解题思路 考虑对于每个起点$i$预处理出从这个点开始完成一大局比赛后第二局比赛的起点，以及这一大局$team\ A$是否获胜。自然想到再用倍增预处理出进行$2 ^ 1,2^2,2^3,\dots$大局后$team\ A$获胜的次数。然后处理询问，只需要从最高位往下遍历凑出有一个队获胜的条件即可。至于预处理大局的起点，可以联想到双指针，因为每一小局在$1$~$n$上是连续的。 最后将上面的想法整理起来即可。 参考代码1234567891011121314151617181920212223 ...

Floor Tiles题目大意 给定一棵所有边权为$1$的树，定义$f(u) = \sum_{v} dis(u,v)$，$v$表示树中所有节点，$dis(u, v)$是指节点$u$到节点$v$之间的简单路径的长度。 给出一个整数$x(1 \le x \le 10^{18})$，如果一棵树中存在两个节点使得$f(u) - f(v) = x$，则称这棵树为“好树”，求构造出一棵“好树”所需的最小节点数。 解题思路 首先考虑$n$个节点所能构造出的$f$的最大差值，很明显，形成一条链的时候差值最大，可以选取端点和最中间的点，可以得到最大差值$w = \lfloor\frac{n - 1}{2}\rfloor \cdot \lceil\frac{n - 1}{2}\rceil$，接下来思考对这条链上加点，具体对以下这条链进行操作： 首先选取节点$1$和节点$6$，此时$w = 5 \times 5 = 25$，然后我们可以在$6$的右边多连一个点，或者在$1$的左边多连一个点，或者在节点$1$到节点$6$的之间的简单路径上加点。然而在$6$的 ...

Malfunctioning Typewriter题目大意 给定$n(1\le n \le 1000)$个长度为$m(1 \le m \le 1000)$的字符串，你有一个打字机，要求你打印一个字符串，并且它是由这$n$个字符串按任意顺序连接形成的字符串之一。使用这台打字机时，你有$p(0.5 \le p \le 1)$的概率打出想要打的字符。 问采取最优策略，打印出满足要求的字符串的概率是多少？ 解题思路 可以考虑建一棵字典树，那么打出一个合法字符串就相当于在这字符串上走$n$次，每走一次遍删去所对应的字符串。那么，对于字典树上的某一节点，假设它的左子树上的叶子节点数为$x$，右子树上的叶子节点数为$y$，需要保证遍历到这个节点的时候，往它的左儿子走了$x$次，右儿子走了$y$次。并且每个节点对答案的贡献都是独立的，假设节点$i$的贡献为$f[x_i][y_i]$，那么答案即为：$\prod f[x_i][y_i]$。 接下来思考如何求$f[x_i][y_i]$，自然联想到$dp$，$f[i][j]$表示打印$i$个$1$和打印$j$个$0$的概率，可得状态转移方程： $f[i][j ...

Bridging the Gap2题目大意 共有$n(1 \le n \le 5 \times 10^5)$个人处在河的一侧，现在有一艘船，船上只能容纳$k$个人，$k \in [l, r]$。问能否将所有人送至河的另一侧。 解题思路 假设这$n$个人一开始处在河的左侧，可以推出，从左侧划船至右侧在整个过程中是一定可行的。 因为，每次从右侧划回来都至少会带回$l$个人，那么左侧人数一定始终大于$l$，并且他们的体力也一定大于等于$1$，要将所有人送至右侧，自然不会让划回左侧后没体力的人回来，所以从右侧回来的人体力一定大于等于$1$，原本留在左侧的人体力也一定大于等于$1$。 所以，我们只需要保证整个过程中，每次都至少有$l$个人能从右侧划回左侧，并且他们的体力大于等于$2$。 那么首先，我们算出整个过程中从右侧返回左侧的总次数，$S = \lceil\frac{n - r}{r- l}\rceil$，即第一次划向右侧会使左侧减少$r$个人，接下来每个来回都会使左侧减少$r - l$ 个人，最后上取整即可。 接下来算出每个人最多能从右侧返回左侧多少次，$a_i = m ...

并题目大意 平面直角坐标系上有$n(1 \le n \le 2 \times 10^3)$个矩形，对于$k\in[1,n]$，求解在$n$个矩形中随机选取$k$个不同的矩形，其所有覆盖部分的并集的面积的期望值，由于答案可能很大，请对$998244353$取模。 解题思路 官方题解的做法是用任选的方案数减去没有被覆盖的方案数，思路比较清晰简单。奈何笔者赛时并没有想到，一直在用容斥的思想去写，所幸最后还是写了出来。笔者认为还算是一次较为有益的尝试，所以这篇博客主要探究容斥的做法，至于此题的具体做法将不再赘述。 考虑从$n$个矩形里面取出$i$个矩形，然后参考这样一个经典的图， 可以将$A$、$B$和$C$分别看作一个矩形所覆盖的区域，它们之间有部分相互重叠，并假设当前$n$为$3$，要从这三个矩形里面取$i$个矩形，并求它们覆盖面积的期望。 首先参考这张图里的容斥公式： $\vert A\cup B\cup C \vert = \vert A\vert + \vert B\vert +\vert C\vert - \vert A\cap B| - \vert A\cap C\v ...