NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#12

NanoApe posted @ 2016年2月27日 20:06 in 蒟蒻不做题提前退役 , 389 阅读

刷题太慢了(

50/50

1030: [JSOI2007]文本生成器

包含单词字符串数=总数-不含单词字符串数

后者可以建完AC自动机后直接DP出来(设当前在自动机上走几步走到哪个点)

2330: [SCOI2011]糖果

差分约束

要求最小方案,所以跑最长路

SPFA貌似跑负环复杂度会$O(n^2)$,所以我换了个判定方法,即当前点的最短路的长度大于 n 时则判定有负环

2005: [NOI2010]能量采集

数论

也就求个gcd前缀和,n不大,用莫比乌斯初步优化一下就可以出来了

1500: [NOI2005]维修数列

Splay模板题

学会了双旋写法

1070: [SCOI2007]修车

网络流

设$nm$个点,表示第i个维修工是否进行倒数第j次的维修,然后再设$n$个点,表示各车

最后费用设一下,求费用流

1061: [NOI2008]志愿者招募

网络流

将题目条件写成 n 个约束条件,增加松弛变量使得约束条件变成等式,变形式子使得每个变量只出现两次且一正一负

设有 m 个式子,那么建立 m 个点和源汇,每个变量作为一条流,通过约束条件建图,正为入流负为出流

然后去跑费用流

3211: 花神游历各国

暴力下传标记暴力修改,当一段区间内的所有数都小于2时不用下移标记修改

1432: [ZJOI2009]Function

当n为1时$ans=1$,否则第k层为$2*min(k,n+1-k)$

2434: [NOI2011]阿狸的打字机

建立AC自动机,求出FailTree的dfs序,遍历AC自动机,当访问到某询问的左端点时,查询右端点在FailTree中有多少标记点为其祖父

2875: [NOI2012]随机数生成器

快速幂+快速乘

1565: [NOI2009]植物大战僵尸

最大权闭合图,被保护点连至保护点,tarjan缩环后连至tarjan的点全部无效,然后跑网络流

2006: [NOI2010]超级钢琴

建堆,用堆维护$(a,l,r)$表示左端点为a且右端点范围为$[l,r]$的最大值。枚举左端点全部扔到堆里,然后选取最大值,并将右端点范围分裂成两块,通过ST表求得最大值后扔进堆里,循环K次

4413: [Usaco2016 Feb]Milk Pails.txt

随便记忆化搜索一下

1143: [CTSC2008]祭祀river

最长反链=最小链覆盖=最少可相交链覆盖,然后传递闭包一下就可以变成最少不可相交链覆盖

2435: [NOI2011]道路修建

树DP

3670: [NOI2014]动物园

ExKMP

3143: [HNOI2013]游走

高斯消元求出每个点的期望经过次数,推出每条边的期望经过次数,贪心编号

1415: [NOI2005]聪聪和可可

最短路得移动方向,然后记忆化搜索一发

2879: [NOI2012]美食节

网络流

同“修车”,但是一开始不要把所有边都建立起来,当厨师做好第K个人的菜的时候才加入第K+1个点

1491: [NOI2007]社交网络

Flody求最短路数量

2208: [JSOI2010]连通数

缩环后$O(n^2)$暴力找

1076: [SCOI2008]奖励关

记忆化搜索,设$F[i,S]$表示 i 轮过后拿到的奖品的集合状态为 S 时的期望最优值

3668: [NOI2014]起床困难综合症

分位考虑

1499: [NOI2005]瑰丽华尔兹

DP+单调性优化

1797: [AHOI2009]Mincut 最小割

在残余网络上跑 tarjan 求出所有 SCC,记$id[u]$为点 u 所在 SCC 的编号,显然有$id[s] \ne id[t]$

①对于任意一条满流边$(u,v)$能够出现在某个最小割集中,当且仅当$id[u] \ne id[v]$

②对于任意一条满流边$(u,v)$必定出现在最小割集中,当且仅当$id[u]=id[s]$且$id[v]=id[t]$

1977: [BeiJing2010组队]次小生成树 Tree

MST建出来后倍增维护树上路径最大值和次大值

1017: [JSOI2008]魔兽地图DotR

DP套背包,$F[i,j,k]$表示以 i 为根的子树+向上传送 j 个物品+花费 k 的最大攻击力

3224: Tyvj 1728 普通平衡树

Treap

3223: Tyvj 1729 文艺平衡树

Splay

2120: 数颜色

用树状数组套主席树维护$next[]$,$next[i]$表示右边最接近的和i同色的下标

1251: 序列终结者

Splay

2818: Gcd

欧拉函数

2588: Spoj 10628. Count on a tree

树上遍历套主席树,同“BZOJ3123:森林”

2152: 聪聪可可

一遍树DP

2179: FFT快速傅立叶

这是道模版题

3110: [ZJOI2013]K大数查询

权值线段树套区间线段树

1901: Zju2112 Dynamic Rankings

树状数组套主席树

3196: Tyvj 1730 二逼平衡树

上题再加个 Splay

3289: Mato的文件管理

莫队,用树状数组维护区间逆序对个数

2049: [SDOI2008]Cave 洞穴勘测

LCT 模版题

2631: tree

LCT+Splay

3669: [NOI2014]魔法森林

LCT 动态维护 MST

先把所有边按 a 为第一关键字从小到大排序,对于一段相同的 a 查询 1 点到 n 点在 MST 上的瓶颈边

2594: [WC2006]水管局长数据加强版

也是 LCT 动态维护 MST

离线逆序操作,就变成加边维护MST

1507: [NOI2003]Editor

Splay

1269: [AHOI2006]文本编辑器editor

Splay

3676: [APIO2014]回文串

回文树乱搞

3555: [CTSC2014]企鹅QQ

Hash 一边就完事

1566: [NOI2009]管道取珠

要求$\sum a_S^2$,我们可以看成是 A B 两个玩家分别完成游戏后获得的字符串相同的方案数

设$F[o][i][j]$为当前取了 o 颗,A 在一管取了 i 颗,B 在一管取了 j 颗,且两人所得到字符串相同的方案数

3139: [HNOI2013]比赛

记忆化搜索,Hash去重(去重的状态:有i个人互相都没安排的时候剩余未安排分数)

3931: [CQOI2015]网络吞吐量

最短路后直接网络流


登录 *


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