CSP-S 2023 题解

被创似的一集。

T1 密码锁

萌萌送分题。

由于限制比较死，一种状态能产生的合法密码数量很少。要求的是这些合法密码的交。

一种密码只有五个数，可以用 std::vector 表示。将每种状态能产生的密码存进 std::set 中，手动遍历取交即可。

数据范围这么小，什么时间复杂度都可以冲过去吧。

T2 消消乐

考场上最沙波的一集。

考虑对元素入栈，栈顶两个相同就消去，这样合法的子串一定是一个能把栈消空的序列。

我们对前缀记录栈的状态，如果两个前缀状态 $i,j$ 相同，那么子串 $[i+1,j]$ 就是合法的，因为这个子串全部被消掉了。记录栈的状态哈希一下就可以了。

时间复杂度 $\mathcal{O}(n)$。

核心代码：

mp[{0, 0}] = 1;
for (int j = 0; j < 2; j++) {
    pw[j][0] = 1;
    for (int i = 1; i <= n; i++)
        pw[j][i] = pw[j][i - 1] * base % mod[j];
}
ll f = 0, g = 0, ans = 0;
top = 0;
for (int i = 1; i <= n; i++) {
    if (top && a[st[top]] == a[i]) {
        top--;
        f = (f - a[st[top + 1]] * pw[0][top] % mod[0] + mod[0]) % mod[0];
        g = (g - a[st[top + 1]] * pw[1][top] % mod[1] + mod[1]) % mod[1];
    } else {
        st[++top] = i;
        f = (f + a[st[top]] * pw[0][top - 1] % mod[0]) % mod[0];
        g = (g + a[st[top]] * pw[1][top - 1] % mod[1]) % mod[1];
    }
    ans += mp[{f, g}];
    mp[{f, g}]++;
}

T3 结构体

考场上以为很难写，实际上也很难写。

按照 lzy 传授的写模拟题的思路，先来梳理一下我们需要哪些东西。

1. 类型（包括基本类型和结构体）

   • 名字 name。
   • 对齐大小 align。
   • 大小 size。（基本类型的大小 = 对齐大小）
   • 成员数量 n_mem。
   • 成员 members[]。（基本类型没有成员）

2. 成员

   • 编号 idx。
   • 名字 name。
   • 偏移量 offset。（也就是从哪里开始对齐）
   • 大小 size。

为了方便处理，这里我们给每个成员都赋了一个编号。

我们要把所有定义过的类型都记录下来，同时还要记录全局的偏移量以及全局已经定义过具体变量的元素。我们可以把全局也理解为一个类型，它的成员就是所有定义过的元素。

这样我们就有了一个框架。现在来看看怎么处理操作。

• 新建类型。给类型赋一个编号，建立类型和编号的双射。

inline int AddType(string name) {
    tid++;
    type2tid[name] = tid;
    return tid;
}

• 初始化四个基本类型。执行四次 AddType 将类型都填进去即可。

inline void init() {
    pair<string, int> config[4] = {
        {"byte", 1}, {"short", 2}, {"int", 4}, {"long", 8}
    };
    for (int i = 0; i < 4; i++) {
        auto cfg = config[i];
        int idx = AddType(cfg.first);
        type_table[idx].size = cfg.second;
        type_table[idx].align = cfg.second;
    }
}

• 处理对齐。设当前地址为 $addr$，对齐大小为 $a$，其实就是找一个 $\geq addr$ 的最小的 $a$ 的倍数作为起始地址，本质是一个上取整的过程。

inline long long AlignAddr(long long addr, int align) {
    return (addr + align - 1) / align * align;
}

• 定义一个结构体。用一个 AddType 函数定义新类型，在结构体内定义成员时，要记录结构体内部的成员的大小并不断对齐，作为结构体的偏移量，同时要取成员对齐要求的最大值作为结构体的对齐要求。

if (op == 1) {
    string type_name;
    int n_mem;
    cin >> type_name >> n_mem;

    int idx = AddType(type_name); // 加入新类型，得到其编号

    Node &type = type_table[idx];
    type.n_mem = n_mem;
    long long in_type_offset = 0; // 处理结构体内部偏移

    for (int i = 1; i <= n_mem; i++) {
        string mem_type, mem_name;
        cin >> mem_type >> mem_name;

        Member &mem = type.members[i];
        mem.name = mem_name;

        int mem_tid = type2tid[mem_type]; // 通过类型得到编号，从而访问其属性
        type.align = max(type.align, type_table[mem_tid].align); // 结构体对齐要求

        // 成员对齐位置
        in_type_offset = AlignAddr(in_type_offset, type_table[mem_tid].align); 
        
        mem.offset = in_type_offset;
        mem.size = type_table[mem_tid].size;
        mem.idx = mem_tid;
        in_type_offset += mem.size;
    }
    in_type_offset = AlignAddr(in_type_offset, type.align); // 结构体大小
    type.size = in_type_offset;
    cout << type.size << " " << type.align << "\n";
}

• 定义一个具体元素。在全局类型中加入一个成员，更新全局偏移量。

if (op == 2) {
    string type, type_name;
    cin >> type >> type_name;

    var_table.n_mem++; // 全局成员数量 +1
    int idx = type2tid[type];

    Member &mem = var_table.members[var_table.n_mem]; // 更新全局成员
    mem.idx = idx;
    mem.name = type_name;
    mem.size = type_table[idx].size;

    int align = type_table[idx].align;
    var_offset = AlignAddr(var_offset, align); // 处理全局偏移量
    mem.offset = var_offset;
    cout << mem.offset << "\n";
    var_offset += mem.size;
}

• 根据元素访问地址。将访问的元素按照 . 切开，从全局类型开始，找到名字为每一段的成员，答案加上偏移量，递归查找即可。

if (op == 3) {
    string vis_name, mem_name;
    cin >> vis_name;
    vis_name += '.';

    ll addr = 0;
    mem_name.clear(); // 处理每一段成员的名字
    Node cur = var_table;

    for (int i = 0; i < vis_name.size(); i++) {
        if (vis_name[i] == '.') {
            for (int j = 1; j <= cur.n_mem; j++) {
                auto mem = cur.members[j];
                if (mem_name == mem.name) { // 找到成员
                    addr += mem.offset;
                    cur = type_table[mem.idx]; // 从其成员下去查找
                    break;
                }
            }
            mem_name.clear();
            continue;
        }
        mem_name += vis_name[i];
    }
   cout << addr << "\n";
}

• 根据地址查找成员。从全局类型开始，如果当前地址被某个成员包含，就递归下去查找。

if (op == 4) {
    ll addr;
    cin >> addr;

    string vis_name;
    Node cur = var_table;

    bool valid = true;

    while (true) {
        bool ok = false;
        for (int i = 1; i <= cur.n_mem; i++) {
            auto mem = cur.members[i];
            
            // 地址被成员包含
            if (mem.offset <= addr && addr < mem.offset + mem.size) {
                addr -= mem.offset;
                vis_name += mem.name;
                ok = true;
                cur = type_table[mem.idx];
                break;
            }
        }
        if (!ok) { // 地址没有元素占有
            valid = false;
            break;
        }
        if (cur.n_mem) vis_name += '.'; // 没递归到头，要加分隔符
        else break;
    }
    if (valid) cout << vis_name << "\n";
    else cout << "ERR" << "\n";
}

这样就差不多写完了·。

T4 种树

能想到二分答案是这道题的关键。

结束时间是具有单调性的，能够在 $t$ 时刻达成目标也必定能在 $t+1$ 时刻达到。

考虑二分答案 $x$，可以算出每个点想在第 $x$ 天达成目标最晚需要在什么时候种上树。越晚种上越不容易达成目标，发现这里的最晚时间也有单调性，可以再二分一次。

设每个点最晚种树的时间为 $f(u)$，由于父亲一定要比儿子种树早，从而有

$f(u)=\min_v f(v)-1$

现在就得到了每个点真正最晚种树的时间。而在第 $i$ 个时刻最多有 $i$ 棵树被种上，开一个桶，统计一个前缀和即可。

时间复杂度 $\mathcal{O}(n\log n\log V)$。

核心代码：

inline ll calc(int i, int x) {
    if (c[i] >= 0)
        return (ll)x * b[i] + (ll)x * (x + 1) / 2 * c[i];
    else {
        ll t = (b[i] - 1) / (-c[i]);
        if (x <= t) return (ll)x * b[i] + (ll)x * (x + 1) / 2 * c[i];
        return (ll)t * b[i] + (ll)t * (t + 1) / 2 * c[i] + x - t;
    }
}

void dfs(int u, int fa) {
    f[u] = late[u];
    for (int v: g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        f[u] = min(f[u], f[v] - 1);
    }
}
  
inline bool check(int x) {
    for (int i = 1; i <= n; i++) {
        ll S = calc(i, x);
        if (S < a[i]) return false;
        int l = 1, r = n, ans;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (S - calc(i, mid - 1) >= a[i]) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        late[i] = ans;
    }
    memset(cnt, 0, sizeof(cnt));
    dfs(1, 0);
    if (f[1] < 1) return false;
    for (int i = 1; i <= n; i++) {
        cnt[f[i]]++;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += cnt[i];
        if (sum > i) return false;
    }
    return true;
}