WC2021游记

_jhq · 2021-02-07 18:02:35 · 个人记录

DAY 1~4（2021.2.1~2021.2.4）

第一课堂大多是优秀学生（包括IOI2020金牌）讲课，第二课堂都是CCF的钻石/金牌教练讲课。

第一课堂非常难，第二课堂有点水。

所以我每天都去听第一课堂，然后听着听着就自闭了。

两次营员交流也是这样，听着听着就掉线了。

自己还是太菜了，不过每天学习许多难的知识，还是收获颇丰的。

DAY 5（2021.2.5）

考前订个小 （大）目标：Cu（换而言之就是拿牌就行，不要打铁）。

这次考试时间是8:30~13:30，5个小时对于我这种只会打暴力的蒟蒻来说时间非常充足。

考前看了看 dijkstra 和 kruskal 的板子，但是一个也没有考。

开考前几分钟发了密码：XinNianKuaiLe。新年快乐？刹那间感觉出题人会把题目出得很难。

果然如此，把三道题浏览了一遍，还真是一道都不会正解。

题目链接：T1、T2、T3。

首先看T1，因为有环，暴力DFS会陷入死循环，想了很长一段时间也没有想出怎么处理，就先跳过了。

接着看T2，发现没有问号时有显然的 O(n|E|) 的暴力做法，遇到括号递归处理即可，这样能够拿到50分。而有问号时暴力做法有 2^t 种情况，但是数据最小是 t\le5\times10^3，直接TLE，没想到怎么做。

所以我就先码了50分代码，为了方便递归函数返回数组我用了结构体。由于 O(n|E|) 的时间复杂度显然过不了 n\le5\times10^4，|E|\le5\times10^4 的数据，再加上每次调用 Expr 和 work 函数时都要新开一个结构体变量存数组，所以考场上我害怕数组开到 5\times10^4 可能导致MLE，便把数组开到了 5\times10^3。

考场T2代码如下（共95行）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
typedef long long LL;
using namespace std;

void read(int &s)
{
    s = 0; bool pd = false; char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') pd = true;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        s = (s << 3) + (s << 1) + (c ^ 48);
        c = getchar();
    }
    if (pd) s = -s;
    return;
}

const int N = 5e3 + 10;
const int M = 20;
const LL MOD = 1e9 + 7;

int st[N], R[N];
int n, m, len, top;
LL Ans;
char s[N];

struct node
{
    int num[N];
}a[M];

node Expr(char c, node x, node y)
{
    node ans;
    if (c == '<')
        for (int i = 1; i <= n; i++)
            ans.num[i] = min(x.num[i], y.num[i]);
    if (c == '>')   
        for (int i = 1; i <= n; i++)
            ans.num[i] = max(x.num[i], y.num[i]);
    return ans;
}

node work(int l, int r)
{
    node ans;
    for (int i = 1; i <= n; i++)
        ans.num[i] = a[s[l] - '0'].num[i];
    for (int i = l + 1; i <= r; i++)
    {
        if (s[i + 1] == '(')
        {
            ans = Expr(s[i], ans, work(i + 2, R[i + 1] - 1));
            i = R[i + 1];
        }
        else
        {
            ans = Expr(s[i], ans, a[s[i + 1] - '0']);
            i++;
        }
    }
    return ans;
}

int main()
{
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    read(n); read(m);
    for (int i = 0; i < m; i++)
        for (int j = 1; j <= n; j++)
            read(a[i].num[j]);
    scanf("%s", s);
    len = strlen(s);
    for (int i = 0; i < len; i++)
    {
        if (s[i] == '(')
            st[++top] = i;
        if (s[i] == ')')
            R[st[top--]] = i;
    }
    node ans;
    ans = work(0, len - 1);
    for (int i = 1; i <= n; i++)
        Ans = (Ans + ans.num[i]) % MOD;
    printf("%lld", Ans);
    return 0;
}

然后看T3，“众所周知，小葱同学擅长计算，尤其擅长计算组合数。”居然是zhx神仙出的题，瞬间感到瑟瑟发抖。

不过20分的暴力非常好写，我枚举到了 5m（埋下伏笔）。

考场T3代码如下（共51行）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

void read(int &s)
{
    s = 0; bool pd = false; char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') pd = true;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        s = (s << 3) + (s << 1) + (c ^ 48);
        c = getchar();
    }
    if (pd) s = -s;
    return;
}

const int T = 5e3;
int n, m, a, b, ans, f[T + 10];

int main()
{
    freopen("fib.in","r",stdin);
    freopen("fib.out","w",stdout);
    read(n); read(m);
    while (n--)
    {
        read(a); read(b);
        memset(f, 0, sizeof(f));
        ans = -1;
        f[0] = a % m; f[1] = b % m;
        for (int i = 0; i <= T; i++)
        {
            if (i >= 2)
                f[i] = (f[i - 1] + f[i - 2]) % m;
            if (f[i] == 0)
            {
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

之后我又回来看T1，思考如何处理死循环问题时突然就想到了可以用 IDDFS（迭代加深搜索），经过计算发现过不了 n=8 的数据，只能过 n=4 的数据，搜索最深应该是走11次边，12次时间就有点超了。

我在考场上没有枚举最大搜索次数，而是只设立了最大搜索次数是11次，这样也能过 n=4 的数据，可以拿到16分。

考场T1代码如下（共100行）：

#include <iostream>
#include <cstdio>
typedef long long LL;
using namespace std;

void read(int &s)
{
    s = 0; bool pd = false; char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') pd = true;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        s = (s << 3) + (s << 1) + (c ^ 48);
        c = getchar();
    }
    if (pd) s = -s;
    return;
}

const int N = 3e5 + 10;
const int M = 6e5 + 10;
const int T = 11;

int n, m, k, s, t, tot;
int head[N], a[N], b[N], st[3];
LL ans;

struct Edge
{
    int to, nex, w, dir;
}edge[M << 1];

void addedge(int u, int v, int w, int dir)
{
    edge[++tot].to = v;
    edge[tot].w = w;
    edge[tot].dir = dir;
    edge[tot].nex = head[u];
    head[u] = tot;
    return;
}

bool check()
{
    st[1] = st[2] = 0;
    for (int i = 1; i <= tot; i++)
    {
        if (b[i] == 1) st[a[i]]++;
        else
        {
            if (st[a[i]] == 0) return false;
            else st[a[i]]--;
        }
    }
    if (st[1] == 0 && st[2] == 0) return true;
    else return false;
}

bool dfs(int u, int cnt)
{
    if (u == t)
        if (check())
            return true;
    if (cnt > T)
        return false;
    for (int i = head[u]; i; i = edge[i].nex)
    {
        int v = edge[i].to;
        a[++tot] = edge[i].w;
        b[tot] = edge[i].dir;
        if (dfs(v, cnt + 1)) return true;
        tot--;
    }
    return false;
}

int main()
{
    freopen("bracket.in","r",stdin);
    freopen("bracket.out","w",stdout);
    read(n); read(m); read(k);
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        read(u); read(v); read(w);
        addedge(u, v, w, 1);
        addedge(v, u, w, 2);
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            s = i; t = j; tot = 0;
            if (dfs(s, 0)) ans++;
        }
    printf("%lld", ans);
    return 0;
}

最后的时间里我一直在想T1如何优化能过掉 n=8 的数据，T2如何快速处理有问号的情况，T3当 m 是质数时的做法，但是都没有想到该怎么做，或许就是因为我太菜了，实力不行吧。

考后估分：16+50+20=86 分。

考试结束后cbj巨佬直接把T1秒掉了，他给我提示了一个重要结论：对于一个合法括号序列一定是由若干个合法括号序列拼接而成的。这样就能优化暴力搜索拿到更高的分了，由此可见我真的是很菜。

下午讲题，T1、T2、T3正解听得一脸懵逼，果然我太菜了。

T2数据可能会有连续多个左括号？？？开头可能有左括号？？？/jk

加上连续多个左括号以及开头加上左括号优先级不会发生改变，这样的数据感觉应该不会出现啊，但是讲题人说这样的数据算合法的。当时评论区瞬间刷屏了，这样只要有带括号的数据许多人的代码都过不去，估计T2掉分会很惨烈，我应该会直接50分变成20分。/kk

T3斐波那契数列膜一个数的循环节的长度居然是不超过 6m？？？/jk

讲题人说这是一个经典结论。好像很多人都不知道这个结论（包括我这个蒟蒻），因为当时评论区又一次刷屏了。许多人问只枚举到 2m 或 5m 能拿多少分。我是枚举到了 5m，如果数据中 F_p=0 的 p 最小时超过了 5m，我就直接20分变成0分了。/kk

讲题后估分：16+20+0=36 分。

DAY 6（2021.2.6）

上午看了IOI2021中国队选拔，评委们的一些非常坑人的提问很有意思。

下午出了WC2021分数线，这次比赛Au线158分，Ag线118分，Cu线70分。

分数线这么高？/jk

我36分岂不是要打铁了？/kk

看完分数线之后就开始念榜了，是按分数从低到高倒着念。由于我在外面有事所以用手机看，当回到小区门口时念到了Cu 88分，此时手机突然断网了QAQ。我便赶紧跑回家打开电脑看，这时已经开始念Ag榜了。

88分已经高出了自己的考后估分，从Cu 70分到 Cu 88分一直没有听到自己的名字，看来自己真的是打铁了。/kk

迫于想知道自己的得分，我在山东NOIP群里找到了SD所有WC选手的得分，我从70分往下翻。咦，怎么没有我的名字？我又往上翻，发现自己居然是94分！

原来我没有打铁，而是Cu了！/cy

T1 IDDFS 居然多跑过去了两个点，拿到了24分；T2数据没有像讲题人那样那么毒瘤，我的50分做法没有挂掉；T3数据没有 F_p=0 的 p 最小时超过 5m 的情况，我的暴力做法没有挂掉。

实际得分：24+50+20=94 分。

这次WC2021我暴力一分没挂还多拿了8分，总体来说发挥还行，但是也显现出我还是太菜了，还需要继续努力。