P3214 [HNOI2011]卡农 题意 在集合 \(\{1,2,\cdots,n\}\) 中选出 \(m\) 个非空子集满足： 不存在完全相同的两个集合； 每个元素在所有集合中出现次数之和为偶数。 思路 考虑转移，利用容斥方法进行 Dp。设 \(f_i\) 表示选了 \(i\) 个集合满足条件的方案数： 首先，如果确定了前 \(i-1\) 个集合，那么为了满...

P3312 数表 题意 求出 \[ \sum_{i=1}^n\sum_{j=1}^m\sigma(\gcd(i,j))[\sigma(\gcd(i,j))\le a] \] 其中 \(\sigma\) 表示约数和。 思路/推导 考虑没有 \(a\) 的限制的情况。 \[ \begin{aligned} ans&=\sum_{d=1}^{\min(n,m)}\sigm...

平面图 平面图就是所有点的连边可以在平面上不相交的图。这一点可以大概理解成拓扑图的性质，即每连一条边就会将某个区域进行分割——很明显，如果两个点分别处在两个不可达的区域，它们要连边显然是要穿过其他边的。 平面图定理 边数大于点数的三倍减六的图一定不是平面图。即设n为点数，m为边数，有 \[m<=n*3-6\] 关于平面图的其他定理和上定理的证明我不会不过我有大佬博客就不乱搬了...

P3643 [APIO2016]划艇 题意 一个合法序列可表示为一个长度为 \(n\) 的序列，其中第 \(i\) 个数可以为 0 或 \([l_i,r_i]\) 中一个整数，且满足所有不为零的数组成的子序列严格上升。求合法序列方案数。\(n\leq 500,l_i\leq r_i\leq 10^9\)。 思路 朴素动态规划做法为，设 \(f_{ij}\) 表示第 \(i\)...

P4074 [WC2013]糖果公园 树上带修莫队 题意：树上每个点有一种糖果，求\(\sum_c\sum_{i=1}^{cnt_c}v_c*w_i\) 其中c为糖果种类，\(cnt_c\)其为出现次数。 思路 离线树上带修莫队。 先进行树上分块。分块内的询问按照出发点、终止点、询问id优先级依次递减排序。 对于树上莫队，其实就是在欧拉序上莫队。因为欧拉序的性质，即每个节点子树...

P4168 蒲公英 暴力分块思想。分块的思想与莫队相同。它能将时间和空间复杂度均摊XD belong 表示所属区块，num 维护区间颜色出现次数，maxx 维护区间 max 值。查询时只需要比较两端的区块即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474...

P4180 [BJWC2010]严格次小生成树 题意 求出一个无向联通图的严格次小生成树。严格次小生成树的定义为边权和大于最小生成树的边权和但不存在另一棵生成树的边权和在最小生成树和严格次小生成树之间（不相等）。 思路 先求出一颗最小生成树，发现严格次小生成树一定是其断了一条边并加了一条边且边权和的增加量最小。 那么我们继续在最小生成树上做。对于每一条不是最小生成树上的边，求出其两...

P4293 [WC2010]能量场 题意 给你 \(n\) 个粒子，每个粒子有两个权值 \(m_i,c_i\) 每个相邻有序对 \((a,b)\) 会产生 \(m_am_b(c_a-c_b)\) 的贡献。现让你处理两个问题： 找出一个有序对使贡献最大。 找出一个序列成环后贡献和最大。 思路 我们将贡献转化一下： \[ m_am_b(c_a-c_b)=m_ac_am...

P4334 [COI2007] Policija 题意 一个无重边的无向图，每次询问删掉一条边或删掉一个点后两个点是否联通。 思路 连通性问题，我们可以考虑使用广义圆方树解决。 对于删掉一个点的情况： 我们先跑 tarjan 建出圆方树。如何判断两点在删去一个点后在树上的连通性？当且仅当被删去的点在两点间的路径上。根据圆方树的性质，如果被删点在一个点双连通分量中，它是符...

P4494 [HAOI2018]反色游戏 题意 给你一个无向图，图上每个点是黑色或者白色。你可以将一条边的两个端点颜色取反。问你有多少种方法每个边至多取反一次使得图上全变成白色的点。 思路 若任意一个连通块黑色点的个数为奇数那么无解。 先考虑树的情况。发现如果是树，并且黑点个数为偶数，有且仅有一种方式达到目标。然后发现，对于一个无向图，它的任意一个生成树若有解，那么其他非树边无论是...