寒假专题练习 #2 解题思路参考

题单二(基础数据结构)

SCUTSE Origin: SCUT SE 2020 day2 基础数据结构 - Virtual Judge
SCNUSE Fork: SCNUSE 香农先修班寒假专题练习 #2 - Virtual Judge (密码 shannon)

STL 容器的使用、并查集和单调栈,依然是萌新友好场。

不要直接看题解,也不要口胡完就来看题解,一定要自己敲一下, 不敲都不知道自己手残得有多厉害

A. CodeForces 879B

根据题意模拟即可,开一个队列表示这 n 个人的队伍,然后模拟整个比赛的过程。注意是 in a row,也就是要连续赢。所以如果擂主输的时候,要把计数器置为 1 ,毕竟攻擂者已经赢了一回了。另外考虑到 k 的值非常大,如果 k \geq n-1 ,直接输出最大值就行。

B. HRBUST 1170

注意 ({)} 这样子也是不合法的,所以不能简单地对圆括号和花括号分别计数。考虑只开一个栈,遇到左括号就进栈,遇到右括号就看看栈顶是不是与这个右括号匹配的左括号,如果是就弹栈;如果不是就说明括号不匹配。读到 Ctrl+Z 再检查一下目前的栈是不是空的就行了。

C. HDU 4006

我们可以维护一个优先队列用于存储前 k 大的数。当有插入操作的时候,我们就试着将这个数添加到优先队列中,此时优先队列有 k+1 个数,我们再把堆顶(也就是最小的元素)弹出来就行了;当有查询操作的时候,直接输出堆顶的数就行。

D. CodeForces 713A

考虑到只需要计数而不需要输出哪些数匹配,考虑对 a_i 进行变换,即直接将奇数位置为 1 ,偶数位置为 0 ,然后补全到 18 位,此时就可以使用 map<string, ll> 对于同一类型的数进行计数了。查询时只需将 s 也补全到 18 位即可。

E. CodeForces 519D

考虑对字符权值作前缀和处理,这里用 pre_i 表示前 i 个字符的权值和。不妨假设字符串 s_{l}s_{l+1}...s_{r-1}s_{r} 是一个符合题目要求的字符串,那么一定有 s_{l}=s_{r}pre_l=pre_{r-1} 。那么我们可以开 map<ll, ll> 数组 mp ,用 mp_{i,j} 记录对于字母 i 前缀和值为 j 的个数。对于字符串中的每一个字符,我们使用尚未更新的 mp 数组更新答案,再更新 mp 数组即可。

核心代码
string s;
map<ll, ll> mp[30];
ll x[30], pre = 0, ans = 0;

for (int i = 0; i < s.size(); i++)
{
    int c = s[i] - 'a';
    // 此时的 pre 是前 i 个字符的前缀和
    // mp[c][pre] 是前 i 个字符中可以与第 i + 1 个字符配对作为开头的字符数
    // 计算以第 i + 1 个字符为末尾的合法字符串
    ans += mp[c][pre];
    // 更新前缀和
    pre += x[c];
    // 更新字符 c 前缀和 pre 的字符数量
    mp[c][pre]++;
}

F. HDU 1213

一种做法是并查集,统计答案的时候只需要统计满足 find(i) == ii 的个数就行了。
还有一种方法就是建图跑 DFS 求连通块个数,也是可以 AC 的。

G. HDU 4496

不妨把整个情况反过来,就假设刚开始的时候所有道路都被炸没了,然后从第 M 条道路开始逐条道路进行恢复,这就回到了并查集的板题。在合并的同时记录答案,若要连边的两点不在一个集合中,答案减一即可。

H. HDU 1506

单调栈。栈里面放矩形下标,然后从左往右扫,只要扫到的矩形高度不小于栈顶矩形高度就进栈;否则就要一边把栈里面比扫到矩形高的矩形出栈,一边更新答案,然后将最后一个出栈矩形设置为与扫描到的矩形等高且单独对其重新入栈。

2021-01-30 22-05-24 的屏幕截图_gaitubao_436x251

就以左边的图和中间的图为例,第 1-4 个矩形都进栈了,这是因为 h_1 \leq h_2 \leq h_3 \leq h_4 但是由于 h_4 > h_5 所以开始弹栈。由于 h_3>h_5,h_4>h_5 所以 3,4 两个矩形就被弹出来了,此时我们计算了黄色和橙色这两个矩形的面积以更新答案。最后一个出栈的是 3 ,我们把第 3 个矩形的高重置成了第 5 个矩形的高,随后将 3 进栈(这样做的目的其实就是为了考虑右图绿色矩形这样的情况)。

要注意的是,为了能使栈里面所有矩形到最后都能出栈,要给矩形高度数组的末尾添加一个负数。

1赞
粤 ICP 备 2020080455 号