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

P4169-CDQ分治/K-D tree（三维偏序）-天使玩偶 这是一篇两种做法都有的题解 题外话 我写吐了…… 本着不看题解的原则，没写（不会）K-D tree，就写了个cdq分治的做法。下面是我的写题步骤： 想着树状数组维护不了区间最值，于是写了线段树，因为一个**的错误调了几个小时； cdq只写了两个方向。显然是错的，因为没考虑修改。所以挂了； 加上另外两个方向，...

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

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

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 建出圆方树。如何判断两点在删去一个点后在树上的连通性？当且仅当被删去的点在两点间的路径上。根据圆方树的性质，如果被删点在一个点双连通分量中，它是符...

P4827 [国家集训队] Crash 的文明世界 题意 求出对于树上每个点 \(x\) 的 \(\sum_{u=1}^ndis(x,u)^k\)。所有边长为 1。 思路 根据斯特林反演： \[ m^n=\sum_{j=0}^n\begin{Bmatrix}n\\j\end{Bmatrix}C_m^jj! \] 可以得到： \[ \sum_{i=1}^n\sum_{j=0}...

P5042 丢失的题面 顺序：10 - 1 - 7 - 8 - 9 - 4 - 5 - 6 - 2 - 3 Point 10 读入，特判，输出。 读入的英文意思是让选手输出自己的程序本身，这个题的确存在，但是这题并没有 SPJ ，所以特判一下输出输出文件就好了。 C++ 的atoi函数可以让读入的字符串变成数字以完成其他点的任务。 Point 1 我和其他聚铑做这个点的过程...

P5110 块速递推 题意 多次询问，求数列 \[ a_i=\begin{cases}233a_{i-1}+666a_{i-2} & i>1\\ 0 & i=0\\ 1 & i=1\\ \end{cases} \] 的第 \(n\) 项在 \(\mod 1e9+7\) 意义下的值的异或和。 思路 首先这个数列是一个广义斐波那契数列。对于广义斐波...