NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#9

NanoApe posted @ 2016年1月13日 08:45 in 蒟蒻不做题提前退役 , 597 阅读

Year榜#1好难拿。。。

50/50

1057: [ZJOI2007]棋盘制作

DP,最大子矩阵问题;最大子正方形一定在极大子矩阵中

1059: [ZJOI2007]矩阵游戏

二分图匹配

1412: [ZJOI2009]狼和羊的故事

最小割

1411: [ZJOI2009]硬币游戏

★首先,$2^a$次的操作后,每个数的状态只由原先两个数决定;那么把操作分解成若干$2^a$的操作

2656: [ZJOI2012]数列(sequence)

高精度运算烦。。。

我们可以一直维护两个数及其次数并同时除2

1833: [ZJOI2010]count 数字计数

数位DP,入门题

1834: [ZJOI2010]network 网络扩容

网络流

首先跑最大流,然后在残留网络上费用流

1452: [JSOI2009]Count

维护100个二维树状数组

1003: [ZJOI2006]物流运输trans

枚举日期区间跑最短路,然后再来DP

1864: [ZJOI2006]三色二叉树

树状DP,其实只需要理绿色就行

1433: [ZJOI2009]假期的宿舍

最大流,建图什么的挺容易的

1096: [ZJOI2007]仓库建设

斜率优化DP

2324: [ZJOI2011]营救皮卡丘

★首先Flody求各个点之间的最短路(注意$d(i,j)=d(i,k)+d(k,j)$的k不能同时大于i和j),然后建图求最短路径覆盖,费用流的部分

4195: [NOI2015]程序自动分析

并查集

4196: [NOI2015]软件包管理器

链剖

1497: [NOI2006]最大获利

最大权闭合图

1968: [AHOI2005]COMMON 约数研究

☆直接求每个因子的贡献即可(然而这函数能线性筛么。。。貌似可以

1800: [AHOI2009]fly 飞行棋

水题

1265: [AHOI2006]斐波卡契的兔子(kacci)

高精度除法!我&&)&*(&*)%¥#%@#%!@¥##@%!@#¥#@%!¥#

1801: [AHOI2009]chess 中国象棋

DP,设f[i][j][k]表示前i行有j列放了0个炮,k列放了1个炮的的方案数

1406: [AHOI2007]密码箱

平方剩余(模任意数)

将$x^2 \equiv 1 \pmod n$分解成$(x-1)(x+1)=yn$

然后枚举$n$的约数$a$,枚举倍数$k$,设$x=ak+1$或$x=ak-1$,若x有满足条件的则加入set排重

1266: [AHOI2006]上学路线route

最短路+最小割

1786: [AHOI2008]Pair 配对 & 1831: [AHOI2008]逆序对

DP,由贪心可得填的数必定为单调不减,然后DP一发

1787: [AHOI2008]Meet 紧急集合 & 1832: [AHOI2008]聚会

求三次Lca,分类讨论

1789: [AHOI2008]Necklace Y型项链 & 1830: [AHOI2008]Y型项链

可知最终串一定是三字符串之一的子串,枚举最终串讨论

1798: [AHOI2009]Seq 维护序列seq

线段树

1799: [AHOI2009]self 同类分布

枚举模数然后数位DP(加了几个显然的剪枝就#1了

2822: [AHOI2012]树屋阶梯

卡特兰数

1970: [AHOI2005]Code 矿藏编码

DFS+高精度

1264: [AHOI2006]基因匹配Match

最长公共子序列的DP照做,然而对于一个字符最多只有5个匹配点,于是我们先储存起来就可避免$O(n)$的查找,用树状数组维护,降至$O(nlogn)$

1081: [SCOI2005]超级格雷码

如何制造格雷码:递归的时候翻来翻去???

1083: [SCOI2005]繁忙的都市

线段树,维护格子之间的连通性

1965: [AHOI2005]SHUFFLE 洗牌

数论

可知第x张牌下次出现的地方为$2x \mod {(N+1)}$

那么第x张牌经过k次洗牌后出现的地方为$2^kx \mod {(N+1)}=L$

L乘个逆元就是x了,求任意数逆元用Exgcd

1082: [SCOI2005]栅栏

二分答案+搜索

剪枝1:能切的话肯定是切长度前x小的

剪枝2:先用较小的木板切较大的所需

剪枝3:如果当前所需的长度和前一个所需的长度相同,那么枚举原料的时候直接从切出前一个的地方开始枚举

剪枝4:如果浪费掉的材料+前x小的总长度>原料总长度,这种方案一定不可行

☆1086: [SCOI2005]王室联邦

块状树(树分块)

DFS一遍,若子树大于B则剪掉,剩余部分全部合并到最后一个块内

1237: [SCOI2008]配对

状压DP,可证每个数所配对的最远距离不超过2,然后状压一发

1293: [SCOI2009]生日礼物

游标卡尺法

1018: [SHOI2008]堵塞的交通traffic

线段树

将一格子的联通情况储存起来,然后线段树维护

1930: [SHOI2003]pacman 吃豆豆

费用流

处理出两两点的偏序关系,然后建图跑网络流

注意,数据点有N个点都在同一位置上的情况,所以要对图进行剪枝

若 a→b 且 b→c 则不用连 a→c 然后每个点的允许经过次数调整为2

1936: [SHOI2004]Rect 矩形

先离散化,然后枚举左下角和右上角(只枚举在矩形角上的)预处理出每个点左右上下沿边界移动的最大距离,$O(n^2+n^2)$

☆1933: [SHOI2007]Bookcase 书柜的尺寸

DP,状态设置得很巧妙

设置状态为$F(i,j)$为第一二层的宽度分别为 i、j 时的最小高度和

3033: 太鼓达人

欧拉回路,直接dfs一遍就行

1935: [SHOI2007]Tree 园丁的烦恼

给N个点,每次询问某个矩阵内有多少个点

离散化后将询问分解成四个前缀矩阵的询问,然后从左到右扫一遍,用树状数组维护

1226: [SDOI2009]学校食堂Dining

DP

将包括自己及其后面7人的状态以及前一个人的位置记录下来,然后在满足每个人的限制下进行转移

2465: [中山市选2009]小球

贪心,将最大价值的球放在分数上界最大的瓶子内

2565: 最长双回文串

回文树,左右各跑一遍,统计每个点往左能走多远,往右能走多远

2456: mode

思考题

相同则累加出现次数,不同则两两消去


登录 *


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