Year榜#1好难拿。。。

50/50

1057: [ZJOI2007]棋盘制作

DP，最大子矩阵问题；最大子正方形一定在极大子矩阵中

1059: [ZJOI2007]矩阵游戏

二分图匹配

1412: [ZJOI2009]狼和羊的故事

最小割

1411: [ZJOI2009]硬币游戏

★首先，$2^a$次的操作后，每个数的状态只由原先两个数决定；那么把操作分解成若干$2^a$的操作

2656: [ZJOI2012]数列(sequence)

高精度运算烦。。。

我们可以一直维护两个数及其次数并同时除2

1833: [ZJOI2010]count 数字计数

数位DP，入门题

1834: [ZJOI2010]network 网络扩容

网络流

首先跑最大流，然后在残留网络上费用流

1452: [JSOI2009]Count

维护100个二维树状数组

1003: [ZJOI2006]物流运输trans

枚举日期区间跑最短路，然后再来DP

1864: [ZJOI2006]三色二叉树

树状DP，其实只需要理绿色就行

1433: [ZJOI2009]假期的宿舍

最大流，建图什么的挺容易的

1096: [ZJOI2007]仓库建设

斜率优化DP

2324: [ZJOI2011]营救皮卡丘

★首先Flody求各个点之间的最短路（注意$d(i,j)=d(i,k)+d(k,j)$的k不能同时大于i和j），然后建图求最短路径覆盖，费用流的部分

4195: [NOI2015]程序自动分析

并查集

4196: [NOI2015]软件包管理器

链剖

1497: [NOI2006]最大获利

最大权闭合图

1968: [AHOI2005]COMMON 约数研究

☆直接求每个因子的贡献即可（然而这函数能线性筛么。。。貌似可以

1800: [AHOI2009]fly 飞行棋

水题

1265: [AHOI2006]斐波卡契的兔子（kacci）

高精度除法！我&&）&*（&*）%￥#%@#%！@￥##@%！@#￥#@%！￥#

1801: [AHOI2009]chess 中国象棋

DP，设f[i][j][k]表示前i行有j列放了0个炮，k列放了1个炮的的方案数

1406: [AHOI2007]密码箱

平方剩余（模任意数）

将$x^2 \equiv 1 \pmod n$分解成$(x-1)(x+1)=yn$

然后枚举$n$的约数$a$，枚举倍数$k$，设$x=ak+1$或$x=ak-1$，若x有满足条件的则加入set排重

1266: [AHOI2006]上学路线route

最短路+最小割

1786: [AHOI2008]Pair 配对 & 1831: [AHOI2008]逆序对

DP，由贪心可得填的数必定为单调不减，然后DP一发

1787: [AHOI2008]Meet 紧急集合 & 1832: [AHOI2008]聚会

求三次Lca，分类讨论

1789: [AHOI2008]Necklace Y型项链 & 1830: [AHOI2008]Y型项链

可知最终串一定是三字符串之一的子串，枚举最终串讨论

1798: [AHOI2009]Seq 维护序列seq

线段树

1799: [AHOI2009]self 同类分布

枚举模数然后数位DP（加了几个显然的剪枝就#1了

2822: [AHOI2012]树屋阶梯

卡特兰数

1970: [AHOI2005]Code 矿藏编码

DFS+高精度

1264: [AHOI2006]基因匹配Match

最长公共子序列的DP照做，然而对于一个字符最多只有5个匹配点，于是我们先储存起来就可避免$O(n)$的查找，用树状数组维护，降至$O(nlogn)$

1081: [SCOI2005]超级格雷码

如何制造格雷码：递归的时候翻来翻去？？？

1083: [SCOI2005]繁忙的都市

线段树，维护格子之间的连通性

1965: [AHOI2005]SHUFFLE 洗牌

数论

可知第x张牌下次出现的地方为$2x \mod {(N+1)}$

那么第x张牌经过k次洗牌后出现的地方为$2^kx \mod {(N+1)}=L$

L乘个逆元就是x了，求任意数逆元用Exgcd

1082: [SCOI2005]栅栏

二分答案+搜索

剪枝1：能切的话肯定是切长度前x小的

剪枝2：先用较小的木板切较大的所需

剪枝3：如果当前所需的长度和前一个所需的长度相同，那么枚举原料的时候直接从切出前一个的地方开始枚举

剪枝4：如果浪费掉的材料+前x小的总长度>原料总长度，这种方案一定不可行

☆1086: [SCOI2005]王室联邦

块状树（树分块）

DFS一遍，若子树大于B则剪掉，剩余部分全部合并到最后一个块内

1237: [SCOI2008]配对

状压DP，可证每个数所配对的最远距离不超过2，然后状压一发

1293: [SCOI2009]生日礼物

游标卡尺法

1018: [SHOI2008]堵塞的交通traffic

线段树

将一格子的联通情况储存起来，然后线段树维护

1930: [SHOI2003]pacman 吃豆豆

费用流

处理出两两点的偏序关系，然后建图跑网络流

注意，数据点有N个点都在同一位置上的情况，所以要对图进行剪枝

若 a→b 且 b→c 则不用连 a→c 然后每个点的允许经过次数调整为2

1936: [SHOI2004]Rect 矩形

先离散化，然后枚举左下角和右上角（只枚举在矩形角上的）预处理出每个点左右上下沿边界移动的最大距离，$O(n^2+n^2)$

☆1933: [SHOI2007]Bookcase 书柜的尺寸

DP，状态设置得很巧妙

设置状态为$F(i,j)$为第一二层的宽度分别为 i、j 时的最小高度和

3033: 太鼓达人

欧拉回路，直接dfs一遍就行

1935: [SHOI2007]Tree 园丁的烦恼

给N个点，每次询问某个矩阵内有多少个点

离散化后将询问分解成四个前缀矩阵的询问，然后从左到右扫一遍，用树状数组维护

1226: [SDOI2009]学校食堂Dining

DP

将包括自己及其后面7人的状态以及前一个人的位置记录下来，然后在满足每个人的限制下进行转移

2465: [中山市选2009]小球

贪心，将最大价值的球放在分数上界最大的瓶子内

2565: 最长双回文串

回文树，左右各跑一遍，统计每个点往左能走多远，往右能走多远

2456: mode

思考题

相同则累加出现次数，不同则两两消去