月度归档: 2021年8月

5 篇文章

CF1179D Fedor Runs for President
题目链接:CF1179D 给一棵 $n$ 个点的树,求加入一条边后,最多有多少条无向简单路径。 简单路径定义为任意一个点最多经过一次的路径。 $n\leq 5\times 10^5$。 Sol 考虑原来的树显然任意两点之间都能抵达,答案为 $\frac{n(n-1)}2$。 然后加入一条边 $(x,y)$ 就可以把 $x$ 到 $y$ 之间的路径拉…
P6072 『MdOI R1』Path
题目链接:P6072 给定一棵 $n$ 个节点的无根树,从中选择两个不交路径,求边权异或和之和最大值。 $n\leq 3\times 10^4$。 Sol 这里具体讲讲一只 $\log$ 的做法(在此感谢 神仙lwy)。 考虑这种题首先套路地枚举分界点 $x$,使两条路径一条在节点 $x$ 的子树内,另一条在子树外。 然后就很自然地想到了 $\ma…
「NOIP2021模拟赛8.19 C」玩家(gamer)
给定一个序列 ${a_i}$,统计有多少个排列 $p_1,\dots,p_n$ 对于任意 $i$ 满足 $p_i=a_i$ 或 $p_{p_i}=a_i$。 $1\leq n\leq 10^5,1\leq a_i\leq n$ $\texttt{2s/512MB}$ Sol 首先考虑一个满足条件的排列 $p$,一定会构成若干个环,使得每个点必然走一…
P3349 [ZJOI2016]小星星
题目链接:P3349 给定一棵 $n$ 个节点的树和一个 $n$ 个节点的图,要求为树上的每个节点映射到一个图上的节点(双射),且要求树上边对应图上也必须有相应的边,求方案数。 $n\leq 17$。 Sol 考虑朴素 DP,设 $F[i][j][k]$​ 表示将 $i$ 映射到 $j$,且 $i$ 的子树内的映射集合为 $k$ 的方案数。 瓶颈在…
浅谈容斥原理
容斥原理 定理: 设有 $n$ 个集合,第 $i$ 个集合为 $A_i$,则所有集合的并集可以表示成如下形式:$$|A_1\cup A_2\cup \cdots\cup A_n|=\sum_{i=1}^n (-1)^{i-1}\sum|A_1\cap A_2\cap\cdots\cap A_i|$$ 证明: 假设元素 $a$​ 被 $x$​ 个集合…