5
21
2015
0

CERC/NEERC/WF 2013/2014

跟着学长混 有学长题解妈妈我再也不怕啦

CERC2013:

CERC2014:

Outer space invaders:

离散化后设\(f[l][r]\)为消灭完全存在区间\((l,r)\)中的外星人代价,\(O(n^3)\)dp显然

Wheels:

这题各种问题……直接按题意做就行了……

最坏应该写高精度但是不用写……

数据中会有环但是强行当成树就好……

NEERC2013:

NEERC:2014

WF2013:

WF2014:

Sensor Network:

PoPoQQQ:爆搜T到死,加什么剪枝都没用……

我用了4个小时的时间深刻地感受了这一点

无爱……

Surveillance:

首先把环变成二倍链,于每个点处理出它一次能够走到的最右侧的点+1,这样就形成了一棵树结构

枚举起点,判断i跳到i+n的最小步数,即树中i的祖先的第一个>=i+n的点与i的深度差,由于内存吃紧就写了树剖

baggage:

首先n=3的时候特判

然后我们发现其实只需要-1,0两个空白就够了

我们定义solve(l,r)为将形如"__(BA)^n"的串变为"A^nB^n__"

S^n表示SSSS......

然后:

__BABA(BA)^nBABA

ABBABA(BA)^nB__A

ABBA__(BA)^nBBAA

注意到中间的情况变为了"__(BA)^n"可以递归solve解决,然后变成这样

ABBAA^nB^n__BBAA

A__AA^nB^nBBBBAA

AAAAA^nB^nBBBB__

啦啦完成啦!

显然我们每次把问题由n变为了n-4的子问题,可以递归解决

n=3的时候非常特殊,需要特判

递归的边界是n=4,5,6,7

手玩一下打个表

这题蛋疼了我两天……由于智商不够手玩好长时间……还不如写个搜索……

Game Strategy:

首先正向思考似乎没什么思路

那么逆过来,从终点进行bfs

枚举终点,枚举到终点的最短步数

设当前枚举的步数为cnt,可以在cnt-1步内到达终点的点集为S

枚举一下不在点集中的起点,考虑如果该起点有一个集合,这个集合是S的子集,那么Alice选择这个集合就能够进入S集合内的

点,于是该起点的到终点最短距离就是cnt.

总复杂度\(O(n^2m)\)……然后就过了

Category: OI | Tags: | Read Count: 730

登录 *


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