目录
Contest InfoSolutions A. BowWow and the TimetableB. Mislove Has Lost an ArrayC. Anna, Svyatoslav and MapsD1. Kirk and a Binary String (easy version)D2. Kirk and a Binary String (hard version)E. Natasha, Sasha and the Prefix SumsPractice Link
SolvedABCD1D2E6/6OOOOØØ O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试题意： 找一个二进制表示的数\(n\)中有多少个小于\(n\)的\(4\)的幂次的数。
思路： 计算\(\left\lceil log_4s \right\rceil\)。
签到。
题意： 给出一张图的邻接矩阵，然后给出一条路径，要缩短路径，使得缩短后的路径的任意两点之间加上这两点的最短距离经过的点，会变成原路径。
思路： 跑一下\(Floyd\)，然后用栈判断，栈顶的三个点的那么中间点能否移去。
题意： 给出一个\(01\)串，问构造另一个\(01\)串，使得两个\(01\)串的任何一个子段的\(LIS\)长度相同，并且要保证\(0\)的个数尽量多。\(|s| \leq 2000\)
思路： 猜测\(0\)的个数最多的方案下只有第一个串那个位置是\(1\)的话，构造的那个串的那个位置才需要放\(1\)。 然后每次暴力判断一下，如果不合法，那一位就放\(1\)
题意：同\(D1\)，\(|s| \leq 10^5\)
思路： 我们考虑倒着做：
\(dp0\)表示以\(0\)开头的\(LIS\)的最大长度\(dp1\)表示一\(1\)开头的\(LIS\)的最大长度我们发现左边如果增加一位\(0\)，那么\(dp0 = max(dp0, dp1) + 1\)否则如果增加一位\(1\)，那么\(dp1 = dp1 + 1\)，并且\(dp0\)不变那么我们注意到，如果原串的那一位是\(0\)，那么直接放\(0\)没有什么问题。当原串那一位是\(1\)的时候，我们如果在新串中放\(0\)可能导致新串中的\(max(dp0, dp1)\)产生变化也就是说当\(dp0 < dp1\)的时候，那么这一位如果放\(0\)放\(1\)，那么会使得\(dp0 = dp1 + 1\)，如果放\(1\)，会使得\(dp1 + 1\)，发现\(max(dp0, dp1)\)没有变而每次左边增加一个数，只增加了以它开头的一些子段，而\(max(dp0, dp1)\)就是保证了这些子段的\(LIS\)的最大长度。题意： 有\(n\)个\(1\)，\(m\)个\(-1\)，每出每一种方案的最大前缀和的和。
思路：
考虑枚举每一个最大前缀和\(a\)，然后统计有多少种序列的方案的最大前缀和是\(a\)。考虑\(n \leq m\)的情况： 在二维平面上，从\((0, 0\)开始，我们令放一个\(1\)为向右走一步，放一个\(-1\)为向上走一步，那么我们要知道最大前缀和\(\leq a\)的方案数就是所有路径不跨过\(y = x - a\)的方案数然后稍微容斥一下，即可求得最大前缀和恰好为\(a\)的方案数。\(n > m\)的情况转化成\(m \leq n\)的情况即可转载于:https://www.cnblogs.com/Dup4/p/11406945.html
