跟着学长混 有学长题解妈妈我再也不怕啦
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
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)\)……然后就过了
评论 (0)
