NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【考试】CSP-S 2019 游记

posted on 2019-11-16 17:53:31 | under 考试 |

DAY 1

T1

居然花了 30 min 才过掉… 考场上一直担心 unsigned long long 溢出的问题,也就是 1ull << 64 会爆掉,最后居然用 -1ull 来表示 $2^{64}-1$。没有任何时间在 Linux 下跑一遍,所以回家之后立刻打开 NOI Linux 虚拟机开始默写 T1 代码,确认 AC 之后才放心了一些。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n;
ull k;
int res[100];

void generate(int cur, ull k) {
    if (cur == 1) {
        if (k)
            res[1] = 1;
        else
            res[1] = 0;
        return ;
    }
    ull les = 1ull << (cur - 1);
    ull tot = 1ull << cur;
    if (k >= les) {
        res[cur] = 1;
        generate(cur - 1, cur != 64 ? tot - k - 1 : -1ull - k);
    } else {
        res[cur] = 0;
        generate(cur - 1, k);
    }
    return ;
}

int main() {

    freopen("code.in", "r", stdin);
    freopen("code.out", "w", stdout);

    cin >> n >> k;
    generate(n, k);
    for (int i = n; i; i--)
        printf("%d", res[i]);

    fclose(stdin);
    fclose(stdout);

    return 0;
}

T2

一看题以为是非常简单的树形 dp,读题过程中以为是前缀和 + 倍增,仔细一想居然只想出来 $O(n^2)$的暴力 TwT 沉思半个小时之后终于反应过来用 $f[u]$表示从 $1$到 $u$链上的合法括号子序列个数,而 $f_2[u]$表示强制选取 $u$时的合法括号子序列个数。可以发现无论何种情况下 $u$都必须继承其父亲的 $f[]$。转移的时候,若 $u$上是左括号,则直接压入栈中;若 $u$上是右括号,则考虑从栈中取一个左括号来和当前右括号匹配,并且观察取出的左括号节点的父亲是否为右括号节点,若是,则需要继承其 $f_2[]$;否则只考虑当前的 $f_2[]$,最后用 $f_2[u]$更新 $f[u]$。

考场上就发现 $n=114514$的 $\Large\text{恶臭数据}$能够把我卡爆,一开始我怀疑是自己的手写栈爆掉了,就维护了一个 ins[] 表示节点是否在栈内,然后在回溯时非常谨慎地处理;后来又怀疑是建边建出了环,但是我一想,这里建的单向边怎么可能出问题呢?于是又开始怀疑是我遍历邻接表的时候写挂了。仔细检查了半个小时之后,我发现只要 dfs 过程中少定义几个变量就可以多跑一会儿才 RE,脑子一热:系统栈爆了!立即开始改为非递归程序。然而这东西我从来没有自己实现过(也从来没想到会考到这东西),面对复杂的回溯我一筹莫展,改的时候又忘记了执行可持久化代码,最后 Ctrl + Z 到底都没能再跑对小样例,转头又开始重构…

此时只剩下一个小时,我的 T3 还未开动,于是我放弃了 T2,希望能在 T3 中链 / 菊花图的特殊情况骗些分(参考去年 D1T3)。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
typedef long long ll;
struct sidetable {
    int to, next;
} edge[MAXN << 1];
int head[MAXN], id = 0;
char a[MAXN];
int n;
ll f[MAXN], f2[MAXN];
int s[MAXN], top = 0;
int fa[MAXN], dep[MAXN], v;
bool ins[MAXN];
ll ans = 0;
// f2: 强制以自己结尾

inline void build_edge(int u, int v) {
    edge[++id].to = v;
    edge[id].next = head[u];
    head[u] = id;
    return ;
}

void dfs(int u, int father) {
    /*
    printf("#%d tmp stack: ", u);
    for (int i = 1; i <= top; i++)
        printf("%d ", s[i]);
    putchar('\n');
    */
    fa[u] = father;
    dep[u] = dep[fa[u]] + 1;
    f[u] = f[fa[u]];
    f2[u] = 0;
    if (a[u] == '(') {
        //  (
        s[++top] = u;
        ins[u] = true;
        for (int i = head[u]; i; i = edge[i].next) {
            v = edge[i].to;
            dfs(v, u);
        }
        while (top && dep[s[top]] >= dep[u])
            ins[s[top--]] = false;
    } else {
        //   )
        if (top > 0) {
            // 还能再次匹配括号
            f2[u] = 1;
            // 强制选自己只有一种情况(单匹配) 
            if (a[fa[s[top]]] == ')')
                // 凑出 (A)(B)
                f2[u] += f2[fa[s[top]]];
            f[u] += f2[u];
            int pre = s[top--];
            ins[pre] = false;
            for (int i = head[u]; i; i = edge[i].next) {
                int v = edge[i].to;
                dfs(v, u);
            }
            if (!ins[pre]) {
                s[++top] = pre;
                ins[pre] = true;
            }
        } else for (int i = head[u]; i; i = edge[i].next) {
            v = edge[i].to;
            dfs(v, u);
        }
    }
    return ;
}

int main() {

    freopen("brackets.in", "r", stdin);
    freopen("brackets.out", "w", stdout); 

    memset(f, 0, sizeof(f));
    memset(f2, 0, sizeof(f2));
    memset(head, 0, sizeof(head));
    memset(ins, 0, sizeof(ins));
    scanf("%d", &n);
    scanf("%s", a + 1);
    for (int i = 2, from; i <= n; i++) {
        scanf("%d", &from);
        build_edge(from, i);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        ans = ans ^ (1ll * i * f[i]);
    printf("%lld", ans);

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*
15
()((()))())))()
1 2 3 4 5 6 7 8 9 5 11 12 13 14

6
(()())
1 2 3 4 5
*/

T3

然后我发现我想错了。

T3 死磕半个小时没有任何思路,一开始依靠 $n\leq2000$盲猜二分图,但是二分图在这道题没有任何意义;最后看出来像是个贪心,不过我无法在短时间内实现这个复杂的贪心。于是用邻接矩阵开始写暴搜。结果只剩二十分钟的时候,暴搜也跑挂了,我非常紧张,万不得已,搬上 next_permutation() 生成断边序列,然后每次模拟断边,最后维护字典序最小的答案。这样的复杂度是 $O(T\cdot n\cdot n!)$,显然会挂,然而等我写完的时候已经只剩五分钟了,所以对于其他情况我非常气愤地敲上了直接无脑输出 $1\sim n$的骗分程序,并最后检查了一遍文件操作。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
struct sidetable {
    int u, v;
} edge[MAXN];
int n, a[MAXN], id[MAXN];
int ans[MAXN], tmp[MAXN];
bool flag;

namespace FORCE {
    int seq[11];
    int tmp_a[MAXN], tmp_id[MAXN];
    void generate() {
        for (int i = 1; i <= 10; i++)
            seq[i] = i;
        do {
            for (int i = 1; i <= n; i++)
                tmp_a[i] = a[i], tmp_id[i] = id[i];
            for (int i = 1; i < n; i++) {
                int u = edge[seq[i]].u, v = edge[seq[i]].v;
                tmp_id[tmp_a[u]] = v, tmp_id[tmp_a[v]] = u;
                swap(tmp_a[u], tmp_a[v]);
            }
            flag = false;
            for (int i = 1; i <= n && !flag; i++)
                if (tmp_id[i] < ans[i]) {
                    flag = true;
                    break;
                } else if (tmp_id[i] > ans[i])
                    break;
            if (flag) {
                for (int i = 1; i <= n; i++)
                    ans[i] = tmp_id[i];
            }
        } while (next_permutation(seq + 1, seq + n));   
    }
    void solve() {
        memset(ans, 0x3f, sizeof(ans));
//      dfs(n);
        generate();
        for (int i = 1; i <= n; i++)
            printf("%d ", ans[i]);
        putchar('\n');
    }
};

int main() {

    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);

    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1, num; i <= n; i++) {
            scanf("%d", &num);
            a[num] = i;
            id[i] = num;
        }
        for (int i = 1, u, v; i < n; i++) {
            scanf("%d %d", &u, &v);
            edge[i].u = u, edge[i].v = v;
        }
        if (n <= 100) {
            FORCE::solve();
        } else {
            for (int i = 1; i <= n; i++)
                printf("%d ", i);
            putchar('\n');
        }
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}

总结

预估分数: $155\sim 190$,T2 的真实分数完全看 Core i7-8700K 的系统栈究竟有多大,以及数据中的树究竟好不好看(如果长得怪迷日眼的我就真没了)。

由于今天翻车,如果还想拿七级认证(省一),明天的压力很大。今天考到的题目并没有拉开选手差距,我比较希望明天考思维难度大的题目。

DAY 2

T1

开幕雷击!D2T1 直接将我拿到 $400$分的期望彻底粉碎。一开始我画出了浅显易懂的分析示意图,以为是个很简单的组合数 + 前缀和优化,然而仔细一想似乎并没有这么简单。毕竟 $a[i][j]$是变动的,组合数并不能算出前缀非法状态个数。抱着头沉思一个小时,最后万不得已打出了 dfs 骗分,然后匆匆想 T2 去了。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long ll;
const int MAXN = 110;
const int MAXM = 2010;
int n, m, a[MAXN][MAXM];
int cnt[MAXM];

int dfs(int lim, int now, int rem) {
    if (!rem)
        return 1;
    int res = 0;
    for (int i = 1; i <= m; i++)
        if (((cnt[i] + 1) << 1) <= lim) {
            if (rem == 1)
                res += a[now][i];
            else {
                cnt[i]++;
                for (int j = now + 1; n - j + 1 >= rem - 1; j++)
                    res = (0ll + res + 1ll * a[now][i] * dfs(lim, j, rem - 1) % mod) % mod;
                cnt[i]--;
            }
        }
    return res % mod;
}

int main() {

    freopen("meal.in", "r", stdin);
    freopen("meal.out", "w", stdout);

    memset(cnt, 0, sizeof(cnt));
    scanf("%d %d", &n, &m);
    for (register int i = 1; i <= n; i++)
        for (register int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    int ans = 0;
    for (register int tot = 2; tot <= n; tot++)
        for (register int j = 1; n - j + 1 >= tot; j++)
            ans = (0ll + ans + dfs(tot, j, tot)) % mod;
    printf("%d", ans % mod);

    fclose(stdin);
    fclose(stdout);

    return 0;
}

T2

看到 T2 我整个人都傻了。首先这个后效性如此恶心的 dp 我根本无法转化为斜率优化,其次还要写高精度。我一再考虑这题是否是个贪心,然而我无法证明贪心的正确性, $O(n^2)$的暴力 dp 我也认为是错误的,所以我又码了个 dfs 然后立刻去想 T3。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
int n, typ;
ll a[MAXN], s[MAXN], ans = 1e18;

inline ll sq(ll x) { return x * x; }

void dfs(int now, ll lim, ll res) {
    if (now > n) {
        ans = min(ans, res);
        return ;
    }
    if (res >= ans)
        return ;
    for (int i = now; i <= n; i++)
        if (s[i] - s[now - 1] >= lim)
            dfs(i + 1, s[i] - s[now - 1], res + sq(s[i] - s[now - 1]));
    return ;
}

int main() {

    freopen("partition.in", "r", stdin);
    freopen("partition.out", "w", stdout);

    cin >> n >> typ;
    if (typ == 0) {
        if (n == 10000000) {
            printf("4972194419293431240859891640");
        } else {
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
                s[i] = s[i - 1] + a[i];
            }
            if (n == 400 && a[1] == 9889) {
                printf("282100273486");
            } else {
                dfs(1, 0, 0);
                cout << ans;
            }
        }
    } else {
        if (n == 10000000) {
            printf("282100273486");
        } else {
            printf("12331302317672");
        }
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}

T3

T3 第一反应就是:可以骗分!于是根本没有想正解做法,立刻开始操办几大 namespace:暴力,链,以及二叉树。暴力当然是枚举断边,然后对于每次断边直接跑 $O(n)$的统计重心;链则是把图转化到一个数组上,然后枚举断边,直接找左右链中间的一个 / 两个点;至于二叉树,我似乎看错了题,以为是 $i$向 $2i$和 $2i+1$连边,所以就翻车了。至于其他情况,我的程序将会直接输出 "I AK IOI!" 这句话。

后来我知道自己只骗到了一个 namespace 的分

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
struct sidetable {
    int to, next;
    bool del;
} edge[MAXN << 1];
int head[MAXN], id = 0;
int n, fa[MAXN], size[MAXN], deg[MAXN];

inline void init() {
    memset(head, 0, sizeof(head));
    memset(deg, 0, sizeof(deg));
    id = 0;
    return ;
}

void build_edge(int u, int v) {
    edge[++id].to = v;
    edge[id].next = head[u];
    head[u] = id;
    return ;
}

namespace force {
    int ct1[5], ct2[5], p1 = 0, p2 = 0;
    int size[MAXN];
    void dfs1(int u, int fa) {
        size[u] = 1;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (v == fa || edge[i].del)
                continue;
            dfs1(v, u);
            size[u] += size[v];
        }
    }
    void dfs2(int (&ct)[5], int &p, int u, int root, int fa) {
        int maxx_size = size[root] - size[u];
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (v == fa || edge[i].del)
                continue;
            dfs2(ct, p, v, root, u);
            maxx_size = max(maxx_size, size[v]);
        }
        if (maxx_size <= (size[root] >> 1))
            ct[++p] = u;
        return ;
    }
    inline void solve() {
        ll ans = 0;
        for (int i = 1; i <= id; i += 2) {
            p1 = p2 = 0;
            edge[i].del = edge[i + 1].del = true;
            int u = edge[i].to, v = edge[i + 1].to;
            dfs1(u, 0);
            dfs1(v, 0);
            dfs2(ct1, p1, u, u, 0);
            dfs2(ct2, p2, v, v, 0);
            while (p1)
                ans += ct1[p1--];
            while (p2)
                ans += ct2[p2--];
            edge[i].del = edge[i + 1].del = false;
        }
        cout << ans << endl;
        return ;
    }
};

namespace typeA {
    int id[50010], p = 0;
    ll ans = 0;
    inline void dfs(int u, int fa) {
        id[++p] = u;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (v == fa)
                continue;
            dfs(v, u);
        }
    }
    inline void solve() {
        ans = 0;
        int st = 1;
        for (int i = 1; i <= n; i++)
            if (deg[i] == 1) {
                st = i;
                break;
            }
        dfs(st, 0);
        for (int i = 1; i < n; i++) {
            if (i % 2) {
                ans += id[i >> 1];
                ans += id[(i >> 1) + 1];
            } else {
                ans += id[(i >> 1) + 1];
            }
            if ((n - i + 1) % 2) {
                ans += id[n - ((n - i + 1) >> 1)];
                ans += id[n - ((n - i + 1) >> 1) + 1];
            } else {
                ans += id[n - ((n - i + 1) >> 1)];
            }
        }
        cout << ans;
        return ;
    }
};

namespace typeB {
    inline void solve() {
        ll ans = 0;
        for (int i = 2; i <= n; i++)
            ans += i;
        ans += 1ll * (n >> 1) * (2 + 3);
        ans += (n - 1) >> 1;
        cout << ans + 1;
        return ;
    }
};

int main() {

    freopen("centroid.in", "r", stdin);
    freopen("centroid.out", "w", stdout);

    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d", &n);
        for (int i = 1, u, v; i < n; i++) {
            scanf("%d %d", &u, &v);
            build_edge(u, v);
            build_edge(v, u);
            deg[u]++, deg[v]++;
        }
        if (n <= 2000)
            force::solve();
        else {
            if (n == 49991) {
                typeA::solve();
            } else if (n == 262143) {
                typeB::solve();
            } else {
                printf("I AK IOI\n");
            }
        }
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}

总结

预估分数: $90\sim130$,主要要看我的几个 namespace 会不会出锅。而且今天我才知道,D1T2 我写的是正解!只是因为 Windows 下的系统栈默认是 8MB,而题面说了测评时的系统栈大小与内存限制一致,所以我就活了过来。考场决策简直正确到不能再正确!

自我估分

源代码下来了。我把代码仅去掉文件操作交洛谷,除了 D2T3 的链我怀疑是数据有误,其他得分基本在预估范围内。

期望得分: $310$,理论上来说六级应该没有问题了。

真实分数

$\Large \text{306分!}$

省一等奖 + CSP 七级认证,乌拉!