开个坑……

50/50

2257: [JSOI2009]瓶子和燃料

给 n 个数，求大小为 k 的子集的$Maxgcd$

从 1 到 $sqrt(n)$ 枚举小约数求所有约数（Wrong：自己跑去筛质数了）然后map加完才去统计（Wrong：为了记忆化搜索每次加完都查一遍结果 TLE 了）

2245: [SDOI2011]工作安排

啊裸费用流

3240: [NOI2013]矩阵游戏

把操作弄成矩阵（其中右边一列一直都是 0 和 1 可以省略）

$$A= \begin{matrix} a & 0 \\ b & 1 \\ \end{matrix}$$

$$B= \begin{matrix} c & 0 \\ d & 1 \\ \end{matrix}$$

然后将所有操作合在一起就成了$(A^{m-1}B)^{n-1}A^{m-1}$

当 $a = 1$ 时 $n\mod{p}$，否则 $n\mod{p-1}$

证明：$\sum A^i \equiv 0 \pmod {p}(0 \le i \le p-2)$

m 也这么取一下模，然后快速幂搞搞

1493: [NOI2007]项链工厂

线段树维护，全局翻转用个全局标记维护，这样其他操作就要看左右了

注意全局询问段数的时候，段数=1且右端等于左端的特殊情况（段数此时不能减1）

2333: [SCOI2011]棘手的操作

合并线段树

全局修改依旧全局变量，开个堆实现询问全局最大值

（Add：其实可以离线操作完使得同个联通块的点一直位于一段区间内，这样就能扔掉一个 $logn$ 了）

3675: [APIO2014]序列分割

斜率优化一下DP

2286: [SDOI2011]消耗战

虚树

先预处理出倍增要用的 H 和 D 数组，可以求某点的根和某段路径的最小值

然后虚树处理就可以

（Wrong：邻接表我每次询问都清空，导致复杂度爆炸变成 $O(mn)$）

1407: [NOI2002]Savage

数论+线性同余

枚举 M，一开始 $M=max(c_i)$，然后判断合法性就解一下线性同余

（Wrong：break 只跳出第一层循环，后来才知道能用 goto 语句）

3529: [SDOI2014]数表

设$g(i)$为在询问范围内$gcd(x,y)=i$的个数

$$\begin{align} ans & =\sum F(i)*g(i) \\ & =\sum F(i)\sum_{i|d}\mu(d/i)[n/d][m/d] \\ & = \sum_d [n/d][m/d] \sum_{i|d} F(i)\mu(d/i) \end{align}$$

然后就前缀和处理$\sum_{i|d} F(i)\mu(d/i)$，枚举$i$再枚举倍数$d$更新

然后就把询问离线按$A$排序，不断选出符合条件的$F(i)$更新，前缀和就用树状数组维护

1056: [HAOI2008]排名系统

套个Splay就完事了

1898: [ZJOI2005]Swamp 沼泽鳄鱼

算出个周期，弄个矩阵快速幂就完了

1071: [SCOI2007]组队

复制成两组，分别按$sum=A*height+B*speed$和$height$排序

然后枚举mins，在枚举minh的时候就可以扫过sum在合法范围内的人，若这些人的speed也符合要求则累加答案；然后扫过height离开合法范围的人，若这些人的speed符合要求则减去答案

1562: [NOI2009]变换序列

根据图建二分图，然后匈牙利

2115: [WC2011]Xor

给无向图求最大xor路径

先dfs找出所有简单环，维护线性基，然后随便找条路径，利用线性基使得xor最大

4010: [HNOI2015]菜肴制作

给拓扑图，求拓扑序列，要让点1提早出现，有多者满足前条件时点2提早出现，有多者满足前者条件时点3提早出现……

建反图然后求最大字典序的答案，逆序输出

2563: 阿狸和桃子的游戏

无向图，每个人轮流取点染色，最后的得分为点权+两端同颜色的边权，求最优博弈下的最小分差

边权拆给两个点，每个点 $e_i/2$，然后排个序，最优策略是每次选取最大价值的点

1187: [HNOI2007]神奇游乐园

求总和最大的回路

插头DP初探

2657: [ZJOI2012]旅游(journey)

三角剖分的话，答案就是将块看成点后形成的无向图的最远点对，建图后两次dfs

我不清楚是不是求任意无向图的最远点对都可以用求树直径的方法求

3573: [HNOI2014]米特运输

读题难系列

一个点确定的话，其余的点也就纷纷确定下来了，所以枚举不改变的点，求出根此时的值，然后排序取出现最多次的就行

1978: [BeiJing2010]取数游戏 game

水DP

（Wrong：求一个数的质因数分解不要dfs，求多个数的质因数分解弄个$O(n^{1.5})$的普通质数筛法）

2229: [Zjoi2011]最小割

求无向图任意两点对的最小割

首先无向图最小割最多有 $n-1$ 个，而且不会互相分割

所以求出一个点集的全局最小割后，这个点集会被分成两块，递归计算两个子点集的最小割

3236: [Ahoi2013]作业

长度 $n$ 数列，$m$ 次询问，每次询问某个区间的位于 $[a,b]$ 的权值和以及权值个数

莫队+树状（或许还有其他解法）

3876: [Ahoi2014]支线剧情

有下界费用流

求个最小费用可行流出来就行

3576: [Hnoi2014]江南乐

$n$ 堆石子，每次可以选出一堆均分，求先后手必胜

首先一堆石子确定好均分堆数后所得到的堆的情况是确定的，关键是SG值怎么求（直接暴力求太慢）

若当前石子个数为 $k$，然后分成 $a$ 堆，若 $k/a=k/(a+2)$ 则无需讨论分成 $a+2$ 堆的情况

2595: [Wc2008]游览计划

斯坦纳树

1835: [ZJOI2010]base 基站选址

线段树优化DP

设 $F[i][k]$ 为当前最右的基站建立在第 $i$ 个上且建立了 $k$ 个的最小代价，然后新加一个点就判断有没有被覆盖到然后区间更新，这步用线段树玩

3932: [CQOI2015]任务查询系统

树状套主席树

2337: [HNOI2011]XOR和路径

高斯消元

按位考虑，设 $F[i]$ 表示从i点出发到终点的期望值，列个xor方程组高斯消元就可以解了

1212: [HNOI2004]L语言

DP，然后弄个Trie实现转移就行

3140: [Hnoi2013]消毒

首先我们可以贪心知道用1*b*c或a*1*c或a*b*1是最优的，然后把最小的一维度当做高（最多17）压成个二进制状态，枚举我们要取走哪些层，将没取的层压成一层然后二分匹配

2820: YY的GCD

数论，求$\sum [gcd(i,j)=prime](1 \le i \le n,1 \le j \le m)$

2806: [Ctsc2012]Cheat

广义SAM+DP单调优化

二分答案后配合SAM转移，然后决策区间是只往右面移动的就可以单调优化

3052: [wc2013]糖果公园

树上带修改莫队

4129: Haruna’s Breakfast

树上带修改莫队

然后mex就用分块处理一下，$O(1)$ 修改，$O(\sqrt n)$ 查询

4507: [Usaco2016 Jan]Mowing the Field

离散化完用set的暴力算下交点

4506: [Usaco2016 Jan]Fort Moo

算完每个格向右向下的最大延伸长度，然后枚举左上右上两格，再往下延伸计算，加个最优性剪枝

4525: [Usaco2016 Jan]Angry Cows

二分答案

4519: [Cqoi2016]不同的最小割

同BZOJ2229（然而求出最小割树还能更快）

4521: [Cqoi2016]手机号码

数位DP

4523: [Cqoi2016]路由表

Trie建完弄个单调栈就行了

4524: [Cqoi2016]伪光滑数

搜索+堆，取最大的数然后修改后扔进堆里面

4522: [Cqoi2016]密钥破解

Pollard_rho质因素分解

1468: Tree

点分治初探

4518: [Sdoi2016]征途

将 $n$ 个数分成 $m$ 段，使得方差最小

斜率优化一发

4516: [Sdoi2016]生成魔咒

每次新加一个字符，求不同子串数

SAM，设新加的点为 $a$，答案每次累加上 $len[a]-len[fail[a]]$，字符集巨大所以用map储存儿子

4517: [Sdoi2016]排列计数

求恰好有 $m$ 个数在原位置的全排列数

组合数学，枚举稳定个数的位置 $C(n,m)$ 再乘上错排数（转成循环节个数可以得到递推公式 $F(i)=(F(i-1)+F(i-2))*(i-1)$

4514: [Sdoi2016]数字配对

首先这是个拓扑图，然后可以二分染色，就可以连源汇做费用流，每次找费用最大的增广路，直到费用最接近0时停止

☆4513: [Sdoi2016]储能表

求$\sum max(x^y-k,0)~(0 \le x \le n-1,~0 \le y \le m-1)$

我居然看不出这是个数位DP。。。乙烷

设置状态 $F[len][a][b][c]$ 统计异或和减去 $k$ 的总和，其中 $len$ 指前几位，$a=0$时目前 $x<n$，$b=0$时目前 $y<m$，$c=0$时目前 $x^y>k$，当$a,b,c$ 不为0时则无限制，同理设置状态 $G[len][a][b][c]$ 表示方案数

然后就转移咯

☆4515: [Sdoi2016]游戏

数据结构

标记下传新姿势

我们把添加的数看成是一个等差数列（一次函数），当有两个一次函数标记出现在一个区间内的时候就判断一下要留下哪个

假如区间最值函数是由两个函数共同构成的，那么我们看各个函数在哪段区间是最值

设两段函数，前者在 $[l,x)$ 优过后者，后者在$(x,r]$ 优过前者，那么我们看 $x$ 和 $mid$ 的大小关系

假如 $[l,mid)>[l,x)$ 我们就把前者往下传递，同理后者，递归传递

单次处理复杂度是链剖+线段树+标记下传的 $O(log^3n)$

3751: [NOIP2014]解方程

……取一个万级单位的模数 $A$ 和十亿级的模数 $B$，前者先预处理出模 $A$ 时是否为0，判断时若前者符合则判断后者模数。