[数据结构与算法]周总结2022.1.31-2022.2.6

1.31?

Codeforces

Codeforces Round #769 (Div. 2)

A - ABC (0:07, +1)

可恶！可恶！可恶！读错题了！读错题了！读错题了！

只要给定的01串长度大于2，就一定是NO，如果长度是2，如果01串里的两位数字相同，则为NO。其余情况全是YES（好像也没几种情况了）。

AC代码

B - Roof Construction (0:20, +)

这个题挺唬人的，不过推一推就可以发现，其实就是把不超过给定数字的最大的2的幂数标记，然后从1~n按照顺序输出，如果要输出那个被标记的数了，就先输出个0，然后再把那个数输出。

AC代码

C - Strange Test (0:58, +)

以为是个什么大难题，然后发现，一旦异或就会导致。所以实际上，异或只会执行一次。那么枚举异或之前a所相加的次数、b所相加的次数就好了。

AC代码

D - New Year Concert

赛中想了个拆因数+线段树，但是因为拆因数写成了质因数分解，线段树还写炸了，导致没来得及交上去。（算了算时间复杂度，会T）

事实上，拆因数本身是正确的，但是时间复杂度很不优秀。正确做法是二分。因为我们注意到，随着长度的增加，gcd本身是在逐渐减小的，所以gcd和长度的交点有且仅有一个。所以我们先建立一个gcd的线段树，然后二分查找gcd与长度相等的点。由于我们每次可以将不合法的数字换成一个超级大的数字，查找后续的数字时，那个数即以前的所有数字都可以不再考虑了。如果这个数中找到了gcd和长度相等的位置，那么这个数不合法，令答案+1，并记录当前位置，下次二分的时候以这个数的后一个数作为左端点。

AC代码

2.1

Nowcoder

21303 - 删括号

给两个合法的字符串s,t，问能否从s中删去0个或多个"()"，使s=t。

有两个做法：DP方法和把括号序列移到树上的方法。

DP方法：

对于串的常规匹配模式：dp[i][j]表示第一个串前i个字母和第二个串前j个字母是否匹配。而这道题目由于我们可以主动删去t串的一些字符，所以我们还要s串中的k个字符。而事实上，我们只需要考虑删掉'('，因为题目保证括号序列一定合法，所以我们遇到的左括号一定是多于右括号的。此时我们只需要记录，删去几个已经读到的左括号，使t串前j个与s串前i个匹配。

所以我们定义dp[i][j][k]表示s串的前i个符号、t串的前j个符号，在删除掉s串中的k个左括号后是否匹配，如果匹配值为1，不匹配值为0。

初态，一个字母都没有读入，此时i=j=k=0。这个状态是合法的。即dp[0][0][0] = 1。

现在我们考虑转移方程。我们假设dp[i][j][k]=1，以此可以匹配的状态读取s串的第i+1个字符和t串的j+1个字符。显然现在有四种情况：

1.s[i + 1] = '(' and t[i + 1] = '('

2.s[i + 1] = '(' and t[i + 1] = ')'

3.s[i + 1] = ')' and t[i + 1] = '('

4.s[i + 1] = ')' and t[i + 1] = ')'

分别来考虑：

当s[i + 1] = '(' and t[i + 1] = '('时：由于两个串下一个符号相同，且所以不难推出k=0时，dp[i + 1][j + 1][0] = 1。如果我们只看s串的下一个符号，那么想要让s的前i+1个符号和t的前j个符号匹配，那就只能多删除s串的新读入的那个左括号了，于是得出：dp[i + 1][j][k + 1] = 1。

为什么要在k=0的情况下？

由于s和t都是合法的，所以读入的左括号的数量一定大于等于右括号。而当k>0时，意味着dp[i][j]所表示的配对中，有大括号被删去了。而我们题目中的要求是必须要删除匹配的一个左括号和一个右括号。我们当前的表示是只删除了左括号，而不能保证后面有足够的右括号让我们删除。

当s[i + 1] = '(' and t[i + 1] = ')'时：由于两个串的下一个符号不同，肯定不能同时匹配。由于s[i + 1] = '('，所以可以想到，和第一种情况一样，我们读入但删去s[i + 1]的左括号，即令dp[i + 1][j][k + 1] = 1。

当s[i + 1] = ‘)' and t[i + 1] = '('时：当k>0时，因为这两个不一样，所以肯定不能在i+1的位置上同时匹配。所以考虑s的前i+1个字符和t的前i个字符匹配。那么，s的右括号可以让前面一个被删除的左括号复原，然后成对移走，即dp[i + 1][j][k - 1] = 1。

当s[i + 1] = ')' and t[i + 1] = ')'时：和第一种情况同理，当k=0时，有dp[i + 1][j + 1][0] = 1。和第三种情况同理，考虑s的前i+1个字符和t的前i个字符匹配，即dp[i + 1][j][k - 1] = 1。

把以上四种情况的转移方程做一个总结，写出代码如下：

if (k == 0 and s[i + 1] == t[j + 1]) {
    dp[i + 1][j + 1][0] = 1;
}
    if (s[i + 1] == '(') {
        dp[i + 1][j][k + 1] = 1;
}
else if (k) dp[i + 1][j][k - 1] = 1;

?AC代码

括号序列的树表示法

我们用树来存储括号内外嵌套的一个关系。举一个直观的例子：(()()())。我们用树可以表示成：

?整个空间用1号结点表示（其实没有也行）

2号结点：(()()())

3号结点：(()()())

4号结点：(()()())

5号结点：(()()())

在外层的那对括号表示的结点在里层括号所表示的结点的祖先一侧。

我们用这段代码来把括号序列存起来。

我们需要一个vector来存每一个结点的子结点，用一个栈来维护当前正在处理哪些括号的内部。

大体的思路就是：遇到一个左括号，意味着内部嵌套的这一层开始了，于是给这个括号对标个序号，然后加入到当前栈顶的子结点中，不难理解。然后把这个括号对推入栈中，表示这个括号对的内部嵌套从此开始。遇到一个右括号，则意味着当前所管辖的左括号任务结束，将其从栈顶弹出。

代码：

s.push(1);
for (LL i = 0; i < n; ++i) {
    if (s[i] == '(') {
        T[s.top()].push_back(++sid);
        s.push(sid);
    }
    else s.pop();
}

对于这道题目，我们要删除s串中的括号对。删除括号对，在这道题目当中，其实就是删除表示的这棵树的结点。所以我们要将给的s串和t串用树表示起来，然后看能否把s串的几个叶节点摘除，使剩下的树和t的树一模一样即可。

同时我们也注意到，由于嵌套顺序相似（否则没办法变成同样的树），加上我们建树时标号的顺序也就代表了当前结点的子结点的顺序，那么我们不考虑编号的情况下，只需要从左到右遍历，看看能不能让两个结点匹配。

具体的看看代码就看懂了。

AC代码

Codeforces

Educational Codeforces Round 122 (Rated for Div. 2)

A - Div. 7

当前数+0~+6内一定有一个可以被7整除的。

AC代码

B - Minority

长度为1和2时答案一定为0。

长度大于等于3时，统计1的个数和0的个数。如果两个数不一样多，取最少。如果两个数一样多，去那个数-1（抛去最边上一个数）

AC代码

C - Kill the Monster

最优做法一定是k枚硬币全都用掉。所以给第一个操作i次，一定给第二个操作k-i次。枚举i从0到k，如果有一种方法可以打败怪兽，就输出YES，否则输出NO。

AC代码

D - Make Them Equal

显然的01背包。赛中每一个数的代价统计出错，花费了很长时间。

人生首次被Hack。原因是dp数组过大，每次都进行了初始化，无比浪费时间。事实上，k根本到不了1e6，甚至最多也就15000，给15000初始化就足够了，时间上也搞得过去。

教训：时刻注意初始化，也要注意初始化的时间复杂度！如果无法优化，就观察是否真的有必要整个数组都初始化，或求出初始化的边界。

AC代码