NanoApe's Blog

既是咸鱼又是辣鸡

【卖萌Oct】Problems

NanoApe posted @ 2015年10月03日 21:42 in 蒟蒻不比赛何来学费 , 291 阅读

完成度:

4/23

[SRM 670 Div1 A]

给定一个括号序列,求和他相同长度且合法且LCS最大的括号序列有多少个

可以知道\(LCS=Length-1\),然后就枚举括号序列中的一位左右移动,获得\(L^2\)的LCS合法序列,然后就判断合法+map去重,复杂度\(O(L^3)\)

[SRM 670 Div1 B]

给定一棵树,上有一些红蓝标记,每轮各方可移动一些同色标记一步或者原地不动(每轮中红先蓝后)当红蓝标记重叠时蓝方胜利。求红方最多能苟延残喘多少轮。

首先把蓝标记位置dfs一遍,求出d[i]表示i点与蓝标记的最近距离。然后对于每个红点假如不可能被抓就移动,求最大值为其最长存活时间。然后所有红点的最长存活时间求最小值。

[CF 325 Div2 E]

妈呀神奇的构造题。把x和y用类似辗转相除的方法求操作序列,输出的时候也不用倒序输出(并不会证明QAQ

[CF 325 Div2 F]

分成两边,然后3^13的复杂度找选择方案,然后在两边找偏移值一样的方案,加起来即为合法,顺便还可以求总和最小


登录 *


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