bzoj一句话题解

发现好多人都在搞这个。。。本人也想来试试（Solved刚到70就搞这个靠不靠谱啊喂）。会更新的。嗯。

1000-1029

1000 A+B problem

（这个还需要一句话吗.

1001 狼抓兔子

平面图最小割转化为最短路。

1002 轮状病毒

矩阵树定理加一个手推的递推式就行了（注：在原行列式上递推有点麻烦，可以先递推行列式的一部分）。

1003 物流运输

枚举区间floyd求最短路，然后O(n2)” role=”presentation” style=”position: relative;”>O(n2)$O(n^2)$$O(n^2)$dp。。。

1004 Cards

直接上Burnside定理。

1005 明明的烦恼

无根树prufer序列+一点数学推导。

1006 神奇的国度

弦图的染色数=最大团，按完美消除序列倒序染色。

1008 越狱

容斥（减法计数原理+两个快速幂（那么简单的题还能上省选。

1009 GT考试

经典KMP递推。

1010 玩具装箱

据说标算是单调队列，但由于决策单调递增，然后搞一个枚举就能过（数据太水，此做法只要有许多1就能卡）。

1011 遥远的行星

利用误差巧妙将分母统一然后计算（话说这不符合物理规律吧喂）。

1012 最大数

单调队列+二分查找。

1013 球形空间产生器

列方程组，高斯消元。

1015 星球大战

倒着处理，并查集。

1021 循环的债务

利用总和不变的性质和每个币种只有6种情况来巧妙的减少记忆化搜索（或dp）枚举量。

1022 小约翰的游戏

SJ定理（http://www.cnblogs.com/y-clever/p/6667592.html）， 这个不算一句话。

1024 生日快乐

暴搜（加记忆化之后可以在bzoj上跑0ms）。。。

1025 游戏

数学推导+简单的分组背包。

1026 windy数

简单的数位dp。

1028 麻将

枚举听牌，再枚举对子，最后顺着扫一遍，顺子和刻子优先选后者。

1030-1299

1030 文本生成器

1009题的加强版，dp放到了AC自动机上。

1031 字符加密

后缀数组裸题，只要把原串复制一份接在后面就好了。

1037 生日聚会

dp裸题，按男孩女孩数和所有后缀中男女孩数量的差的最大最小值dp。

1038 瞭望塔

可以发现塔顶一定在每相邻两个顶点的直线上方，所以求一遍半平面交，枚举所有已知点和所有半平面交顶点的横坐标即可。

1041 圆上的整点

利用平方差公式和gcd减少枚举量。

1042 硬币购物

dp预处理+容斥原理。

1045 糖果传递

中位数（我会告诉你这是蓝书例题3吗。

1047 理想的正方形

开b个单调队列维护各列在当前上下界的最大（最小）值，再开一个单调队列扫描一遍即可。

1048 分割矩阵

暴力dp，因为标准差σ=1n∑ixi2−x¯2” role=”presentation” style=”position: relative;”>σ=1n∑ix2i/span>xˉ2span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>span style=”display: inline-block; width: 0px; height: 4.01em;”>√$sigma=sqrt{frac{1}{n}sum_i x_i^2 - bar{x}^2}$，dp最小平方差。

1057 棋盘制作

优化DP（据说叫做扫描法）。

1059 矩阵游戏

因为同行同列的关系始终不变，只需要找出n个点不同行列，也即二分图完美匹配（行列为点，黑格子为边）。

1061 志愿者招募

通过类似线性规划的想法将题目转化为 络流。

1070 修车

通过把每个技术工拆成倒数第一个，倒数第二个…倒数第n个，然后就可以二分图最大匹配了。

1078 斜堆

找规律（提示：斜堆的左右儿子节点数之差的绝对值几乎不变）。。。

1088 扫雷

这题放到普及组也是送分题啊。。。

1089 严格n元树

考虑深不超过d的树数为fd=fd&#x2212;1n+1” role=”presentation” style=”position: relative;”>fd=fnd/span>1+1$f_d=f_{d/mo><mn>1</mn>}^n+1$$f_d=f_{d-1}^n+1$，答案即为fd&#x2212;fd&#x2212;1” role=”presentation” style=”position: relative;”>fd/span>fd/span>1$f_d-f_{d-1}$，python裸题。

1090 字符串折叠

O(n2)” role=”presentation” style=”position: relative;”>O(n2)$O(n^2)$$O(n^2)$dp。

1192 鬼谷子的钱袋