VP NAC 2024

The 2024 ICPC North America Championship
The 3rd Universal Cup. Stage 0: Trial Contest

Date 2025.08.21
Solved 9 / 13

A	B	C	D	E	F	G	H	I	J	K	L	M
O		Ø	O		Ø	O	O	Ø	O			Ø

C. Comparator

对于每个 expr，我们可以直接枚举两个输入的 4 种取值（x=0/1, y=0/1），并计算表达式的结果。

因此对于每条 IFFY 语句：

a b expr r

它的效果等价于不超过 4 条简单规则：

如果 word1 的第 $a$ 位等于 $u$ 且 word2 的第 $b$ 位等于 $v$，则立即返回 $r$

所有可能的 $(a, u, b, v)$ 组合数量为：

$$
k \times 2 \times k \times 2 = 4k^2
$$

一旦某个 $(a, u, b, v)$ 已经被更早的语句覆盖，在此之后出现的相同组合就可以被忽略，因为这些输入对 $(x, y)$ 已经返回过结果了。

因此，我们只需要处理不超过 $4k^2$ 条有效规则。
对于每条规则，我们可以在 $O(2^{2k})$ 的时间内，枚举所有满足 $\text{bit}_a(word1) = u \quad \text{且} \quad \text{bit}_b(word2) = v$ 的 (word1, word2) 对，并为它们赋返回值 $r$。

对于答案统计：

• 自反性违例数: 暴力枚举所有单词 $x$，统计：$f(x, x) = 1$ 的次数。
• 对称性违例数: 暴力枚举所有 $(x, y)$ 对，统计：$f(x, y) = 1 \quad \text{且} \quad f(y, x) = 1$ 的次数。
• 传递性违例数:
  • 枚举所有 $(x, y)$，如果 $f(x, y) = 1$，则对于所有满足 $f(y, z) = 1$ 的 $z$，检查是否存在：$f(x, z) \neq 1$的情况。
  • 这里使用 bitset 存储每一行的 $f$ 值集合，利用集合的按位运算可以在：$O\left(\frac{2^k}{w}\right)$ 时间内完成一次按行统计

时间复杂度：

• 解析与求值表达式：
  每条表达式只需计算 4 种 $(x, y)$ 输入，复杂度：$O\left(\sum |expr|\right)$
• 填充 $f$ 表：
  最多 $4k^2$ 条有效规则，每条规则 $O(2^{2k})$ → $O\left(k^2 \cdot 2^{2k}\right)$
• 检查性质：
  • 自反、对称：$O(2^{2k})$
  • 传递（bitset 优化）：$O\left(\frac{2^{3k}}{w}\right)$

总时间复杂度为：

$$
O\left( \sum |expr| + k^2 \cdot 2^{2k} + \frac{2^{3k}}{w} \right)
$$

const int K = 1024;

int priority(char c) {
    if (c == '(') return -1;
    if (c == '!') return 5;
    if (c == '=') return 4;
    if (c == '&') return 3;
    if (c == '|') return 2;
    if (c == '^') return 1;
    return 10;
}

void solve() {
    int n = read(), k = read();

    vector vis(k, vector(k, array<array<int, 2>, 2>{}));

    vector f(1 << k, bitset<K>{});
    vector vf(1 << k, bitset<K>{});

    for (int i = 0; i < n; i++) {
        int a = read(), b = read();
        string expr; cin >> expr;
        int r = read();
        a--, b--;

        vector<char> stk;
        string suf;
        for (auto c : expr) {
            if (c == 'x' or c == 'y' or c == '0' or c == '1') {
                stk.eb(c);
            } else if (c == '(') {
                stk.eb(c);
            } else if (c == ')') {
                while (stk.back() != '(') {
                    suf += stk.back();
                    stk.pop_back();
                }
                stk.pop_back();
            } else {
                while (!stk.empty() and priority(c) < priority(stk.back())) {
                    suf += stk.back();
                    stk.pop_back();
                }
                stk.eb(c);
            }
        }

        while (!stk.empty()) {
            suf += stk.back();
            stk.pop_back();
        }

        // cerr << suf << '\n';

        for (int x : {0, 1}) {
            for (int y : {0, 1}) {
                if (vis[a][b][x][y]) continue;

                vector<int> v;
                for (auto c : suf) {
                    if (c == '0') {
                        v.push_back(0);
                    } else if (c == '1') {
                        v.push_back(1);
                    } else if (c == 'x') {
                        v.push_back(x);
                    } else if (c == 'y') {
                        v.push_back(y);
                    } else if (c == '!') {
                        v.back() ^= 1;
                    } else {
                        int a = v.back();
                        v.pop_back();
                        int b = v.back();
                        v.pop_back();
                        if (c == '=') {
                            v.push_back(a == b);
                        } else if (c == '&') {
                            v.push_back(a & b);
                        } else if (c == '|') {
                            v.push_back(a | b);
                        } else if (c == '^') {
                            v.push_back(a ^ b);
                        }

                    }
                }

                // assert(v.size() == 1);
                if (v[0]) {
                    vis[a][b][x][y] = 1;
                    for (int i = 0; i < (1 << k); i++) {
                        if (((i >> a) & 1) == x) {
                            for (int j = 0; j < (1 << k); j++) {
                                if (((j >> b) & 1) == y and !vf[i][j]) {
                                    f[i][j] = r;
                                    vf[i][j] = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }


    int r = read();
    for (int i = 0; i < (1 << k); i++) {
        for (int j = 0; j < (1 << k); j++) {
            if (!vf[i][j]) {
                vf[i][j] = 1;
                f[i][j] = r;
            }
        }
    }

    int ans1 = 0, ans2 = 0, ans3 = 0;

    for (int x = 0; x < (1 << k); x++) {
        if (f[x][x]) ans1++;

        for (int y = 0; y < (1 << k); y++) {
            if (f[x][y] and f[y][x]) {
                ans2++;
            }
            if (f[x][y]) {
                ans3 += (f[y] & ~f[x]).count();
            }
        }
    }

    cout << ans1 << ' ' << ans2 << ' ' << ans3 << '\n';
}

M. Training, Round 2

设 $f(j)$ 表示加实现 $j$ 次时，思维能力的可行取值集合。
初始 $f(0) = {t_0}$，其余为空。按题目顺序依次处理，每道题对应实现区间与思维区间的一个矩形限制。

对于每个 $j$，将 $f(j)$ 与该矩形相交，得到可行子集 $S$。对 $S$ 中的每个元素，有两种扩展：

1. 将其加入 $f(j+1)$（对应加实现）；
2. 将其加一后仍留在 $f(j)$（对应加思维）。

由于可行集合在一维上保持连续性，$f(j)$ 可用一个区间表示，并在转移时取交或并。

最终答案为所有 $j$ 中 $\max(j + \text{max}(f(j)) - t_0)$，时间复杂度 $O(n^2)$。

void solve() {
    int n = read();
    int i0 = read();
    int t0 = read();

    vector<int> l(n + 1), r(n + 1, -1);
    l[0] = r[0] = t0;
    for (int i = 0; i < n; i++) {
        int il = read(), ir = read();
        int tl = read(), tr = read();

        for (int j = i; j >= 0; j--) {
            if (i0 + j < il or i0 + j > ir) continue;

            int L = max(l[j], tl);
            int R = min(r[j], tr);
            if (L > R) continue;

            r[j] = max(r[j], R + 1);
            if (r[j + 1] < l[j + 1]) {
                l[j + 1] = L;
                r[j + 1] = R;
            } else {
                l[j + 1] = min(l[j + 1], L);
                r[j + 1] = max(r[j + 1], R);
            }
        }
    }

    int ans = 0;
    for (int j = 0; j <= n; j++) {
        if (l[j] <= r[j]) {
            ans = max(ans, j + r[j] - t0);
        }
    }

    cout << ans << '\n';
}

I. Not Another Constructive!

设 $f(i, N, C)$ 表示处理前 $i$ 个字符时，已有 $N$ 个 N，未来还有 $C$ 个 C，可行的 "NAC" 子序列数量集合。
初始 $f(0, 0, C) = {0}$ 对所有 $C$ 成立，其余为空。

依次处理每个位置，根据字符种类进行转移：

1. 若为 'N'，则转移到 $(N+1, C)$；
2. 若为 'A'，则 NAC 数整体增加 $N \times C$（集合整体左移该值）；
3. 若为 'C'，则转移到 $(N, C-1)$；
4. 其它字符保持状态不变。

由于 NAC 数集合可压为长度 $K+1$ 的布尔数组，能用 bitset 加速。

末尾检查 $f(n, N, 0)$ 中是否包含目标 $k$；若存在则自右向左回溯，根据可行性依次确定每个 ‘?’ 的取值，构造出一个满足条件的串。

总状态数 $O(n^3)$，每个状态更新复杂度 $O(K / w)$（$w$ 为字长），在 $n \le 40, K \le 2500$ 时可行。

const int K = 2500;

void solve() {
    int n = read();
    int k = read();

    string s; cin >> s;

    vector dp(n + 1, vector(n + 1, vector(n + 1, bitset<K + 1>{})));

    for (int i = 0; i <= n; i++) {
        dp[0][0][i][0] = 1;
    }

    for (int i = 0; i < n; i++) {
        if (s[i] == '?' or s[i] == 'N') {
            for (int N = 0; N <= i; N++) {
                for (int C = 0; C <= n - i; C++) {
                    dp[i + 1][N + 1][C] |= dp[i][N][C];
                }
            }
        }
        if (s[i] == '?' or s[i] == 'A') {
            for (int N = 0; N <= i; N++) {
                for (int C = 0; C <= n - i; C++) {
                    dp[i + 1][N][C] |= dp[i][N][C] << (N * C);
                }
            }
        }
        if (s[i] == '?' or s[i] == 'C') {
            for (int N = 0; N <= i; N++) {
                for (int C = 1; C <= n - i; C++) {
                    dp[i + 1][N][C - 1] |= dp[i][N][C];
                }
            }
        }
        if (s[i] == '?' or (s[i] != 'N' and s[i] != 'A' and s[i] != 'C')) {
            for (int N = 0; N <= i; N++) {
                for (int C = 0; C <= n - i; C++) {
                    dp[i + 1][N][C] |= dp[i][N][C];
                }
            }
        }
    }


    int N = -1;
    for (int i = 0; i <= n; i++) {
        if (dp[n][i][0][k]) {
            N = i;
        }
    }

    if (N == -1) { cout << "-1\n"; return; }

    int C = 0;
    for (int i = n - 1; i >= 0; i--) {
        if ((s[i] == '?' or s[i] == 'N') and N > 0 and dp[i][N - 1][C][k]) {
            s[i] = 'N';
            N--;
        } else if ((s[i] == '?' or s[i] == 'A') and k >= N * C and dp[i][N][C][k - N * C]) {
            s[i] = 'A';
            k -= N * C; 
        } else if ((s[i] == '?' or s[i] == 'C') and dp[i][N][C + 1][k]) {
            s[i] = 'C';
            C++;
        } else if (s[i] == '?') {
            s[i] = 'Z';
        }
    }

    cout << s << '\n';
}

F. Magic Bean

work 函数：执行一次旋转

1. 把当前操作记录到 ans（如 "o3"）。

2. 如果是 外围圈 (x < 3)：

   • 用 std::rotate 实现顺时针旋转 k 格。
   • 注意 rotate 的参数是 “把最后 k 个元素移到最前面” 来模拟顺时针转。

3. 如果是 中间圈 (x == 3)：

   • 中心圈旋转的效果是“3 条轨道之间，交换某些位置的珠子”。
   • 这段代码把每个“对应列”的珠子取出来（每个列有来自三个圈的珠子），
     然后顺时针旋转 k 格，再放回去。

主还原循环:

• 顺着每一圈去找第一个不对颜色的珠子
• 把它通过一些旋转（外围圈 + 中心圈）放回自己应该的圈
• 同时不会破坏已经好的部分

具体步骤：

1. 遍历三条圈（i=0..2），再遍历每圈的每个位置（j=0..9）

2. 如果这个位置的颜色正确（s[i][j] == t[i]），跳过

3. 否则，执行一系列操作：

   • 如果不在圈的 0 号位置，就先旋转该圈，把错珠子移到位置 0。
   • i1 = t.find(s[i][0]) 找出这个错珠子应该属于哪一圈（看它的颜色）。
   • 在 i1 这个圈中，找第一个还没对齐的位置 j1。
   • 如果 j1 != 3（目标插入位置不是 3 号位置），就把 i1 圈转一下，把它空出来。
   • 用中心圈旋转，把珠子换到正确的圈上去。
   • 再调整外围圈、中心圈的顺序，保证整体正确性。

void solve() {
    string s[3];
    for (int i = 0; i < 3; i++) cin >> s[i];

    const string t = "ogrc";
    vector<string> ans;


    auto work = [&](int x, int k) {
        ans.eb(t.substr(x, 1) + char(k + '0'));
        if (x < 3) {
            rotate(s[x].begin(), s[x].end() - k, s[x].end());
        } else {
            for (int i = 0; i < 3; i++) {
                string u;
                for (int j = 0; j < 3; j++) {
                    u += s[j][i];
                }
                rotate(u.begin(), u.begin() + k, u.end());
                for (int j = 0; j < 3; j++) {
                    s[j][i] = u[j];
                }
            }
        }
    };

    while (1) {
        bool flag = 1;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 10; j++) {
                if (s[i][j] == t[i]) continue;

                flag = 0;
                if (j != 0) work(i, 10 - j);
                int i1 = t.find(s[i][0]);
                int j1 = 0;
                while (s[i1][j1] == t[i1]) j1++;

                if (j1 != 3) work(i1, (3 - j1 + 10) % 10);
                work(3, (i - i1 + 3) % 3);
                work(i1, 9);
                work(3, (i1 - i + 3) % 3);
            }
        }

        if (flag) break;
    }

    cout << ans.size() << '\n';
    for (auto s : ans) cout << s << '\n';
}

G. Manhattan Walk

在格子 $(i,j)$，右边的期望时间记为 $a$，下边的期望时间记为 $b$，假设 $a \le b$。
初始箭头随机指向“右”或“下”，概率各 $0.5$。每个箭头都有一个定时器，在 $[0,p]$ 内均匀分布初始值，归零后翻转方向。

• 如果 $a + p \le b$，说明即使等待满 $p$ 秒翻成右边再走，还是比走下边更优。

  • 初始向右：等待 $0$，耗时 $a$。
  • 初始向下：等待期望 $p/2$ 秒翻向右，再走右边 $a$。
  • 所以综合：$E(i,j) = \frac12 \cdot a + \frac12 \cdot (\frac p 2 + a) = a + \frac p 4$。

• 如果 $a + p > b$，这里“等翻向右”不一定比直接走下边好，要视定时器剩余时间 $x \in [0,p]$ 而定。

  • 初始向右（概率 0.5）：直接走右，耗时 $a$。
  • 初始向下（概率 0.5）：定时器剩余时间 $x \sim U[0,p]$：
    • 区间 1：$x < b-a$，概率 $(b-a)/p$，耗时期望是 $a + \mathbb{E}[x]$，其中 $\mathbb{E}[x] = \frac{b-a}{2}$，因此这段的期望耗时 = $a + \frac{b-a}{2} = \frac{a+b}{2}$。
    • 区间 2：$x \ge b-a$，概率 $(p - (b-a)) / p = (p - b + a)/p$，此时直接下走，耗时 $b$。
  • 所以综合：$E(i,j) = 0.5 \cdot a + 0.5 \cdot \frac{p - b + a}{p} \cdot b + 0.5 \cdot \frac{b-a}{p} \cdot \frac{a+b}{2}$

void solve() {
    int r = read(), c = read(), p = read();

    vector dp(r + 1, vector<double>(c + 1));

    for (int i = r; i >= 1; i--) {
        for (int j = c; j >= 1; j--) {
            if (i == r and j == c) {
                dp[i][j] = 0;
            } else if (i == r) {
                dp[i][j] = 0.25 * p + dp[i][j + 1];
            } else if (j == c) {
                dp[i][j] = 0.25 * p + dp[i + 1][j];
            } else {
                auto a = dp[i][j + 1], b = dp[i + 1][j];
                if (a > b) swap(a, b);

                if (a + p <= b) {
                    dp[i][j] = 0.25 * p + a;
                } else {
                    dp[i][j] = (p - b + a) * 0.5 / p * b
                                + 0.5 * a
                                + (b - a) * 0.5 / p * (a + b) * 0.5;
                }
            }
        }
    }

    printf("%.10lf\n", dp[1][1]);
}