隔壁Child正在把之前用学长权限号交的题批量转移中。。。

拿不到Year#1了QwQ

50/50

1000: A+B Problem

看到这题还没写题解我就来充数了（跑

1297: [SCOI2009]迷路

矩阵DP，由于边长最多为9，于是拆边变成各个中间点，就可以矩阵DP了

1934: [SHOI2007]Vote 善意的投票

最小割，将同意的连源点，反对的连汇点，可知一种方案对应一种割，于是求最小割

1019: [SHOI2008]汉诺塔

构造题，与普通的汉诺塔一样得一层层推，然而层与层之间转化不止$x*2+1$那么简单，有可能是$x*3+2$

2749: [HAOI2012]外星人

可知到最后一定是2被分解，所以看分解出来的2的个数

2750: [HAOI2012]Road

最短路，对每个点跑最短路，然后对每个点x统计起点到x的最短路径数（拓扑DP）和x到其余各点的最短路径数（DFS），按边统计一下

2752: [HAOI2012]高速公路(road)

★线段树+概率

求每段路径的贡献，将公式变形，然后用线段树维护$v[i],v[i]*i,v[i]*i*i$的区间和，就可以算了

2302: [HAOI2011]Problem c

DP，可知编号小于i的至少得i个

设$f_{i,j}$表示编号小于i的有j个的方案数，$cnt_i$表示确定编号为i的人的个数，$sum_i$表示编号可以小于i的人的个数 

则$f_{i,j}=\sum_{k=cnt_i}^{j-i+1}f_{i-1,j-k}*C_{sum_i-cnt_i-(j-k)}^{k-cnt_i}$

那个组合数表示现在有$sum_i$个人，$cnt_i$个人已经确定必须选，$j−k$个人已经选完了，在剩下的人中选出$k−cnt_i$个人使其编号为i

2428: [HAOI2006]均分数据

写了个略残的模拟退火

2426: [HAOI2010]工厂选址

枚举工厂，先贪心把煤运往最便宜的地方，然后再来按代价从小到大调整

2298: [HAOI2011]problem a

DP，$F_i$表示名次1-i的最大可确定人数，$Num_{i,j}$表示名次在i至j的人数，则$F_i=F_j+Num_{j+1,i}$

2440: [中山市选2011]完全平方数

数论+容斥，二分答案，转化为求x以内有多少个无平方因子数，$cnt=\sum x/i^2*\mu(i)$

2438: [中山市选2011]杀人游戏

图论，问x个人成功的概率为$1-x/n$，Tarjan缩环后入度为1的点都要询问；假如有个点入度为1但连的点的入度都大于1，则答案减一

4031: [HEOI2015]小Z的房间

生成树计数，Matrix-Tree定理+行列式

做个基尔霍夫矩阵，然后去掉一列一行，求行列式的值（由于模数不为质数，所以行与行之间用辗转相除消元）

2743: [HEOI2012]采花

离线排序，左端点不断移动，维护每种颜色第二左的点的坐标

1225: [HNOI2001]求正整数

搜索，首先质数最多16个，然后就加各种剪枝各种搜索了（可以用log加法代替乘法比较当前值与答案的大小）

2783: [JLOI2012]树

dfs一遍

2768: [JLOI2010]冠军调查

最小割，这跟某道小朋友不肯睡觉的题一样啊

2665: [CQOI2012]编号

$C(5,7)$种状态，然后乱搞

1305: [CQOI2009]dance跳舞

二分答案+网络流

1260: [CQOI2007]涂色paint

DP，$F[i,j]=min(F[i,j-1](s[j]==s[i]~or~s[j-1]),F[i+1,j](s[i]==s[i+1]~or~s[j]),F[i,k]+F[k+1,j])$

1304: [CQOI2009]叶子的染色

树形DP，可以证明取哪个结点做根都一样

3108: [CQOI2013]图的逆变换

若A→B,C→B,A→D，但没有C→D，则为非法图

3295: [CQOI2011]动态逆序对

倒过来执行，然后CDQ分治+树状数组计算逆序对个数

3506: [CQOI2014]排序机械臂 & 1552: [Cerc2007]robotic sort

就Splay

3504: [CQOI2014]危桥

最大流跑一边，路径B的起点终点颠倒再跑一次

3626: [LNOI2014]LCA

树链剖分，转成区间加&区间和

3173: [TJOI2013]最长上升子序列

Treap可以支持

3170: [TJOI2013]松鼠聚会

首先把$max(x1-x2,y1-y2)$改成曼哈顿距离，然后横纵坐标各取中位数

设两点$(x1,y1)(x2,y2)$则其曼哈顿距离为

$$|x1-x2|+|y1-y2|=max((x1+y1)-(x2+y2),(x1-y1)-(x2-y2))$$

3171: [TJOI2013]循环格

费用流

满足条件的情况当且仅当每个点的入度出度等于1，然后就费用流一发

4000: [TJOI2015]棋盘

行的状态最多有$2^6$种，行与行之间的转移矩阵拿去快速幂松松

3999: [TJOI2015]旅游

树链剖分

带有方向的路径询问。。。于是线段树要考虑正反两向，线段树的遍历也要考虑先左子树还是右子树

3226: [SDOI2008]校门外的区间

线段树啊，除了整数多维护$x.5$这种数就行

2037: [SDOI2008]Sue的小球

来回DP，$F[i,j,k]$表示已走过区间[i,j]的最小消耗值，k表示当前在哪一端

2186: [SDOI2008]沙拉公主的困惑

数论，$ans=n!/m!*\varphi(m!)=n!*\frac{p-1}{p}*...$，其中p为不超过m的质数

线性求逆元

$inv[i]=(Q-Q/i)*inv[Q\%i]%Q$

证明：

设$t=Q/i,k=Q\%i$

则：

$$t*i \equiv -k \pmod Q$$

$$t*inv[k] \equiv -inv[i] \pmod Q$$

$$inv[i] \equiv -t*inv[k] \pmod Q$$

$$inv[i] \equiv (Q-Q/i)*inv[Q\%i] \pmod Q$$

3229: [SDOI2008]石子合并

专治这种问题的GarsiaWachs算法

设一个序列是$A[1..n]$，每次寻找最小的一个满足$A[k-1]<=A[k+1]$的$k$（方便起见设$A[-1]=A[n]=\infty$）,那么我们就把$A[k]
$与$A[k-1]$合并，之后找最大的一个满足$A[j]>A[k]+A[k-1]$的$j$,把合并后的值$A[k]+A[k-1]$插入$A[j]$的后面

整个过程一个队列就可以实现

3231: [SDOI2008]递归数列

矩阵快速幂

1951: [SDOI2010]古代猪文

数论，Lucas+CRT

又费马定理可知先求$K\pmod{p-1}$的值再去快速幂即可

由于$(p-1)$不是素数，所以我们先用CRT拆开来，然后用Lucas算结果，再合并起来

2243: [SDOI2011]染色

树链剖分维护即可

2705: [SDOI2012]Longge的问题

数论

求$\sum gcd(i,n)$

枚举gcd的值，$gcd(i,n)=a$的数量为$\varphi(n/a)$（a是n的约数）

2282: [SDOI2011]消防

枢纽路径一定是在直径上，然后在所有极大合法枢纽中找最大值

1221: [HNOI2001]软件开发

经典费用流，以每次使用毛巾作为流量

1222: [HNOI2001]产品加工

DP，$F[o,i]$表示前o件事中第一人花了i小时的时候第二人花的最小时间，o这一维可以空间优化

1223: [HNOI2002]Kathy函数

打表可知满足条件的数，其二进制数都是回文串，然后就是数位DP的事了

1224: [HNOI2002]彩票

搜索，上下界剪枝勉强过得了