2024牛客多校第10场

10

B std::pair (B)

模拟题，没什么难度，就是有点恶心。题解提到的二叉树做法赛时也想过，但写着不太顺手就放弃了，转而写了个类似括号匹配的解法。

    for(int i = 1; i <= n; i++) {
        string s;
        cin >> c[i] >> s;
        mp[s] = i;
    }
    while(q--) {
        string s0, s;
        cin >> s0;
        bool flag = 1;
        for(int i = 0; i < s0.size(); i++) {
            if(s0[i] == '.') {
                s = s0.substr(0, i);
                flag = 0;
                break;
            }
        }
        if(flag) {
            s0 += ";"; // 字符串后面还有分号。。。
            cout << c[mp[s0]] << endl;
            continue;
        }
        s += ";";
        int x = mp[s], j = 0;
        for(int i = 0; i < s0.size(); i++) {
            if(s0[i] == '.') { // 相当于需要查找的层数
                if(s0[i + 1] == 'f') {
                    j += 5; // pair向里跳一层到first
                }
                else {
                    j += 5;
                    int stk = 0; // 括号匹配
                    for(; j < c[x].size(); j++) {
                        if(c[x][j] == '<') stk++;
                        else if(c[x][j] == '>') stk--;
                        if(stk == 0 && c[x][j] == ',') break;
                    }
                    j++;
                }
            }
        }
        int stk = 0;
        for(; j < c[x].size(); j++) {
            if(c[x][j] == '<') stk++;
            else if(c[x][j] == '>') stk--;
            cout << c[x][j];
            if(c[x][j] == 't' || c[x][j] == 'e' || c[x][j] == '>') {
                if(stk == 0) break;
            }
        }
        cout << endl;
    }

K Doremy's IQ 2 (K)

假设所有题目的难度满足 \(a\leq 0\). 若最终智商降为 \(m\)，最优情况下所有 \(a_i > m\)（或许还有一部分 \(a_i = m\)）都应作为 \(d=x\)-type，其余题目则用于拉低智商，不计入答案中；\(a\geq 0\) 时与之相似。如此可以 \(O(1)\) 检验任意一个 \(m\) 取值的合法性，考虑二分答案求解。对于 \(a\) 有正有负的情况，为使答案更优，Doremy智商的单调性最多发生一次变化。可从 \(1\) 至 \(n\) 枚举智商第一次递增/递减到的位置，然后二分求其反方向可能存在的最优解。复杂度 \(n\log n\).

    int x = 0, y = 0, z = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(a[i] < 0) x++;
        else if(a[i] == 0) y++;
        else z++;
    }
    int ans = 0;
    for(int i = 1; i <= x; i++) {
        if(i - 1 < -a[i]) continue;
        int res = 0, l = x + y + 1, r = n;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[mid] - a[i] <= n - mid) {
                res = mid - x - y;
                l = mid + 1;
            } else r = mid - 1;
        }
        ans = max(ans, res + x - i + 1);
    }
    for(int i = x + y + 1; i <= n; i++) {
        if(n - i < a[i]) continue;
        int res = 0, l = 1, r = x;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[i] - a[mid] <= mid - 1) {
                res = x - mid + 1;
                r = mid - 1;
            } else l = mid + 1;
        }
        ans = max(ans, res + i - x - y);
    }
    printf("%d\n", ans + y);

L Tada! (L)

由于 \(n\leq 5\)，每次操作可以到达的状态最多只有 \(({5\choose2} + 5)\times 2 = 30\) 种，将每条信息的 \(s\) 作为起始位置，bfs计算其到达各个状态的最小操作次数，\(t\) 次能够到达的所有合法状态取交集即为答案。开始我们认为bfs求出的“最短路”满足 \(d_i\leq t\) 时，即可通过扩大/缩小操作区间凑成 \(t\) 次操作，后来发现遗漏了两个特判：\(n = 1\) 时操作区间无法改变，应严格满足 \(d_i = t\)；起点位置需要至少 \(2\) 次操作才能恢复原来状态，因此 \(t = 1\) 时起点位置不合法。特判后即可通过，时间复杂度 \(30mn\cdot 10^n\).

（代码不是我写的，也不太想再写一遍，多少有点恶心）