Charlie01

ZJOI做题计划

看到各种大爷都在切神题。。我这种蒟蒻也来跟风。。

现在做了几题了：37

[ZJOI2006]物流运输trans：O(n^2)DP，f[i]表示到第i天的最小代价，用SPFA转移。

[ZJOI2008]杀蚂蚁antbuster：强模题，直线与圆的关系可以用圆心到直线的距离来判定。

[ZJOI2008]泡泡堂BNB：贪心，如果最小的能赢对方最小的或最大的能赢对方最大的那么直接去打，否则用最小的去打对方最大的；最小得分就是总分减对方的最大得分。

[ZJOI2008]Risk：平面图找域，射线法判定点与多边形的关系。

[ZJOI2008]树的统计Count：树链剖分。

[ZJOI2008]生日聚会Party：DP，f[i][j][k][l]表示i个人，j个男孩，男孩比女孩多的个数，女孩比男孩多的个数。

[ZJOI2008]瞭望塔：计算几何，用单调栈维护特殊的半平面交。

[ZJOI2008]骑士：环套树DP，把环中的一条边断开做2次TreeDP。

[ZJOI2007]棋盘制作：悬线法求最大01子矩阵，记录d[i][j]表示这条悬线向下能扩展的最大距离，l[i][j]表示这条悬线向左能扩展的最大距离，r[i][j]表示这条悬线向右能扩展的最大距离。

[ZJOI2007]报表统计：set & multiset乱搞。

[ZJOI2007]矩阵游戏：游戏有解的条件是存在n个点使得这n个点的横纵坐标各不相同，转化为二分图问题，若matrix[i][j]为1则i向j连一条边，二分图存在完美匹配则游戏有解。

[ZJOI2007]时态同步：TreeDP，f[x]表示以x为根的子树中的最大深度，则ans=sigma(f[x]-f[son[x]]-time[x,son[x]])。

[ZJOI2007]最大半连通子图：Tarjan缩环，拓扑排序DP找最长路径。

[ZJOI2007]粒子运动：枚举2个点，计算这2个点在每个时间段的最小距离，向量方法计算对称向量、粒子碰撞到圆的位置，二次函数计算在一个时间段内粒子的最近距离。

[ZJOI2007]Hide 捉迷藏：将树转换为括号序列，用线段树维护。

[ZJOI2007]仓库建设：斜率优化DP。

[ZJOI2009]硬币游戏：找规律发现经过2^i次变换使得某一位上的数只和上一次两个位上的数有关，将T二进制分解。

[ZJOI2009]狼和羊的故事：最小割，狼连源点，羊连汇点，相邻点连边。

[ZJOI2009]取石子游戏：博弈论，DP，分类讨论。

[ZJOI2009]对称的正方形：manacher预处理出每一行每一列的rad值，然后对于4个方向二分出最远能扩展的距离取最小值，用ST表维护最小值。

[ZJOI2009]Function：规律题，n=1时答案为1，否则答案为2*min{k,n-k+1}。

[ZJOI2009]假期的宿舍：二分图匹配，源点向需求连边，供应向汇点连边，认识关系相互连边。

[ZJOI2009]染色游戏：SG函数，令左上角的格子为(0,0)，当ij=0时SG(i,j)=lowbit(i+j+1)，否则SG(i,j)=2^{i+j}。

[ZJOI2009]多米诺骨牌：插头DP预处理a[u][d][l][r]表示(u->d, l->r)范围内无限制放置的方案数，容斥列，对于每一容斥项进行补集转化。

[ZJOI2010]count数字计数：数位DP。

[ZJOI2010]network网络扩容：Dinic最大流，费用流。

[ZJOI2010]base基站选址：线段树优化DP，f[i][j]表示前j个村庄建i个基站的最小代价，f[i][j]=min{f[i-1][k]+w(k,j)}+c[j]，w(k,j)单调。

[ZJOI2006]Mahjong麻将：搜索，hash去重。

[ZJOI2006]Book书架：splay。 

[ZJOI2006]GameZ游戏排名系统： splay。

[ZJOI2006]三色二叉树：TreeDP，难点在建树。

[ZJOI2004]Swamp 沼泽鳄鱼：矩阵乘法，按12的循环节快速幂。

[ZJOI2004]Lunch 午餐：按{bi}从大到小排序，DP，f[i][j]表示前i个人，第一个队伍中等待时间为j的最小答案。

[ZJOI2010]Perm 排列计数：本质是堆的计数，f[i] = f[left] * f[i - 1 - left] * C(i - 1, left)。

[ZJOI2015]幻想乡战略游戏：动态点分治，对于每个重心记录当前子树的size，当前子树到重心的带权距离和，当前子树到上一层重心的带权距离和；询问时对于某个重心，若出边连接的点的答案小于当前重心，则答案在出边连接的点对应的子树中。

[ZJOI2015]地震后的幻想乡：DP求出f[S][i]表示最后一条有效边的排名为i，点集为S的方案数即可。

[ZJOI2015]诸神眷顾的幻想乡：（做法I）对于每个叶结点建TRIE，在TRIE上建SA。（做法II）对于每个叶结点DFS，构建广义SAM，ans = sigma(i->value - i->parent->value)。