Min-Max容斥

Min-Max容斥,也叫最值反演(脑子不够,套路来凑),可以处理一些计数问题。 形式(公式挂光了,救救孩子): $$ Max(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Min(T) $$ $$ Min(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Max(T) $$   本质上是容斥TAT,用反演的角度来看,就是只有当T的size为1且是最大值时才会被计入贡献(等式咕了 这里的Min与Max并一定要是最大值和最小值,只要是在某一种偏序下的两个极端就好了。 基本上的套路大概就是随机选一段子集染色,问期望多久把全集染满——这是Max,就可以转化成对于每一个子集, ...

Codeforces 671D Roads in Yusland

题目链接 题意:给出一棵以1为根的有n个点的树与m条权值为ci的链,满足在链的两个端点的lca是他们中的一个(即这些链都是竖直的),所有节点至少被一条链覆盖,问最少选出权值和为多少的链满足方案,无解则输出-1。   题解:网上的做法大多是按照dfn把链离线之后用线段树维护,比较难写(大概)。然而我在某课件中看到了一种新颖的做法:应用对偶原理,将原问题转化为一个简单(?)的贪心问题,然后就要调很久了简单了很多。   先说对偶原理:对于一个线性规划问题,把它写成标准形式之后,大概是一个系数矩阵与未知数向量 ...

51Nod 1380 夹克老爷的逢三抽一

题目:51Nod 1380 题意概述: $3k$ 个数排成一个圆,每次取出一个数,答案加上它的值,并删去左右两边的数,问答案的最大值 思路: 这个题嘛。。。是在贪心专题里边的啦,那自然是贪心无疑了。然而一开始太naive,想了一个看两眼就会觉得是错误的贪心,就不放出来了qwq。实际上正解大概也算是一个带反悔的贪心(应该算是比较常见的操作了吧)。 先考虑另外一个问题:有一个环上有3k个数,要选出k个不相邻的数,使得他们的和最大。 考虑带反悔的贪心:我们贪心地选取最大的值,当我们选出一个点后,删除其左右的点,并在它的位置上加 ...

UOJ #213 圣杯战争

既然是圣杯战争,那主题图片就放一张fate的图咯 pid:70587790_p0 题目:UOJ #213 题意概述: 给你一个序列,定义一个连续子序列的贡献为这个序列中的最大值,分别求对于每种长度的所有连续子序列的贡献,输出异或和。 思路: 看到这道题,大概就能想到对于每一个节点计算贡献。考虑维护每一个端点所统治的区间,进行一番分类讨论: 令 $ p $ 为 $ r_i – i + 1$ 与 $ i – l_i + 1 $ 中较小的一个,$ q $ 为较大的一个。 对于$ [1, p) $ 中的所有长度,加上 $ a_i \times i $ , 对于 $ [p, q) $ 中的所有长度, ...

Kruskal重构树

前两天打了noi2018网上同步赛,看标算重构树以为是什么高明的dark数据结构,一看还是挺小清新的。 先考虑在做Kruskal的过程中,每次会选取一条当前最优的边并加入生成树。在这个过程中,我们可以加入一个虚节点表示当前的这条边,点权值即为边权。由于一条边只能有两个端点,所以这棵树必然是一棵二叉树,就可以妙妙地维护了啊! 然后这个树有一些很棒的性质,比如说一条边到根的路径上的点权是单调的,两点在图中的最长边的最小值即为两点在重构树上的LCA等等(自己想啦~逃 裸题:bzoj3732 打法自己想想吧233 实在不行可以参考我的 ...

NOI同步赛小结

Day1: 本来想和同学py的,结果临时来了个老师帮我们“监考”,就233了,自己打吧。。 开场先看了一遍题,A没看懂,就看B。B我只发现冒泡排序的交换次数是逆序对对数。。。一看数据感觉不是很正确啊。。就去看C。C长得一副SAM的样子,昨天才听了思路,完全不会写,就又回去看A。 仔细理了一下思路,题面里离线的提示似乎是很明显的,然后套路把询问排序,排序好之后就变成用并查集维护联通块了,复杂度十分稳健,就去写了。看部分分的时候还发现有10分好打得很,就写了个7(大)5(众)分。 这里面还有一个树,我当时想得是求一条链上最 ...

莫比乌斯反演

本来还打算写容斥的,结果不知不觉就过(颓)了好几个月,发现原来容斥如此高妙啊QAQ,那就讲讲比较套路的反演吧。。。 莫比乌斯反演。。。听起来很高明,实际上不算太难吧(逃 首先说他是莫比乌斯反演,总要有个缘由吧。个人感觉就是因为莫比乌斯函数,μ,是他的精髓所在。 先说说μ的定义 当n为无平方因子数且n的标准分解中有偶数个质数,μ(n) = 1; 当n为无平方因子数且n的标准分解中有奇数个质数,μ(n) = -1; 当n为有平方因子数时,μ(n) = 0。   μ(n) = 1 if n is a square-free positive integer with an even number o ...

LCA算法合集

这两天看了看“最近公共祖先”(lowest common ancestors, LCA) 先说什么是LCA 好吧,顾名思义,就是,两个节点的深度最大的公共祖先 比如,上图中 4,7 的 LCA就是 2 , 3,6 的则是 3; 那么怎么做呢? 1.朴素算法(在线) 由较深的节点一直向上走,直到与另一个节点到达同一深度,接着两个节点一起向根走,直到达到统一节点,这个节点就是他们的LCA。 复杂度(对于每次询问):最坏 O(n),平均 O(log n) 代码: [code language=”cpp”] //这就不贴了吧 [/code] 2.Tarjan(离线) 首先把所有询问读入并存储,每 ...

关于BIT。。。

二叉索引树(Binary Indexed Tree 或 Fenwick Tree, BIT),俗称树状数组,是一种十分精妙的数据结构。 先上图: *就是它* 至于它的含义,就是:每个点代表一段区间所包含的信息(sum, min, max, etc.),这段区间的长度取决于当前节点编号的lowbit,也就是二进制下最低的不为零的一位。因为数字再计算机中用补码存储,所以可以很方便的求出lowbit(i) : i & -i。 若要求一段区间*的信息怎么办? 由这段区间的最后一个节点开始,每次向前“跳”lowbit个位置,直到1。 更新? 由这段区间的第一个节点开始每次向后“跳”lowbit个位置,直到n ...