Link 这个题有一个很特殊的点，就是最大值不会超过28，可以想一下最多可以合并多少次。 那么常规的区间dp是不能使用的，就要采用特殊的形式， $dp_{i,j}$ 表示$i$在左边，达到$j$的话的右端点位置 $dp{i,j}=dp{dp_{i,j-1}+1,j-1}$ 然后转移就可以了. #include<cstdio> #incl…

LLink 显然的，答案就是$Cn^m*D{n-m}$ #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #incl…

LLink 本代码没有高精。 首先很容易想到的是，0，1之间互相并不干扰，所以说我们只要分开算0和1的方案数乘起来就可以了。 那么怎么算方案数呢？ 首先可以想到的一点就是，如果我们确定了要放$a$个1的话，只要采用隔板法就可以确定了方案书。 有的可以没有怎么办？先给每一个隔间都放上一个球，答案就是$C{a+n}^{n-1}$ 所以$ans=\sum…

Link 首先很容易想到地一点就是平行的直线可以划分为一组，他们的每一条线是“相同的”，这样我们第一件事情就是计算可以有多少划分方式。 然后该怎样计算最后每一种情况是多少个交点呢？ 我们考虑一下，每一条直线都会和不平行的直线产生交点，这样就可以计算每一条直线地贡献了。 $\frac{n^2-\sum{a_i^2}}{2}$就是答案。 最后统计一下就…

link 首先我们要明白，floyed的本质上是一个dp，那么显然我们要先跑一边floyed，然后进行更新 当我们更新的两个点之间的距离的时候，显然我们改变的是和它们有关的距离，所以只要更新这两个边就可以了. #include<cstdio> #include<iostream> #include<cstring>…

Jennie 用splay维护编号就可以了 如果我们要反转[l,r]，那么这个l，就是区间第l个数 然后splay的中序遍历就是整个区间， 那么显然的就是，我们只要找到第l个数就可以了 也就是所谓的按照排名找数。 找到之后，为了维护中序遍历，把l转到根，r转到l右边（也只能是右边了） 然后根r的左儿子打一个标记就可以了， 就像线段树一样，记得下传并…

[Jennie](P4180 [BJWC2010]严格次小生成树) 很显然，我们只要求出最小生成树以后，把没有用过的边插进去，然后删掉形成的环上的最大值就行了 因为要严格，所以我们还要记录一波次大值。 然后就是树上倍增的事情了。 #include<iostream> #include<cstdio> #include<…

JIsoo 首先根据期望dp搞出dp来， $f_{i}表示在到了第i个镜子还需要的期望天数$ 转移显然. $f_i=pi\times f{i+1}+(1-p_i)\times f_1$ 这也显然，并且没法递推hhhh 让我们从第二项开始化简式子 $\frac{1}{p_1\times p_2...p_i}+....+\frac{1}{p_i}$ 这…

Lisa 问题在于环，显然。 但是怎样建图才能把环搞出来呢？不能建无向图，而且男女要交错 那就一种情况男女，另一种女男 然后就是tarjan的事情了. #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #incl…

JennP3275 [SCOI2011]糖果e 差分约束到底在干什么？ 最短路的基本不等式是$dis_v<=dis_u+edge_i$ 那么要求最大的解要依据这个来建立起来一个图，跑最短路 求最小解要跑最长路，也就是 $dis_v>=dis_u+edge_i$ 然后跑最长路 #include<iostream> #inclu…