ZJOI2007棋盘制作
[ZJOI2007]棋盘制作 悬线法DP，一般用于求矩形上最大字矩形 定义三个数组left，right，up，分别表示向左向右可以扩展到哪个格子，向上可以扩展多少格。 考虑这样的情况，DP进行到了黑色位置，蓝色满足要求，绿色却不满足，不操作直接用三个数组计算会导致答案错误 解决方案是，如果上方的格子
0%
NOI2015软件包管理器
[NOI2015]软件包管理器 传说中NOI2015出了三道板子题，果然名不虚传，一道并查集一道Huffman树一道树链剖分… 虽然依赖条件是有向边，但是纸上画一画可以发现有向无向其实没关系。建成一棵双向边连接的，根为0的树即可。 对树进行树链剖分，每次安装时把要安装的点到根全部变成1，统计增加量，
JLOI2014松鼠的新家
[JLOI2014]松鼠的新家 又是一个LCA树剖都能做的题，想少打点代码还跑的快点，用了LCA+树上差分 根据题意，每次要把两点间所有点值+1。因为除第一次外，每次操作都会把当前起始点多+1（最后一次值不增加，也视为多+1），最后输出时要把这些值-1。 于是建立sum数组，每次把两点+1，LCA与
货车运输
货车运输 理论上树链剖分好写一些，然而蒟蒻只能用倍增+LCA… 思路：注意到小边没用，直接贪心求出最大生成树，最优答案一定在最大生成树上 建出新树，求一下重心（其实并不需要… 以重心为树根跑LCA，同时用数组$mincost[x][i]$记录从点x开始向上走$2^i$步能走到的距离内边的最小值。它与
Beauty Contest
Beauty Contest 给定平面上很多点，求最远两点之间距离的平方 凸包是可以把平面上所有点包起来的凸多边形，可以想象为用橡皮筋在外面套了一圈 最远两点一定在凸包上，因为如果不在凸包上的话可以被凸包上更远的点替代 所以，这道题首先要找出凸包 凸包满足斜率单调的性质，Graham扫描法用一个栈来
负载平衡问题
负载平衡问题 这题在网络流24题里，是个费用流的板子题，不过数学解法也能做
网络流解法
（下面用(f, c)表示一条边的流量，费用）： 求出平均数avg，从s向低于avg的点连(avg-a, 0)，从高于avg的点向t连(a-avg, 0) 相邻两条边之间连(INF, 1)，表示可以互相传递，注意
2017国家集训队测试无限之环
[2017国家集训队测试]无限之环 也许是费用流神题？ 说起来我玩过这游戏，打了几十关 这题有15种形状的管子，分别指向1，2，3，4个方向，要分类处理建图 黑白染色，拆成五个点（上下左右中），s，t分别向它们连边。对于每条边，流量全部是1，费用由转几下决定 指向一个方向的与四个方向的好处理，012
在农场万圣节
P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm 学了Tarjan准备缩点，冷静分析后发现暴力DFS就能做 DFS思路：因为是只有一条出边的有向图，DFS找环，然后更新环上答案为环的大小，其它点答案为到环距离+环的大小
1
2
3
4
5
6
7