进入了省选题时间了。。。

刷的速度越来越慢了。。。

现在已完成：

50/50

3195: [JXOI2012]奇怪的道路

设置状态(x,y,S)表示现在在x点连边至后面的点，且已连边数为y，后面的奇偶状态为S的方案数

★2439: [中山市选2011]序列

你有一个数列S，每次操作可以把某段区间的Si-Sj增加或减少一个数，费用为其改变数大小。求最小代价使得数列满足S1<...<Sx>...>Sy<...<Sz>...>ST（Sy不能改变）（N<100000）

先把数列构造成差分数列，那么操作就变成修改两个数一个加一个减。枚举Sy，然后找左右边分别弄成一段正数+一段负数的最小代价。单调队列优化至\(O(n)\)

2463: [中山市选2009]谁能赢呢？

由多米诺骨牌摆放方案可知n分奇偶讨论就行

2464: [中山市选2009]小明的游戏

转成最短路

2469: [中山市选2010]简单数谜

搜索大法

2467: [中山市选2010]生成树

可以知道要拿n+1条边，且中间的圈一定要拿走至少一条，然后就DP一遍

3997: [TJOI2015]组合数学

DAG中有个D开头的定理，最小链覆盖=最长反链

3996: [TJOI2015]线性代数

给一个N*N的矩阵B和一个1*N的矩阵C，求出一个1*N的01矩阵A，使得\(D=(A*B-C)*A^T\)最大（N<1000）

$$D=\sum_{i=1}^n \sum_{j=1}^n a_i a_j b_{i,j} - \sum_{i=1}^n a_i c_i$$

然后就转化模型，变成一道最大权闭合图的最小割裸题了

3175: [TJOI2013]攻击装置

转化成二分图后求最小点覆盖集，最小点覆盖集=最大匹配

3174: [TJOI2013]拯救小矮人

贪心排序后DP。按A+B从小到大排序（因为越小的让其越先出去）然后F[i]表示现在出去i人后的剩余人的最高高度

4034: [HAOI2015]T2

裸树剖

2748: [HAOI2012]音量调节

水题

2429: [HAOI2006]聪明的猴子

就一道MST

3105: [CQOI2013]新Nim游戏

（拟阵）给定一个集合，求一个最大子集S，使得S的任意子集的xor和不为0

按火柴总数排序后贪心取并维护线性基

3106: [CQOI2013]棋盘游戏

对抗搜索。可以证明假如相邻的话白棋必胜，否则黑棋必胜，且步数最多为3n，然后就记忆化搜索。

1257: [CQOI2007]余数之和

求\(\sum_{i=1}^n k\;mod\;i\)

枚举k/m的数，会发现k%m是个等差数列，然后就\(O(\sqrt n)\)了

2751: [HAOI2012]容易题

就一个快速幂

4004: [JLOI2015]装备购买

（拟阵）有个向量集合，求一个最大子集S，使得S的任意子集的系数向量和（就是设每个向量为\(A_i\)，系数为\(B_i\)，值为\(\sum B_i*A_i\)）不可能为0

也是拟阵，按花费排序后贪心取并维护线性基

4037: [HAOI2015]Str

\(F(x)\)表示x拆分成若干个不大于m的数的和的方案数，\(G(x)\)表示将数字串分割成若干个数，将他们加起来，求F，并求和。求\(G(x)\)

首先F可以通过矩阵快速幂计算得到，设A为转移矩阵，可以知道\(G(123)=F(12+3)=A^{12+3}=A^{12}*A^3\)，然后G也可以\(O(n^2)\)计算，叠加起来就是\(O(n^2 m^3)\)，顺便%太多次会TLE，卡常数

4033: [HAOI2015]T1

有大小为N的树，K个点染成黑色，价值定义为黑点两两距离和+白点两两距离和，求最大价值

树状DP，然后就结合背包随便做了，看起来复杂度是\(O(n^3)\)，事实上可以证明复杂度为\(O(n^2)\)

3631: [JLOI2014]松鼠的新家

裸链剖

3172: [TJOI2013]单词

AC自动机，然后每个字符串的前缀节点+1，然后fail树累积至树根

3998: [TJOI2015]弦论

SA裸题

2761: [JLOI2011]不重复数字

省选签到题

4029: [HEOI2015]定价

省选签到题*2

3609: [HEOI2014]人人尽说江南好

首先，每个局面都有最多进行轮数，奇数的话先手必胜，否则后手必胜，而且可以证明必胜的那一方绝对能把局面推到最多进行轮数的情况（然而不会证，直觉）

3191: [JLOI2013]卡牌游戏

就是概率DP

2764: [JLOI2011]基因补全

DP，类似最长公共子序列

2431: [HAOI2009]逆序对数列

DP，F[i,j]表示数列中1..i的数构成的序列的逆序对为j的方案数

2425: [HAOI2010]计数

数位DP，预处理C算方案数

2423: [HAOI2010]最长公共子序列

裸题。。。

1046: [HAOI2007]上升序列

倒过来做最长下降序列，然后从后往前扫一遍

1045: [HAOI2008]糖果传递

一开始每人有\(K_i\)个苹果，相邻可以传递，用最小传递次数使得所有人的苹果数一样

设p[i]表示第i人需要传给第i+1人的苹果数，然后我们会发现同时增减所有p时都是合法的，而答案等于p的绝对值之和，于是当p的中位数=0时答案最优

1044: [HAOI2008]木棍分割

对于问题一是二分答案+贪心，问题二则是DP+滚动数组。

1042: [HAOI2008]硬币购物

DP+容斥，先预处理出每种价钱的方案数，然后$Ans=([Null])-([1]+[2]+[3]+[4])+([12]+[13]+[14]+[23]+[24]+[34])……$

（$[abc]$表示哪些种硬币超出使用限制）

1048: [HAOI2007]分割矩阵

状态数（10*10*10*10*10）不多，可以考虑记忆化搜索

2424: [HAOI2010]订货

裸网络流

1047: [HAOI2007]理想的正方形

给一个矩阵，选取一个子正方矩阵，求$Min(max-min)$

利用单调队列两次，求出每个正方形的max&min

1041: [HAOI2008]圆上的整点

已知$z$，求符合$x^2+y^2=z^2$的$(x,y)$对数

先考虑本原勾股数，本原勾股数满足：

$$x=ab$$

$$y=\frac{a^2-b^2}2$$

$$z=\frac{a^2+b^2}2$$

其中$1 \le a < b$且$gcd(a,b)=1$

然后只需要将$x,y,z$同乘个正整数$d$就能得到所有勾股数了

算法也就出来了，枚举$d$为$z$的约数，然后再枚举$a$，判断$b$是否存在

2301: [HAOI2011]Problem b

莫比乌斯反演

求

$$gcd(x,y)=k(a \le x \le b 且 c \le y \le d)$$

首先，利用子矩阵求和的特点，转成子矩阵前缀和；然后消掉k得到

$$gcd(x/k,y/k)=1(1 \le x \le a/k 且 1 \le y \le b/k)$$

然后就变成求互质对数了。根据莫比乌斯反演某条需要用到容斥的公式，互质对数为

$$\begin{align} & \sum_a^{x/k} \sum_b^{y/k} [gcd(a,b)=1] \\ = & \sum_a^{x/k} \sum_b^{y/k} \sum_d [d|gcd(a,b)]\mu(d) \\ = & \sum_d \mu(d) \frac{x}{kd} \frac{y}{kd} \end{align} $$

然后对于某一段$d$，$(x/kd)$和$(y/kd)$是不变的，于是我们就可以计算$\phi(d)$的前缀和，将$(x/kd)$和$(y/kd)$不变的那一段合并起来计算

2299: [HAOI2011]向量

裴蜀定理，首先将8种操作换成6种：

$(\pm 2a,0)(\pm 2b,0)(0,\pm 2a)(0,\pm 2b)(a,b)(b,a)$

其中最后两种只需用到一次，即可完成题目所需要的所有操作

然后就是枚举最后两种的使用情况（4种可能），列两个个二元方程，判断是否有整数解（Exgcd）

1051: [HAOI2006]受欢迎的牛

询问有多少点能由任意一个点出发到达

Tarjan缩点完判断一下有没有出度为0的联通块，有多个则无答案，一个则答案为此联通块大小

1054: [HAOI2008]移动玩具

傻叉题

1258: [CQOI2007]三角形tri

傻叉题

1303: [CQOI2009]中位数图

傻叉题

1053: [HAOI2007]反素数ant

质因数越小越好，然后约数个数可以通过分解质因数算得，接着就搜索+剪枝大法（其实前10个素数就够用了）

1306: [CQOI2009]match循环赛

搜索+剪枝，能加的剪枝就加

1816: [Cqoi2010]扑克牌

二分答案，J的功能就是来填补其余牌的空缺的，且J的使用张数不能超过答案（否则根据抽屉原理，一定会有一个套牌包含两个J，然而这是不合法的）

1818: [Cqoi2010]内部白点

首先证明不可能有无限循环的情况，而且只需一回合，所有能变黑的白点就都会变黑。

然后离散化的时候就顺便找每个横坐标的垂线段，接着坐标排序完用树状数组维护，垂线段上端点+1，下端点-1，扫完一个纵坐标就累计答案

1055: [HAOI2008]玩具取名

就一个搜索，加点状压