CSP-S 2023 游记。

Day0

去的时候，虽然不是很晚但是天已经很黑了，车里完全黑了。

但是这个电脑亮度调不到更低了啊啊！

试寄，显示器直接扭曲了，鼠标甚至点不了右键。

左边的人直接打了一堆神仙板子 orz orz。

试完寄就很晚了，直接睡了。

Day1

一直睡到中午，打了一会 rrolf 就走了。

sto 上午坐在我这里的人！！显示器竟然直接不扭曲了，鼠标也能右键了。

第一次看到 PDF 还要输密码，就把这个密码存了，右边的人没存密码，结果直接刷新就没了，我是大好人啊就给他密码了。

然后开考 T1 直接切了，虽然很水但是好像在哪见过一样的题？

T2 想写正解但是太蒻了啊，看了 30min 没看出来，只好写 $n^3$ 区间 DP 了，35pts。

又想了一下 T2 只要记录一个前缀就能去掉一个 $n$ 了，写了一个对拍发现很对，50pts。

现在总共 150pts 但是只剩 1h。

最初以为写不了大模拟，但是想了一下似乎还行？想了一会就开始写了。

！！！我竟然最后 30min 写完 T3 然后一遍过样例了！

写完 T3 就几乎没时间了，感觉总分 250pts 还行就没写。

我太蒻了 w 连 T4 最低档暴力都不会（

然后说一下赛时各题做法：

T1 lock

直接暴力对每一组数据求可能的答案，然后取交集就做完了，复杂度 $O(nw)$，其中 $w$ 为状态数。

T2 game

首先 35pts 的区间 DP 你已经完全理解了！

然后发现枚举中间点是 $O(n)$ 的，考虑优化。

一个比较显然的结论：

1. $A$ 是可消除的，$B$ 是可消除的 $\Rightarrow$ $AB$ 是可消除的；
2. $A$ 是可消除的，$B$ 是不可消除的 $\Rightarrow$ $AB$ 是不可消除的。

那么我们只要快速找到一个可消除的前缀，然后判断其余的就可以了。

具体的，记录一个 $\mathrm{pre}_i$ 表示以 $i$ 开始最短的非空可消除前缀，复杂度 $O(n^2)$。

T3 struct

不说做法了，但是提供一个自认为写的非常优雅的赛时代码，去了 freopen 并且格式化了一下。

                
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
namespace solution {
static int n;
static string s, t, r;
struct node {
    i64 siz = 0, adj = 0;
    vector<string> nam;
    vector<string> typ;
    vector<i64> off;
    map<string, i64> pos;
};
static map<string, node> M;
static node glo;
static vector<string> nam;
static vector<string> typ;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    M["byte"].siz = M["byte"].adj = 1;
    M["short"].siz = M["short"].adj = 2;
    M["int"].siz = M["int"].adj = 4;
    M["long"].siz = M["long"].adj = 8;
    for (int i = 1, op; i <= n; i++) {
        i64 k;
        cin >> op;
        if (op == 1) {
            cin >> s >> k;
            auto &cur = M[s];
            for (int j = 1; j <= k; j++) {
                cin >> t >> r;
                if (cur.off.empty()) cur.off.push_back(0);
                else {
                    i64 pre = cur.off.back() + M[cur.typ.back()].siz;
                    i64 adj = M[t].adj;
                    if (pre % adj) pre += adj - pre % adj;
                    cur.off.push_back(pre);
                }
                cur.pos[r] = cur.nam.size();
                cur.nam.push_back(r);
                cur.typ.push_back(t);
                cur.adj = max(cur.adj, M[t].adj);
            }
            i64 pre = cur.off.back() + M[cur.typ.back()].siz;
            i64 adj = cur.adj;
            if (pre % adj) pre += adj - pre % adj;
            cur.siz = pre;
            cout << cur.siz << ' ' << cur.adj << '\n';
        } else if (op == 2) {
            cin >> s >> t;
            if (glo.off.empty()) glo.off.push_back(0);
            else {
                i64 pre = glo.off.back() + M[glo.typ.back()].siz;
                i64 adj = M[s].adj;
                if (pre % adj) pre += adj - pre % adj;
                glo.off.push_back(pre);
            }
            glo.pos[t] = glo.nam.size();
            glo.nam.push_back(t);
            glo.typ.push_back(s);
            glo.adj = max(glo.adj, M[s].adj);
            cout << glo.off.back() << '\n';
        } else if (op == 3) {
            cin >> s;
            s.push_back('.');
            i64 pos = 0, off = 0;
            for (int i = 0; i < (int)s.size(); i++)
                if (s[i] == '.') {
                    r = s.substr(pos, i - pos);
                    if (!pos) {
                        off += glo.off[glo.pos[r]];
                        t = glo.typ[glo.pos[r]];
                    } else {
                        off += M[t].off[M[t].pos[r]];
                        t = M[t].typ[M[t].pos[r]];
                    }
                    pos = i + 1;
                }
            cout << off << '\n';
        } else {
            nam.clear();
            typ.clear();
            cin >> k;
            while (true) {
                auto &cur = nam.empty() ? glo : M[typ.back()];
                bool flag = false;
                for (int i = 0; i < (int)cur.typ.size(); i++)
                    if (cur.off[i] <= k && k < cur.off[i] + M[cur.typ[i]].siz) {
                        nam.push_back(cur.nam[i]);
                        typ.push_back(cur.typ[i]);
                        flag = true, k -= cur.off[i];
                        break;
                    }
                if (!flag) break;
            }
            if (nam.empty()) {
                cout << "ERR\n";
                continue;
            }
            if (typ.back() != "byte" && typ.back() != "short" && typ.back() != "int" &&
                typ.back() != "long") {
                cout << "ERR\n";
                continue;
            }
            cout << nam[0];
            for (int i = 1; i < (int)nam.size(); i++) cout << '.' << nam[i];
            cout << '\n';
        }
    }
    return 0;
}
};
int main() { return solution::main(); }
                
cpp
                

                    
                    
                
                

考完以后总是有种预感会挂大分，于是就想测一下。

SD NOIP 群里发了代码，结果下载不了？？

回来之后终于能下载代码了，LG 和 YD 测的都是 250pts 竟然没挂分啊，就直接睡了。