省选题真多啊……

50/50

1880: [SDOI2009]Elaxia的路线

无向图中给出两条路径的两端，求最长公共最短路径

四个点跑最短路，把最短路网提取出来，然后把同是两条路径上的最短路的边设为1，跑最长路（注意由于是无向图，所以某条路径还要反转方向再跑一边）

1925: [SDOI2010]地精部落

求抖动排列个数

F[i][j]表示由$1-i$所组成且$j=A[1]<A[2]$的抖动排列的个数，G[i][j]与其类似，只是$j=A[1]>A[2]$

$F[i][i+1-j]=G[i][j]=\sum_{k=1}^{j-1}F[i-1][o]$（所以G数组只是为了理解方便，可以去掉

1922: [SDOI2010]大陆争霸

神奇的Dijkstra

1923: [SDOI2010]外星千足虫

判断一个xor方程组是否有唯一解

就维护下线性基

1924: [SDOI2010]所驼门王的宝藏

Tarjan缩环后在拓扑图上找一遍

对于第一种类型的门，每行找一个作为往返中心，非第一种门连单向边，第一种门连双向边；第二种类似；第三种用个map加速查找，然后直接连

1927: [SDOI2010]星际竞速

费用流

每个点拆成入点和出点，S连所有出点，出点连入点（假如x能到y的话将x的出点连至y的入点），入点连T，对于跳跃就S连入点。流量都为1，费用则为时间

1941: [SDOI2010]Hide and Seek

KDTree

Click Here

1972: [SDOI2010]猪国杀

BZOJ模拟题系列，比杀蚂蚁难

Click Here

1974: [SDOI2010]auction 代码拍卖会

一个数字递增的数，我们可以看成是不超过9个类似"111111..."的数加在一起的结果

所以我们先求出所有类似"111111..."的数的mod值，并记录个数为cnt

设F[i][j][k]表示当前用到的k个“连一数”都满足$Mod\;p \in [0,i]$且数本身满足$Mod\;p=j$的方案数

$F[i][j][k]=\sum_{o=0}^k F[i-1][(j-o*i)mod\;p][k-o]*Calc(cnt[i],o)$，其中Calc表示从A个数可重复取B个数的方案数，$Calc(n,m)=C(n+m-1,m)$

2190: [SDOI2008]仪仗队

就欧拉函数求个总和

2241: [SDOI2011]打地鼠

枚举锤子长宽直接暴力求+最优性剪枝

2242: [SDOI2011]计算器

快速幂+ExGCD+BSGS

1007: [HNOI2008]水平可见直线

斜率从小到大排序，相同斜率取最上面的直线，然后弄个队列完事

1006: [HNOI2008]神奇的国度

弦图+最大势算法MCS

完美消除序列不是从后往前求的嘛，那你颜色也从后往前弄就行了

1009: [HNOI2008]GT考试

就是把KMP的状态转移弄成矩阵然后快速幂一发

1008: [HNOI2008]越狱

可能越狱方案数=总方案数-不能越狱方案数

1005: [HNOI2008]明明的烦恼

PruferSequence

这种一年前学的东西都忘光了QwQ

如何制造？每次找最小标号叶子，与其相连的点的标号扔进PS序列，然后删点

如何还原？根据PS序列算出每个点的度数，每次拿序列开头的数和最小标号叶子（度数为1）相连，最后剩余两点再连一次

性质？每棵树对应一个PS序列

然后这题就和顺利变成组合数学题了

1192: [HNOI2006]鬼谷子的钱袋

$Ans=log_2(x)$

1011: [HNOI2008]遥远的行星

由题目可知$f[i]=m_i*m_j/(i-j)(j \le Ai \ge 0.35i)$

前面暴力算，后面把$(i-j)$这部分看成平均数初略求

1188: [HNOI2007]分裂游戏

子游戏组合，就求SG函数完判断胜负关系再求可能方案

1010: [HNOI2008]玩具装箱toy

斜率优化

1193: [HNOI2006]马步距离

远的时候贪心（只走一个方向，在边界则轮流两个方向走，逐渐逼近终点）

近的时候随便搜索

1191: [HNOI2006]超级英雄Hero

随便二分匹配

1189: [HNOI2007]紧急疏散evacuate

先求出每个格到各个门的距离，然后二分答案+最大流判断

1195: [HNOI2006]最短母串

★把字符串看成点，就变成了求哈密顿路径了，状压DP可以接受

本来很容易的，然而要求最小字典序的答案。。。WTF(╯‵□′)╯︵┻━┻

1190: [HNOI2007]梦幻岛宝珠

F(i,j)表示j*2^i的背包，G(i,j)表示j*2^i+W%(2^i)的背包，Sum(i)表示前i层能达到的最大体积

先把物品分层，算F，然后算G，

$G(i,j)=max(F(i,j),F(i,j-k)+G(i-1,min(k*2+W\;and\;2^{i-1},sum(o-1))))$

1026: [SCOI2009]windy数

数位DP

1024: [SCOI2009]生日快乐

由于每块的面积要一样，所以每一步至多有20种切法，可以暴力搜

2756: [SCOI2012]奇怪的游戏

按照棋盘格子数的奇偶性分类讨论：偶数就二分答案+最大流判定，奇数就直接最大流判定

1025: [SCOI2009]游戏

记忆化搜索，求和为n的数列的最小公倍数种数

1033: [ZJOI2008]杀蚂蚁antbuster

BZOJ模拟题*2

1001: [BeiJing2006]狼抓兔子

平面图最大流转最短路求

1031: [JSOI2007]字符加密Cipher

双倍串连在一起后直接后缀数组求排名

3239: Discrete Logging

离散对数，BSGS

2480: Spoj3105 Mod

离散对数，然而模数可能不是质数所以要用ExBSGS

1467: Pku3243 clever Y

同上题

3122: [SDOI2013]随机数生成器

离散对数，BSGS

对a分情况讨论

若$a=0$直接判断

若$a=1$，$x_n=x_1+(n-1)b$，直接Exgcd

若$a>1$，$x_n=a^{n-1}x_1+b \frac {a^{n-1}-1}{a-1}\pmod p=t$

设$c$为$a-1$的逆元，用Exgcd解出$an−1$，最后用BSGS算一下$n$即可

1319: Sgu261 Discrete Roots

N次剩余

1420: Discrete Root

N次剩余，同上

4128: Matrix

离散对数，求逆改成矩阵求逆然后就可以做了

4271: Chemistry

具体见此

★△2219: 数论之神

数论综合

贴个Po姐姐的题解

1012: [JSOI2008]最大数maxnumber

线段树

1013: [JSOI2008]球形空间产生器sphere

高斯消元

设球心坐标，然后根据n+1个点做出n个方程

1015: [JSOI2008]星球大战starwar

并查集

离线完倒着做

1016: [JSOI2008]最小生成树计数

MST+并查集

由MST性质可知所有MST中相同长度的边数是一样的，那么算出相同权值边的连接方案数，然后乘起来就是答案

1029: [JSOI2007]建筑抢修

贪心

任务按t2从小到大排序，若能完成则完成，若不能但耗时比当前已完成最耗时的短则替换，否则就丢掉

1028: [JSOI2007]麻将

枚举等待牌和对子搜一发

1034: [ZJOI2008]泡泡堂BNB

最弱能打赢对方最弱的则打，最强能打赢对方最强的则打，否则让最弱的和对方最强的打

1037: [ZJOI2008]生日聚会Party

DP，将男生看成+1，女生看成-1，F[i][j][k]表示前i个数最大差为j且第i个数为第k大的方案数