wy今天翻看材料，发现了曾经写的部分题目记录，由于wy比较懒，就直接把它复制了出来。。。
1001: [BeiJing2006]狼抓兔子
本题是最大流转最小割转对偶图最短路
推荐周东的《浅析最大最小定理在信息学竞赛中的应用》
1002: [FJOI2007]轮状病毒
递推+高精(生成树计数)
周东的《生成树计数及其应用》
1003: [ZJOI2006]物流运输trans
DP+最短路
1012: [JSOI2008]最大数maxnumber
线段树裸题，也可用单调队列
1029: [JSOI2007]建筑抢修
贪心+优先队列
1036: [ZJOI2008]树的统计Count
树链剖分
1047: [HAOI2007]理想的正方形
单调队列维护行最值，再用单调队列维护行最值的最值
1051: [HAOI2006]受欢迎的牛
强连通分量
1059: [ZJOI2007]矩阵游戏
二分图匹配
1066: [SCOI2007]蜥蜴
网络流，石柱分真假点以高度为容量连线
1069: [SCOI2007]最大土地面积
凸包+旋转卡壳枚举对角线
1070: [SCOI2007]修车
费用流，每个技术人员拆成N个点表该技术人员修的倒数第k辆车，对答案的贡献为k*a[i][j]
1085: [SCOI2005]骑士精神
暴搜+剪枝
1208: [HNOI2004]宠物收养所
平衡树
1251: 序列终结者
平衡树
1270: [BeijingWc2008]雷涛的小猫
动态规划
1415: [Noi2005]聪聪和可可
预处理枚举可可的所在点，Bfs求出当前聪聪更靠近可可的点，再Dfs求期望
1449: [JSOI2009]球队收益
最小费用流
假设后面的M场比赛中双方都是输家，对于N支球队和M场比赛各建一个点，
从源向每场比赛连流量1费用0的边，从比赛向参与这场比赛的两支队伍各连一条流量1费用0的边
我们从第i支队伍的点向汇连x条边，分别代表第i支队伍赢了j场比赛时相对赢j-1场时收益的增量
答案即所有队伍最初收益+最小费用最大流的费用
1503: [NOI2004]郁闷的出纳员
平衡树
1588: [HNOI2002]营业额统计
平衡树
1613: [Usaco2007 Jan]Running贝茜的晨练计划
动态规划
1670: [Usaco2006 Oct]Building the Moat护城河的挖掘
凸包+求周长
BZOJ1798: [Ahoi2009]Seq 维护序列seq
双标记线段树
1876: [SDOI2009]SuperGCD
高精+二进制GCD
1877: [SDOI2009]晨跑
最小费用最大流
2006: [NOI2010]超级钢琴
RMQ+堆
2038: [2009国家集训队]小Z的袜子(hose)
莫队算法
2039: [2009国家集训队]employ人员雇佣
最小割
2150: 部落战争
最小路径覆盖 二分图最大匹配，也可用网络流
2597: [Wc2007]剪刀石头布
补集转化思想+最小费用流
推荐[网络流建模汇总][Edelweiss]
http://wenku.baidu.com/view/0ad00abec77da26925c5b01c.html
2761: [JLOI2011]不重复数字
离散化去重，也可用Hash
2834: 回家的路
SPFA,同行列相邻点连线
2830: 随机树
期望DP
3223: Tyvj 1729 文艺平衡树
平衡树
3224: Tyvj 1728 普通平衡树
算法显然，即平衡树
3275: Number
最小割
3238: [Ahoi2013]差异
正解是后缀自动机，然而也可用后缀数组+单调栈
3894: 文理分科
最小割(先把答案全部累加起来，然后减去建图之后的最大流就是答案)
推荐胡伯涛的《最小割模型在信息学竞赛中的应用》
4195: [Noi2015]程序自动分析
并查集
评论 (0)
