11
12
2014
0

ZJOI做题计划

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)。

Category: training | Tags: ZJOI | Read Count: 10211

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com