【卖萌Oct】Problems

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

完成度：

4/23

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

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

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

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

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

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

NanoApe's Blog