奇怪的技巧

---

奇怪的技巧(不知道有什么用)

1.很奇怪的平方转化

求子树A的size的期望平方和。 转化为求子树A的期望有序点对个数。

2.树的路径求交转子树和

详情见CF19E&&NOIP2015D2T3

3.按照对角线DP

SRM670左右的一个L3，按照对角线顺序+插头DP。 DP能与不能，需要看后效性的”方向”，如果可以通过顺序来去掉这个后效性，倒也是不错的。

4.特殊问题的边权转点权

有一些题目既有边权也有点权，但是可以通过一些特殊的技巧来转。 比如CC的一道题目: A和B在一个点和边都带权的无向图上选点，如果一条边两个点都被某个人选了，那么这个人得到这条边的价值，如果一个点被一个人选了，那么这个人就能得到这个点的价值。最终求这两个人都想让自己的得分最高的情况下，这两个人的分差。 考虑刚刚的想法，把边权分摊给两边的点权，答案除以二。

5.覆盖问题的分层最短路

PTY贪心的课件里有一个题，我忘记了。 大致思想是，把大的目标状态分成多个子状态，对于同一步能到达的单独状态我们建立一个点跑最短路。<感觉同一个思想并不太容易再出第二次……么？>

6.对于中位数/平均数的二分

题目：求树上路径长度为[L,R]的最大边权中位数。 首先二分答案，然后把边权变成1和-1，转化成求最大值问题。

7.矩阵乘法优化

优化1：

rep(i,n)rep(k,n)if(a[i][k])for(j,n)c[i][j] += a[i][k]*b[k][j];

优化2： 预处理矩阵的 2k ，这样非常滋磁。

---

8.容斥原理常见思路

1.cal(强制违反第i个限制,后面的限制随意,前面的限制不允许违反); 即 f[i]=cal(i)−∑f[j]∗g(j−>i) （任意走的方案去掉中途走到j的方案） 2.强制满足->至少违反 (−1)|S|f(S) 3.至少满足->同时满足 S (其他任意)(−1)|S|f(S) 4.补集转化: 补集的并集 + 交集 = U

9.最大值转最小值：

来自wiki，具体定理我有时间再贴。

10.第k大转 n−k+1 小：

这有什么用嘛……（啪 bzoj 4443：小凹凸的矩阵。 很明显的二分+网络流，但是发现个问题…… 诶我交上去怎么WA了…… 需要强制选N个。 这就需要转成 n−k+1 小。 //我承认我水了一条

11.直截了当的贪心

形如最大k子段和这种东西，我们可以用堆+链表来实现。 这类问题的显著特征是：连续一段。 CF#387Div2D：有两种轮胎，一种夏天的一种冬天的，冬天的有使用时间限制，问最少换几次轮胎。 我们注意到，首先我们可以跑一个最差解，即尽可能省地去用轮胎，然后把相邻两段合并起来。 我们发现这个东西其实并不需要用链表合并，只需要一个堆即可，那么这道题就能解决了。 遗憾的是，自己明明发现了和k字段和一样的性质，但是并没有敢去往贪心的方面去想。 吸取教训，虽然是个NOIP题QAQ

---

数学方面 1.数 ⌊ni⌋ 的数值范围是 n√ 级别的. 2. ∑ni=1i2=n(n+1)(2n+1)6 .[数学归纳法] 3. ∑ni=1i3=(∑ni=1i)2 .[数学归纳法] 4.伯努利不等式: ∏ni=1(1+xi)≥1+∑ni=1xi ,其中 xi>−1 ,且同号。[数学归纳法] 两边同乘 1+xn+1 :

∏i=1n+1(1+xi)≥(1+∑i=1nxi)∗(1+xn+1) 拆开右边的 (1+∑i=1nxi)∗(1+xn+1)=1+∑i=1n+1xi+xn+1∑i=1nxi 发现最后 xn+1∑ni=1xi 肯定是 >0 的，那么就证明完毕了。 4.5flag: 伯努利不等式有什么用？

有用的推论1：若 x>−1 , (1+x)n>=1+nx(n>1) 取等号当且仅当 x=0 .[似乎还算显然吧]有用的推论2： (1+1k)k>2 , [k>1]

5.