说好寒假要刷题的，结果还是各种颓废。。。

距离KOI还有8天的时间。。。

50/50

1213: [HNOI2004]高精度开根

Python大法好

1211: [HNOI2004]树的计数

Prufer Sequence+组合数 注意特判些特殊情况

1588: [HNOI2002]营业额统计

Treap 裸数据结构

1217: [HNOI2003]消防局的设立

贪心

设每个点的满足度为F[i]，当点i为消防局点时F[i]=2，向上传递时不断-1

当F[i]<-2时则把点i设为消防局

当点i的最大满足度的子树能满足最小满足度的子树，则F[i]等于最大满足度子树-1，否则为最小满足度子树-1

当问题加强至距离为m时，此贪心皆能满足

1218: [HNOI2003]激光炸弹

直接$O(n^2)$做不会TLE。。。

1208: [HNOI2004]宠物收养所

Treap 也是裸题

1207: [HNOI2004]打鼹鼠

最长上升序列

1202: [HNOI2005]狡猾的商人

前缀和+差分序列，然后去跑一遍最短路

1206: [HNOI2005]虚拟内存

离线离散化一发，然后弄个堆

1197: [HNOI2006]花仙子的魔法

DP

n维被m个球截得最多空间数：f(n,m)=f(n,m-1)+f(n-1,m-1)

1196: [HNOI2006]公路修建问题

二分答案+生成树

1485: [HNOI2009]有趣的数列

转化成Catalan数

1483: [HNOI2009]梦幻布丁

链表+启发式合并

1004: [HNOI2008]Cards

Burnside引理+背包+乘法逆元

用背包计算每个置换下的不变染色方案数，然后除法部分用Exgcd求逆元

1486: [HNOI2009]最小圈

分数规划，然后判有没有负环即可（负环直接dfs判会更快

2004: [HNOI2010]Bus 公交线路

矩乘DP

2003: [HNOI2010]Matrix 矩阵

搜索

就先弄出个符合要求的矩阵（先不理最大值最小值的要求，只需满足和为给定矩阵的要求即可

然后通过dfs搜索第一行的值，推出其余格的值的取值范围，若不可能存在解则及时剪枝

2002: [HNOI2010]Bounce 弹飞绵羊

分块即可

1996: [HNOI2010]chorus 合唱队

区间DP

2326: [HNOI2011]数学作业

数位DP，但是位数不同的转移矩阵也不同

2729: [HNOI2012]排队

组合数学+高精度（用Python水）

$$Ans=n!(A^2_{n+1}A^m_{n+3}+2m(n+1)A^{m-1}_{n+2})$$

2730: [HNOI2012]矿场搭建

Tarjan

先求割点，若某双联通分量与两个或以上的割点相连则不用建立安全点，若只与一个相连则建立一个安全点，若没有连则建立两个

2733: [HNOI2012]永无乡

线段树合并

并查集查询是否同一联通块，权值线段树储存同一联通块内的权值，联通块合并就将线段树合并

3123: [SDOI2013]森林

启发式合并+可持久化线段树

求Lca用倍增，设$Lca(x,y)=a$，则$C(x)+C(y)-C(a)-C(h(a))$就可以提出一条链上的权值树

C(a)为点a到根的路径的权值树，用可持久化线段树维护

2728: [HNOI2012]与非

数位DP（稍难）

若有两个二进制位，在所有数中都是一样的，那么他们是不可能变得不一样的，然后数位DP

2734: [HNOI2012]集合选数

构造+状压DP

弄出这种矩阵

$$ \begin{matrix} x & 2x & 4x & ... \\ 3x & 6x & 12x & ... \\ 9x & 18x & 36x & ... \\ ... \\ \end{matrix} $$

以某个数开头，其2和3倍数的数就全部都在表格内了，没出现的数则再将其作为表头……这样就得到了多个表格了，然后状压DP

3142: [HNOI2013]数列

组合数学

$$Ans=\sum n-\sum C_i = \sum n - \sum \sum C_i = m^{k-1}n-m^{k-2} \frac{m(m+1)}{2}(k-1)$$

1066: [SCOI2007]蜥蜴

最大流

△1002: [FJOI2007]轮状病毒

数论

公式：$f(i)=3f(i-1)-f(i-2)+2$

3124: [SDOI2013]直径

随便找一条直径，对于直径上的点，统计只经过非直径边的最远距离，然后对于直径边统计一发

4390: [Usaco2015 dec]Max Flow

裸链剖

4391: [Usaco2015 dec]High Card Low Card

贪心一发，能打则打，不能就出最弱；然后再乱搞一发（我也不知道自己是怎么乱搞的（

4392: [Usaco2015 dec]Counting Haybales

线段树

4393: [Usaco2015 Dec]Fruit Feast

背包完歇歇再背包

4394: [Usaco2015 dec]Bessie

压完状态跑最短路

4395: [Usaco2015 dec]Switching on the Lights

判断四周可以走到的房间哪个灯是开的

4396: [Usaco2015 dec]High Card Wins

4391弱化版

4397: [Usaco2015 dec]Breed Counting

三个树状数组

3533: [SDOI2014]向量集

线段树+计算几何

每个结点维护上下凸包，查询的时候三分查找

3532: [SDOI2014]Lis

最小割

点拆边完最大流，在残余网络中找割边（先看有没有满流，然后看两端是否联通，确定是割边就恢复割边流对全局的影响

3531: [SDOI2014]旅行

每个宗教建一棵动态开点的线段树

1014: [JSOI2008]火星人prefix

二分答案+Hash，用Splay维护Hash

1027: [JSOI2007]合金

先去掉第三维，然后求由A点构成的最小圈包围所有B点

把B点都在右侧的线段权值设为1，其余为无穷大，Flody求最小圈

1036: [ZJOI2008]树的统计Count

链剖

1040: [ZJOI2008]骑士

基环树DP

1058: [ZJOI2007]报表统计

Treap，然而STL可以搞

★△1095: [ZJOI2007]Hide 捉迷藏

线段树（维护括号序列）

见论文《数据结构的提炼与压缩》

1503: [NOI2004]郁闷的出纳员

Treap

3574: [HNOI2014]抄卡组

给N个字符串，包含通配符"*"，询问是否两两匹配

将字符组分成两类：有通配符和无通配符

无通配符的直接判断是否相同（Hash）

有通配符的直接判断前缀后缀是否相同（排个序然后从小到大判断）

无通配符和有通配符之间的话，就看有通配符中被通配符分割的几个小段在无通配符串中是否按顺序出现（Hash或者KMP）

3809: Gty的二逼妹子序列

主席树大法