考完NOIP完就突然失去做题的动力了……

接下来是要奋战GDKOI，也就是省选难度

加油吧（说着说着打开了Osu

现在已完成：

50/50

1052: [HAOI2007]覆盖问题

给N个点，用三个边长为x的正方形覆盖全部点，求x的最小值

二分答案+搜索，首先将第一个放在四角，然后第二个也是，最后判断第三个能否全覆盖

1050: [HAOI2006]旅行comf

求“最大比最小比值最小路径”

就跟“最大减最小差最小路径”差不多，也是边排序完一条条加，用并查集维护图的连通性

★1049: [HAOI2006]数字序列

先对数据处理，每个数减去其下标，一问就被弄成求最长不下降子序列

然后二问就要DP了，一问的转移用邻接表保存下来，二问的DP就可以以此转移

对于子序列两个数$A,B(A \le B）$之间的区间的数，要不全部弄成A，要不全部弄成B，要不找个中分点，左边弄成A，右边弄成B。可以证明其中有一种方案是最优的

★2466: [中山市选2009]树

高斯消元解xor方程组

3505: [Cqoi2014]数三角形

一个N*M的网格图，求有多少三角形

$Ans=C^3_{(n+1)(m+1)}-三点共线对数$，斜线上的就神奇的枚举姿势，复杂度$O(n^2)$

1022: [SHOI2008]小约翰的游戏John

胜利条件相反的Nim游戏

假如全部为1，则看1个数（奇数先手败，偶数后手败）

否则看Nim，如果$Nim \neq 0$则后手败，否则先手败（跟原Nim游戏相反

3930: [CQOI2015]选数

求在$[L,H]$的区间中选取n个数使得他们的gcd为k的方案数

容斥原理，设F[i]表示$gcd=k*i$的方案数，$F[i]=(H/i/k-L/i/k)^n-F[2*i]-F[3*i]-F[4*i]……-(H/i/k-L/i/k)$（这步是减去全部数都一样的方案），假如$[L,H]$包含k的话方案数+1

或者用莫比乌斯做也行

2760: [JLOI2011]小A的烦恼

就模拟

2763: [JLOI2011]飞行路线

分层图最短路

★2746: [HEOI2012]旅行问题

给N个串，每次询问指定两个串的前缀，求其最长公共后缀且这个后缀是某个串的前缀

建立AC自动机和Fail树，对于询问的两前缀找到结点，答案就是两结点在Fail树上的Lca

首先，保留加油站的点，其余去掉（第一次分层图最短路

然后第二次分层图最短路（怎么觉得自己一直在口胡

然后在注意一下细节什么的就可以辣（没说到重点好像

4027: [HEOI2015]兔子与樱花

从下往上贪心，能删的子节点就删

2342: [SHOI2011]双倍回文

回文树，建完遍历Fail树，找双倍回文

★4028: [HEOI2015]公约数数列

给你一堆数，每次操作可以修改一个数，每次询问某个前缀（最小下标）能满足gcd*xor=给定值

分块，修改的时候维护块内前缀gcd和前缀xor和整块的gcd和xor。查询的时候假如当前块的前缀gcd都相等，则由公式可以反推出自己所需的块内前缀xor值，二分查找即可；如果前缀gcd在块内有变动的话就直接暴力查询。

3613: [HEOI2014]南园满地堆轻絮

二分答案+贪心

3629: [JLOI2014]聪明的燕姿

搜索。若一个数的质因数分解为$$x=p_1^{a1}+p_2^{a2}+p_3^{a3}+……$$

则约数和为$$x=(1+p_1+p_1^2+……+p_1^{a1})*(1+p_2+p_2^2+……+p_2^{a2})*……$$

可以枚举质数p，采取DFS的方式求出所有值

★3612: [HEOI2014]平衡

整数划分，求n个数划分为m个互不相同的数且最大不超过k的数的方案数

令f[n][m]表示n个数划分为m个互不相同的数且最大不超过k的数的方案数

如果最小的数是1，等价于将最下方一排砍掉的方案数，即f[n-m][m-1]

如果最小的数不是1，等价于将最下方一排砍掉的方案数，即f[n-m][m]

但是这样求出的是最大不超过k+1的方案数，因此我们还要减掉最大等于k+1的方案数

最大等于k+1的方案数等价于将最右一排砍掉后最大不超过k的方案数，即f[n-k-1][m-1]

故有f[n][m]=f[n-m][m]+f[n-m][m-1]-f[n-k-1][m-1]

于是分是否取走中间的质点两种情况讨论，每次枚举左右的总和，枚举左右拿走的质点数即可

2028: [SHOI2009]会场预约

STL题，弄个set就可以维护了，又短又好写

★2744: [HEOI2012]朋友圈

求最大团

建立反图，最大团变成最大独立集。枚举A国选择的人，与A国有相连的B国人去掉；B国人通过xor自动分成两类，建立二分图跑最大独立集

顺便知道了如何通过位运算求一个二进制数的1的个数

3166: [HEOI2013]Alo

可持久化Trie

先建立可持久化Trie（把每个数的二进制看成字符串）然后对于非最大数，查找xor后最大的值，范围从左边比当前值大的第二个数到右边比当前值大的第二个数

3192: [JLOI2013]删除物品

怎么做都可以

1067: [SCOI2007]降雨量

就是各种判断，其中求区间的最小值用log算法

Mistake 区间最小值暴力求TLE了QwQ

1068: [SCOI2007]压缩

区间DP，$F(i,j)$表示前i位且最右边的R的位置为j的最短压缩长度

1072: [SCOI2007]排列perm

数位DP，对于计算重复的数，设某个数字出现了A次，最后除以$A!$就行了

★1079: [SCOI2008]着色方案

状态设置比较神奇，$F(o,s1,s2,s3,s4,s5)$表示剩i格没涂的颜色有$si$种，且上次涂的颜色现在剩o格的方案数

1087: [SCOI2005]互不侵犯King

状压DP

1088: [SCOI2005]扫雷Mine

确认第一二格就能推出剩余的格子

1089: [SCOI2003]严格n元树

设$F(i)$表示深度不大于i的严格n元树，推下公式，$F(i)=F(i-1)^n+1$，答案就是$F(d)-F(d-1)$

Mistake 没注意d=0的情况

1084: [SCOI2005]最大子矩阵

状压DP，手推公式就行

1074: [SCOI2007]折纸origami

对于穿孔位置，求$2^n$个可能的孔的位置，去重后一个个模拟着折，统计一下最后的确出现在穿孔位置的孔的位置，总数即答案

1090: [SCOI2003]字符串折叠

区间DP

1295: [SCOI2009]最长距离

枚举起点跑最短路，不超过T的就是可达的

1263: [SCOI2006]整数划分

高精度，能分3出来就分3出来，直到n<=4就直接乘上去

1085: [SCOI2005]骑士精神

搜索+剪枝

1296: [SCOI2009]粉刷匠

就一遍$O(n^3)$的DP

1853: [SCOI2010]幸运数字

把所有范围内的68数搜出来，结合容斥计算

Mistake DFS计算容斥的时候是从小到大搜索的，TLE，应改成从大到小

1856: [SCOI2010]字符串

n个1m个0的二进制数，任意前缀的1的个数不少于0的个数，求满足条件的二进制数个数

将1看作向量$(1,1)$，0看做$(1,-1)$，起点为$(0,0)$，终点为$(n-m,n+m)$，且移动路径不经过$y=-1$的方案数

合法方案数=总方案数-非法方案数=$C_{n+m}^{n}-C_{n+m}^{n+1}$

1857: [SCOI2010]传送带

华罗庚选优法，三分套三分

1858: [SCOI2010]序列操作

标准线段树

Mistake 维护区间修改和区间取反信息的时候没考虑优先级的差别

1854: [SCOI2010]游戏

二分图匹配

2335: [SCOI2011]飞镖

耗智商脑跑题，我自己算了个两元一次方程的解的范围

Mistake 三个10^9乘在一起爆longlong

1876: [SDOI2009]SuperGCD

更相减损（大数GCD）

分三种情况：如果两数能整除2，则gcd*2，两数/2；其次谁能整除2就/2；最后大数减小数

1878: [SDOI2009]HH的项链

随便莫队

或者离线+树状数组，询问按左端点排序，初始每种颜色的第一个点打标记，当扫过有标记的点时将标记移动到下一个同颜色的点，维护前缀和。

1877: [SDOI2009]晨跑

裸费用流

1875: [SDOI2009]HH去散步

由于不能返回走，则将边的两向各设为点，然后矩阵乘DP

1228: [SDOI2009]E&D

求出子游戏的Sg函数是难点：$Sg(a-1,b-1)=k_Min(((a-1)\;or\;(b-1))and\;2^k=0)$

1227: [SDOI2009]虔诚的墓主人

离散化之后坐标排序完按行(y)统计，需树状数组维护前缀和

1235: [SDOI2009]细胞探索

FloodFill一遍，找出细胞核（四联通且只与一个四联通空块相邻）细胞壁（八联通）细胞质（四联通且只与一细胞核和一细胞壁相邻且不与边界相邻），然后就容易了

1879: [SDOI2009]Bill的挑战

首先先预处理出任意位置选任意字母所能匹配的字符串集（二进制），然后DP，$f(i,S)$表示答案串前i位能匹配的字符串集为S的方案数