cf1023

[Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)] (http://codeforces.com/contest/1023)

题目大意：

给出两个字符串\(s\)和\(t\)，\(s\)至多有一个通配符\(*\)可以匹配空串和任意长度的任意串，问\(s\)是否可以匹配\(t\).

题解：

~~我又挂A题了，真是睿智~~

分有没有\(*\)处理一下，\(t\)的长度至少不能小于\(|s| - 1\).

题目大意：

求有多少数对\((a,b)\)，满足\(1\le a < b\le n\)，并且\(a + b = k\)，\(1\le n, k\le10^{14}\).

题解：

特判无解之后，解一下不等式，减去\(a=b\)的case，方案除以\(2\)即可。

题目大意：

给出一个长度为\(n\)的合法括号序列，要求输出一个长度为\(k\)的子序列满足也是合法括号序列。

题解：

算出要删多少字符，用栈匹配的时候删若干对括号即可。

题目大意：

有一个长度为\(n\)的数列，有\(q\)次操作，第\(i\)次操作将区间\([l_i,r_i]\)的数字全变为\(i\).

给出一个操作完成后的数列，判断其是否合法，特别地，如果一个位置为\(0\)，则可以任意填入一个数字。

如果合法输出一种填数的方案。

题解：

如果全是\(0\)，全部填入\(q\)一定合法。

统计出每种数字出现的开始与结束位置，让它们作为区间端点，模拟一下，看是否符合输入的数列。

如果有多余的\(0\)，让它们等于附近的非零数字即可。

注意\(q\)必须得出现，否则，如果有\(0\)，让任意一个\(0\)变为\(q\)即可，没有\(0\)则无解。

题目大意：

交互题。

有一个\(n\times n\)的网格图，每个格子可能有障碍或者没有障碍，现在要从左上角\((1,1)\)走到右下角\((n,n)\)，只可以向右与向下走。

并不清楚具体哪些格子是障碍，但是可以询问不超过\(4n\)次，每次询问两个点\((r1,c1)\)和\((r2,c2)\)，满足曼哈顿距离大于\((n-1)\)，是否可以从第一个点只向下或向右走到达第二个点。

输出一条合法的路径。

题解：

路径会分为两半，一半离\((1,1)\)曼哈顿距离大于\((n-1)\)，另一半离\((n,n)\)曼哈顿距离大于\((n-1)\)，让它们都尽可能向右上角走，拼起来即可。

题目大意：

有一个\(n\)个点，\(k+m\)条边的无向连通图。

其中\(k\)条边尚未决定权值大小，并且这\(k\)条边内部不会有环。

其余\(m\)条边的权值已经决定，并按升序给出。

现在要给\(k\)条边决定权值，使得存在一个最小生成树中它们能全部出现，在这个前提下最大化这\(k\)条边的边权和。

题解：

先把这\(k\)条边建成森林，然后其余的\(m\)条边从破圈法的角度考虑，如果它覆盖的树链上存在大于它的边，就会将其破掉，因此每条边会给链上的所有边一个最大值的限制。

因为输入是升序的，每次只考虑将未被限制的边限制成当前的权值即可，可以轻重链剖分加并查集\(O(n\log{n})\)，也可以tarjan求lca加并查集\(O(n)\).