AtCoder Beginner Contest 312 复盘 + 参与后感

AC_love · 2023-07-30 00:19:38 · 个人记录

本次比赛的题目链接在本文底部，省流党可以直接拉到最下面

说两句闲话：我觉得 AtCoder Beginner Contest 这个系列真的很适合大部分提高组水平以下的同学们，里面题目难度安排得很合适。如果让我对题目难度大致做一个评估的话，基本就是如下表所示：

注：该表格中的组别和题目难度均为一般情况下的难度，不考虑到最近几年 CSP 与 NOIP 内卷严重，题目难度大大上升的情况（比如我曾在 2020 年的 CSP 上单枪匹马面对一道黑题贪吃蛇），也不考虑早期 NOIP 尚未成熟时题目相对都很简单的情况（津津的储蓄计划表示很淦）。

小扯了几句废话，还是复盘一下，顺便说说这次模拟赛的感受

这个比赛还是挺有特点的，赛制是 IOI 赛制（也就是说你交完代码之后直接就能出结果），每道题目根据难易程度不同也有不同的分值（详见上方），一道题只有所有测试点全部 AC 才有分数（也就是说你不能用糊弄总司令的方式来糊弄 AtCoder 的比赛了）。这次我过了 ABC 三道比较水的题目，拿到了 600 分的成绩，在 9300 位提交代码的选手中排名 3538 ，说实话，我觉得可以更高的。

模拟赛的持续时间是 100 分钟，说实话，对我而言还是有点短了。今天偷偷翘了文化课来打比赛，其实只写了一个小时多一点的时间。如果多给一点点时间，我应该是可以把 D 题也做出来再水 400 分的。

复盘一下这次比赛吧。

A - Chord

题意：给你一个长度为 3 的只含大写字母字符串，如果这个字符串是 ACE, BDF, CEG, DFA, EGB, FAC, GBD 中的一个输出 Yes ，反之输出 No

个人感觉， A 题存在的意义就是让你不爆零。这道题没有复盘的必要，唯一遗憾的是我没看懂原题里 uppercase 是什么意思，导致我画蛇添脚写了一个把小写字母转成大写字母的过程，等 A 了这道题之后到翻译姬里面一查发现这个单词的意思是大写字母，尴尬的我差点用脚指头扣出一座芭比娃娃的梦幻城堡。

代码如下：

#include <bits/stdc++.h>
using namespace std;
string a;
int main()
{
    cin >> a;
    if(a == "ACE" || a == "BDF" || a == "CEG" || a == "DFA" || a == "EGB" || a == "FAC" || a == "GBD")
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

B - TaK Code

题意：给你一个 n \times m 的只有黑白两种颜色的网格，让你输出其中所有二维码的位置。

二维码要满足以下条件：

1. 必须是 9 \times 9 的正方形
2. 左上角 3 \times 3 和右下角 3 \times 3 必须都是黑的
3. 左上角和右下角的 3 \times 3 的黑格的周围必须都是白格（仅限处在这个 9 \times 9 范围内的 14 个格，外面的我们不予考虑）

二维码的位置定义为二维码左上角第一个格的坐标。

这道题题意不难理解，当时我选择直接暴力判断，搞了这样一份代码：

#include <bits/stdc++.h>
using namespace std;

char ch[150][150];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i = i + 1)
        for(int j = 1; j <= m; j = j + 1)
            cin >> ch[i][j];
    for(int i = 1; i <= n; i = i + 1)
        for(int j = 1; j <= m; j = j + 1)
            if(
            ch[i][j] == '#' && ch[i + 1][j] == '#' && ch[i + 2][j] == '#' && ch[i][j + 1] == '#' && 
            ch[i + 1][j + 1] == '#' && ch[i + 2][j + 1] == '#' && ch[i][j + 2] == '#' && ch[i + 1][j + 2] == '#' && 
            ch[i + 2][j + 2] == '#' && ch[i + 6][j + 6] == '#' && ch[i + 7][j + 6] == '#' && ch[i + 8][j + 6] == '#' && 
            ch[i + 6][j + 7] == '#' && ch[i + 7][j + 7] == '#' && ch[i + 8][j + 7] == '#' && ch[i + 6][j + 8] == '#' && 
            ch[i + 7][j + 8] == '#' && ch[i + 8][j + 8] == '#' && 
            ch[i + 3][j] == '.' && ch[i + 3][j + 1] == '.' && ch[i + 3][j + 2] == '.' && ch[i + 3][j + 3] == '.' &&
            ch[i][j + 3] == '.' && ch[i + 1][j + 3] == '.' && ch[i + 2][j + 3] == '.' &&
            ch[i + 5][j + 5] == '.' && ch[i + 6][j + 5] == '.' && ch[i + 7][j + 5] == '.' && ch[i + 8][j + 5] == '.' &&
            ch[i + 5][j + 6] == '.' && ch[i + 5][j + 7] == '.' && ch[i + 5][j + 8] == '.')
                cout << i << " " << j << endl;
    return 0;
}

// ps : 第一遍做的时候愚蠢的我把 && 全写成 || 了，好在是 IOI 赛制，全 WA 了之后我检查出问题了。

C - Invisible Hand

题意：有 n 个卖东西的和 m 个买东西的。每个卖东西的人都有一个他可以接受的最低价，他会在在此之上的任何价格（包括这个最低价）把东西卖出去；每个买东西的人也都有一个他可以接受的最高价，他会在此之下的任何价格（包括这个最高价）把这个东西买下来。试问：求一个最小的满足能把东西卖掉的人比能买到东西的人多的价格。

（顺带一提：我觉得这个题目 Invisible Hand 就是意指市场经济中“看不见的手”，即古典经济学家亚当·斯密在《国富论》中提出的理论，认为国家经济的发展不应由zf（敏感词，用缩写代替）干预，而应由整个社会需求进行选择。这种社会需求被认为是调节市场的“看不见的手”。恰巧这道题背景也设计买卖交易，我想就是出题人留下的一个彩蛋吧）

言归正传，这道题应该是一个不错的二分答案样板题，题目里已知所有最高价和最低价都在 10^9 范围内，暴力枚举很可能就会 T 掉，我认为二分答案是最好想的一种方法了。

每次我们都在当前价格区间取中点并判断该点是否满足题意，如果满足我们就让左端点移到中点继续判断，如果不满足我们就让右端点移到中点继续判断。

需要注意的是，满足条件时，不仅左端点需要移动，正解答案也需要同时移动，否则最后左端点移到中间去了，正解答案还是 0 ，那这个题就爆掉了。

至于如何判断一个价格是否符合题意也很简单，只需要枚举一遍最低价数组里比这个价格还要小的数和最高价数组里比这个价格还要大的数即可，这一步其实可以先排序预处理以下，然后再使用二分来解决问题，如果这样的话总的复杂度就是 O(n \log n) （即排序的复杂度），但是如果直接暴力枚举的话其实也是 O(n \log n) 的复杂度（即二分的复杂度与判断的复杂度相乘），此番优化意义不大，没有这样写让代码变得更麻烦的必要。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int buy[200100];
int sell[200100];
int s, b;

bool check(int k)
{
    s = 0;
    b = 0;
   // s 是 sell ， b 是 buy ，我可没有在骂人哈
    for(int i = 1; i <= n; i = i + 1)
        if(sell[i] <= k)
            s ++;
    for(int i = 1; i <= m; i = i + 1)
        if(buy[i] >= k)
            b ++;
    if(s >= b)
        return true;
    else
        return false;
}
int zuo = 0, you = 1000010000;
// 个人习惯，由于left是四个字母，right是五个字母不对称，所以有强迫症的我直接把左右命名为zuo you
int ans;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i = i + 1)
        cin >> sell[i];
    for(int i = 1; i <= m; i = i + 1)
        cin >> buy[i];
    while(zuo < you - 1)
    {
        int mid = (zuo + you) / 2;
        if(check(mid) == true)
        {
            // cout << mid << "is ok" << endl;
            // 前两遍写的时候 WA 了，写了个调试自己查了一下
            you = mid;
            ans = mid;
        }
        else
        {
            // cout << mid << "is not ok" << endl;
            zuo = mid;
        }
    }
    cout << ans << endl;
    return 0;
}

D - Count Bracket Sequences

题意：有一个字符串里包含左括号，右括号，问号三种字符（注：括号只指小括号），每个 ? 都可以被替换成左括号或者右括号，问有多少种替换方式使替换之后的字符串是一个合法的字符串。

合法字符串的定义：

1. 空字符串是合法字符串。
2. 任何一个合法字符串外面套上一层括号还是一个合法字符串。
3. 两个合法字符串相连是一个合法字符串。

ps : 人话就是，括号能够匹配

这道题看起来很简单，有很多老题目都与之相像，但是这道题似乎有有所不同。

我一开始考虑用数学知识解决。

假设字符串只含 ? ，显而易见，当目前 ? 的长度是偶数时，可能的方案数目是 2^{\frac{l}{2} - 1} 其中 l 是字符串长度。

但是很快发现这种做法不适用于此题，于是考虑用动态规划。

然而时间不够了，就没有来得及做（悲）。

等我过两天把这道题 A 了再发思路和代码吧，诸位大佬如果有思路的话也请指正一下，我目前的想法是动态规划，但是又暂时毫无头绪，等有想法再说吧。

感谢神的指导，让我对这道题有了一点思路。

首先这道题的括号只包含小括号，因此我们只需要枚举没有配对的左括号个数即可。我们假设一段问号的长度是 i ，此前未匹配的左括号个数为 j ，那么我们就找到了动规的状态设计，接下来我们就可以开始考虑转移方程的事情了。

前面这一块其实不难实现，问题在于转移方程应该怎么写，以及转移顺序应该怎么来。

首先，我们先考虑找规律。

横行为 i ，纵行为 j ，不难看出只有 i + j 是偶数时才有合法的填法，否则没有，输出 0 。

在 Excel 表格里小试了一下，有的地方没推出来，但是大致可以推测规律是右面的等于上面的加下面的。

用转移方程表示应该是 dp_{i, j} = dp_{i - 1, j + 1} + dp_{i - 1, j - 1}

但是也发现了一个问题，就是我自己手算出 i = 7, j = 1 时的值应该为 12 ，然而按照这个规律这个值应该是 13 ，我算出的数和我推理出的结论自相矛盾了？这咋办？

所以这个时候我们考虑写一个打表代码，自己看看到底是什么规律。

打表代码采用暴力手段，我们知道每个问号都可以替换成左括号或者右括号的一种，那么我们暴力枚举每种情况判断是否合法即可，复杂度为 2^n ，在 n \le 20 的时候应该是跑得飞快的。

那么我们不妨采用栈来判断各种情况是否合法。

当我们读取到一个左括号时，我们将左括号入栈。

当我们读取到一个右括号时，如果栈不是空的，我们就把栈顶的左括号弹出来。

如果栈是空的，说明不合法。

如果全部读取完了，栈还不是空的，说明不合法。

代码实现不难。

省流党注意：以下是题目和链接