做那么多题有啥用啊，人还是那么傻

50/50

3190: [JLOI2013]赛车

半平面交大法

3926: [Zjoi2015]诸神眷顾的幻想乡

给一棵树，节点有字符，问树上不同字符串数（叶子节点不超过20）

从叶子节点遍历，然后插入SAM中，复杂度 $O(20n)$

4584: [Apio2016]赛艇

n个数，每个数有范围，求不同方案数使得数列递增

离散化后分成几段，每段用一个DP来处理，复杂度 $O(n^3)$

1862: [Zjoi2006]GameZ游戏排名系统

平衡树练习题

3991: [SDOI2015]寻宝游戏

Set按dfs序从小到大维护，然后加减一个点就拿出两边的点来更新答案

1855: [Scoi2010]股票交易

设 $F(i,j)$ 表示第i天还有j个股票的最高利润，然后DP一发，再来个单调队列优化就变成 $O(n^2)$

4008: [HNOI2015]亚瑟王

设 $F(i,j)$ 表示第i张牌还有j轮在进行的概率，然后每一张牌枚举是哪轮使用的，$O(n^3)$，等比数列算一发就变成 $O(n^2)$

3534: [Sdoi2014]重建

先把所有路毁了，然后算重建的概率建图（$\frac{p}{1-p}$）然后就计算生成树矩阵

2753: [SCOI2012]滑雪与时间胶囊

最小树形图

朱刘算法会TLE，所以要利用题目的一个性质，按高度排一下然后MST一发就可以了

1564: [NOI2009]二叉查找树

权值离散化，由于权值可以是实数，所以我们也不用理会“权值互不相同”这个条件了

然后中序遍历也是不变的，所以直接设 $F(l,r,w)$ 表示区间 $[l,r]$ 所有点权值不小于 $w$ 的最小代价

2876: [Noi2012]骑行川藏

拉格朗日数乘法

$$\begin{align}F(V, \lambda)& = f(V) + \lambda (g(V) - E) \\& = \sum_{i=1}^{n} \left( \frac{s_i}{v_i} + \lambda k_i s_i ( v_i - v_i' )^2 \right) - \lambda E \\& = \sum_{i=1}^{n} \left( \frac{s_i}{v_i} + \lambda k_i s_i v_i^2 + \lambda k_i s_i {v'}_i^2 - 2\lambda k_i s_i v'_i v_i \right) - \lambda E \\\end{align}$$

解出偏导方程，得到 $2 \lambda k_i v_i^2 (v_i - v'_i) - 1 = 0$

然后发现 $g(V)$ 关于 $\lambda$ 单调，就可以二分 $\lambda$ 求极值了，$v_i$ 也可以牛顿迭代法求

2433: [Noi2011]智能车比赛

预处理出两矩形的交界，上下界和矩形四角作为节点，然后在节点间连边跑最短路

2109: [Noi2010]Plane 航空管制 & 2535: [Noi2010]Plane 航空管制2

首先第一问拓扑图排序，然后对于第二问就枚举位置，将图反过来，每次取距离限制最近的合法解，直到不能取了此时即为答案，复杂度 $O(n^2)$

2878: [Noi2012]迷失游乐园

这把概率DP扔到基环树上也是服气（然后我就卡题了（你干嘛不扔到仙人掌上去啊

首先先处理出树上向下走直到叶子节点的期望长度

$$down[x]=\frac{\sum (down[y]+len(x->y))}{son[x]}$$

然后处理向上走然后走到叶子节点的期望长度

$$up[x]=len(x->f) + \frac{son[f]*down[f]-down[x]-len(f->x) + up[f]}{son[f]-1+1}$$

当然我们要先计算环上的点的数值，这个可以在环上枚举起点+方向+终点算出期望长度，然后对于与环相连的非环点，向上移动期望长度为

$$up[x]=len(x->f) + \frac{ son[f]*down[f]-down[x]-len(f->x) + up[f]*2 }{son[f]-1+2}$$

然后答案就出来了

$$ans=\sum_{i=1}^n \frac{down[i]*son[i]+up[i]}{son[i]+1}$$

2436: [Noi2011]Noi嘉年华

设 $num(i,j)$ 为包含在区间 $[i,j]$ 中的区间个数

$pre(i,j)$ 为在区间 $[0,i]$ 中放入 $j$ 个区间到 $B$ 后，最多能放入 $A$ 的个数

$suf(i,j)$ 为在区间 $[i,+\inf)$ 中放入 $j$ 个区间到 $B$ 后，最多能放入 $A$ 的个数

然后设个 $g(i,j)$ 表示一定要将 $[i,j]$ 分在同一段的最优答案

$$f(x,y)=min(x+y,pre(i,x)+suf(j,y)+num(i,j)),~g(i,j)=max(f(x,y))$$

$O(n^4)$，发现当 $i,j$ 确定的时候 $y$ 是随 $x$ 单调的，然后就变成 $O(n^3)$

1563: [NOI2009]诗人小G

证明决策单调后（这步我跳过）就可以发现决策区间是不断在向右移动的，那么我们就可以弄个堆维护一下决策区间的单调排列然后每次取最优的即可

1270: [BeijingWc2008]雷涛的小猫

水DP

2338: [HNOI2011]数矩形

矩形条件：对角线长度相等且中点重合

两两枚举端点连线，然后满足条件的线段对拿出来算最大面积

1861: [Zjoi2006]Book 书架

Treap

1063: [Noi2008]道路设计

首先我们通过树链剖分都可以直到答案不会超过 $log_2n$，然后就可以设 $F(x,a)$ 表示点x的不便利度为a时的方案数

当然需要考虑当前点在重链的哪里，这个可以记录下前往儿子的边上属于重链的数量

当然有可能答案模完变成0了，所以多开个布尔数组表示当前状态到达没

2432: [Noi2011]兔农

首先这玩意是有循环节的，模 $K$ 意义下的循环节长度最多为 $6K$，所以看是否无限循环就可行了

得到了若干的阶段，我们会发现阶段数最多也只有 $K$ 个，然后我们在来看阶段是否有循环

好了我们现在知道要进行多少次了，操作什么的用矩阵代替吧，每个阶段用矩阵代替，阶段循环也合成一个矩阵，然后就矩阵快速幂了

2007: [Noi2010]海拔

1001做法

但是上面那题是双方向都一样代价的，对于此题我们就要多考虑不同向的边权设置问题

1492: [NOI2007]货币兑换Cash

用个平衡树维护最优决策凸壳（说起来很简单然而被set坑了

4103: [Thu Summer Camp 2015]异或运算

你看看它其中一维怎么那么小啊

那就建 $n$ 棵主席树然后合在一起找最大值

4104: [Thu Summer Camp 2015]解密运算

首先我们考虑出 $O(n^2)$ 的解密

就是你从初始条件可以知道开头和末尾的对应关系，然后整体往右平移+排序，就得到了长度为3的对应关系，以此类推即可

然后我们为什么每次都要得到所有长度相等的对应关系呢？直接拿开头的那个就可以了吧，然后就变成 $O(n)$

3238: [Ahoi2013]差异

SAM建出来什么事都没有

1093: [ZJOI2007]最大半连通子图

Tarjan缩点然后找最长链……

1146: [CTSC2008]网络管理Network

首先没修改的话，预处理出每个点到根的主席树出来，询问就 $T(x)+T(y)-T(lca(x,y))-T(H(lca(x,y)))$

有修改的话就单独为修改开带修改的主席树，下标为dfs序，询问加上这部分即可

4105: [Thu Summer Camp 2015]平方运算

区间平方操作……

然而数据范围将P都扔给你了，我们会发现将平方情况做成图之后会发现它是由多个基环外向树构成的，树深度不超过11，环的最小公倍数也不超过60

然后就每个节点开60个值，平方几次就移动几次，标记还可以永久化

1494: [NOI2007]生成树计数

首先我们把状态压一下，发现可行状态数最多才50+，然后经过一番恶心的求转移矩阵后就可以矩阵快速幂了

2437: [Noi2011]兔兔与蛋蛋

先判断是否必胜必败，看这个点是否被匹配到或者是非必须匹配点，满足则为必败

然后看一轮操作下来假如有把原图的最大匹配数-1的话即为正确移动

3243: [Noi2013]向量内积

首先假如无解的话，将这两个矩阵相乘得到的矩阵 $C$ 除了对角线其余都非1，对于 $K=2$ 是能求出矩阵来的

然后我们随机个向量 $G$，假如 $G*A*B=G*C$，那么就能大概率猜测其无解，否则也能知道0出现在哪里，然后知道一个了枚举另一个就可以求得0出现的位置了

那么 $K=3$ 呢？将维扩充成 $n^2$ ，每一位的值为 $A_i*A_j$ 然后就会发现C中不会出现2了，接下来同理

1867: [Noi1999]钉子和小球

设碰到每个钉子的概率，然后从上往下转移即可

1408: [Noi2002]Robot

政客和军人就奇偶讨论一发，然后用总人数减去前两个就能得到学者人数了，总人数由欧拉定理可以知道为值减一

1416: [NOI2006]神奇的口袋 & 1498: [NOI2006]神奇的口袋

证明x大小无关怎么设都行（保证大小关系不改变），y的相对顺序也无关（那就不用保证大小关系不改变了），然后就直接模拟

1509: [NOI2003]逃学的小孩

答案一定在树的直径上啊，然后找出两端点再各自dfs一遍出来每个点离两端点的较近距离

3241: [Noi2013]书法家

从左到右分成11种状态然后分阶段dp

1495: [NOI2006]网络收费

设 $F(i,a,S)$ 表示节点i管辖内有a个A类且祖先状态为S的最优值，空间会爆炸所以不能开三维数组，将其全部压缩成一维也可以

1650: [Usaco2006 Dec]River Hopscotch 跳石子

二分答案+贪心

1613: [Usaco2007 Jan]Running贝茜的晨练计划

DP

1501: [NOI2005]智慧珠游戏

DXL大法

2659: [Beijing wc2012]算不出的算式

几何证法，当 $p=q$ 时输出 $\frac{(p-1)(q-1)}{4}+\frac{q-1}{2}$，否则输出 $\frac{(p-1)(q-1)}{4}$

3156: 防御准备

啊裸斜率优化

4602: [Sdoi2016]齿轮

你可以取个对数乘除转加减，也可以longdouble，我选择后者

4590: [Shoi2015]自动刷题机

二分答案然后直接模拟判定即可

2395: [Balkan 2011]Timeismoney

最小乘积生成树

2754: [SCOI2012]喵星球上的点名

连在一起SA，然后倍增找出字符串对应的SA区间，然后在这区间询问出现了多少种子串，这个可以用主席树维护（或者离线+树状数组）

数据水，能AC自动机或SA暴力艹过去

3571: [Hnoi2014]画框

最小乘积套个KM