2026牛客暑期多校训练营3

A. Bitmask

位掩码
数学

cpp

#include <iostream>

using namespace std;

int cnt[30][4];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int t;
        cin >> t;
        for (int j = 29; ~j; --j) {
            cnt[j][t >> j & 3]++;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int op, v, res = 0;
        cin >> op >> v;
        for (int j = 29; ~j; --j) {
            int b[4] = {};
            auto t = v >> j & 3;
            for (int i = 0; i < 4; ++i) {
                if (op == 1) b[i & t] += cnt[j][i];
                else if (op == 2) b[i | t] += cnt[j][i];
                else b[i ^ t] += cnt[j][i];
            }
            for (int i = 0; i < 4; ++i) cnt[j][i] = b[i];
            res += cnt[j][1];
        }
        cout << res << '\n';
    }
    return 0;
}

B. Buy One More

数学
组合数学
快速幂
模逆元
随机化

我真是不理解为什么会过这么多人

有一个 Raney 引理，如果

a_{i} \leq 1, \sum_{i = 1}^{n} a_{i} = k > 0,

那么在 $n$ 个循环移位中，满足

所有前缀和 > 0

的循环移位恰好有 $k$ 个。

cpp

/*
获奖 a 次，喝了 m 瓶
n + a * c - m = 0
a = (n - m) / c
*/
#include <iostream>
#define int long long

using namespace std;

const int MOD = 998244353;
int p[2000010], inv[2000010];

int power(int n, int p) {
    int res = 1, base = n;
    while (p) {
        if (p & 1) res = res * base % MOD;
        base = base * base % MOD;
        p >>= 1;
    }
    return res;
}

void init() {
    int n = 2000000;
    p[0] = inv[0] = 1;
    for (int i = 1; i <= n; ++i) p[i] = p[i - 1] * i % MOD;
    inv[n] = power(p[n], MOD - 2);
    for (int i = n - 1; i; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

int comb(int n, int m) {
    // cout << n << ' ' << m << ' ' << p[n] * inv[m] % MOD * inv[n - m] % MOD << endl;
    return p[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int calc(int l, int d) {
    int t = (l + d) / 2;
    return comb(l, t);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int T;
    cin >> T;
    while (T--) {
        int n, m, c, a, b;
        cin >> n >> m >> c >> a >> b;
        if (n > m || (m - n) % c != 0) cout << 0 << '\n';
        else {
            int x = (m - n) / c;
            int p = a * power(b, MOD - 2) % MOD;
            int res = power(p, x) * power((1LL - p + MOD) % MOD, m - x) % MOD;
            res = res * (n * power(m, MOD - 2) % MOD * comb(m, x) % MOD) % MOD;
            cout << res << '\n';
        }
    }
    return 0;
}

F. Not Aqre 2

数学
动态规划
快速幂
位掩码

矩阵快速幂，很巧妙的用前两个字符的选择不重要（只要不一样就行）而且前面两个确定后下一个位置只有两种可以根据前面的选择唯一确定的选择来压缩。

cpp

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1 << 7;
const int MOD = 998244353;
int tmp[3][3] = {
    {0, 2, 1},
    {2, 0, 0},
    {1, 0, 0}
};
LL v1[N], v2[N];
LL a[N][N], b[N][N];
int n, m;

bool check(int i, int j, int x1, int x2, int y1, int y2) {
    if (x1 == y1 || x2 == y2) return false;
    for (int k = 0; k < n; ++k) {
        int cur1 = (i >> k & 1) ? tmp[x1][x2] : x1;
        int cur2 = (j >> k & 1) ? tmp[y1][y2] : y1;
        if (cur1 == cur2) return false;
        x1 = x2, x2 = cur1;
        y1 = y2, y2 = cur2;
    }
    return true;
}

void mul1() {
    memset(v2, 0, sizeof(v2));
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            v2[i] = (v2[i] + v1[j] * a[j][i]) % MOD;
        }
    }
    memcpy(v1, v2, sizeof(v1));
}

void mul2() {
    memset(b, 0, sizeof(b));
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            for (int k = 0; k < (1 << n); ++k) {
                b[i][j] = (b[i][j] + a[i][k] * a[k][j]) % MOD;
            }
        }
    }
    memcpy(a, b, sizeof(a));
}

LL power(LL n, LL p) {
    LL res = 1, base = n;
    while (p) {
        if (p & 1) res = res * base % MOD;
        base = base * base % MOD;
        p >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    if (n == 1) {
        cout << 3LL * power(2, m - 1) % MOD << '\n';
        return 0;
    }
    n -= 2;
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            for (int y1 = 0; y1 < 3; ++y1) {
                for (int y2 = 0; y2 < 3; ++y2) {
                    if (y1 == y2) continue;
                    a[i][j] += check(i, j, 0, 1, y1, y2);
                }
            }
        }
    }
    for (int i = 0; i < (1 << n); ++i) v1[i] = 6;
    m--;
    while (m) {
        if (m & 1) mul1();
        mul2();
        m >>= 1;
    }
    LL res = 0;
    for (int i = 0; i < (1 << n); ++i) {
        res = (res + v1[i]) % MOD;
    }
    cout << res % MOD << '\n';
    return 0;
}

G. Matrix Marking ^(补)

几何
凸包
实现
差分数组

我真服了，我一开始就想到坑里了，每个数字单独算凸包然后写了个超级大模拟骗过了 $97.3 %$ 的测试数据…… 最后发现不对，但是已经来不及了。对每个数字单独处理，离散化行枚举空隙，前面的 y 的 min 和后面的 y 的 max 画出来的矩形一定是这块空隙能画的最大的矩形。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

PLL operator -(PLL a, PLL b) {
    return {a.x - b.x, a.y - b.y};
}

LL operator *(PLL a, PLL b) {
    return a.x * b.y - a.y * b.x;
}

LL area(PLL a, PLL b, PLL c) {
    return (b - a) * (c - a);
}

const int N = 1000010;
int st[N], tp;
int q1[N], q2[N];
bool used[N];
vector<vector<int>> mark;
vector<PLL> v[N];

bool mk(PLL a, PLL b) {
    // cout << "trying" << endl;
    if (b.y > a.y && b.x > a.x) {
        // cout << a.x << ' ' << a.y << ' ' << b.x << ' ' << b.y << endl;
        mark[a.x][a.y]++, mark[b.x + 1][b.y + 1]++, mark[a.x][b.y + 1]--, mark[b.x + 1][a.y]--;
        return true;
    }
    else return false;
}

void work(vector<PLL> a) {
    if (a.size() < 2) return;
    sort(a.begin(), a.end());
    // if (a.size() == 2) {
    //     mk(a[0], a[1]);
    //     return;
    // }
    fill(used + 1, used + a.size() + 1, 0);
    tp = 0;
    for (int i = 0; i < a.size(); ++i) {
        while (tp >= 2 && area(a[st[tp - 1]], a[st[tp]], a[i]) < 0) used[st[tp--]] = false;
        st[++tp] = i;
        used[i] = true;
    }
    used[0] = false;
    for (int i = a.size() - 1; ~i; --i) {
        if (used[i]) continue;
        while (tp >= 2 && area(a[st[tp - 1]], a[st[tp]], a[i]) < 0) tp--;
        st[++tp] = i;
    }

    // for (int i = 1; i <= tp; ++i) cout << a[st[i]].x << ' ';
    
    int ru = 0, ld = 0;
    int l1 = 0, l2 = 0;
    for (int i = 1; i < tp; ++i) {
        if (a[st[i]] >= a[ru]) ru = st[i];
        if (a[st[i]] <= a[ld]) ld = st[i];
        auto d = a[st[i + 1]] - a[st[i]];
        if (d.x > 0 && d.y <= 0) {
            if (!l1) q1[++l1] = st[i];
            q1[++l1] = st[i + 1];
        }
        if (d.x < 0 && d.y >= 0) {
            if (!l2) q2[++l2] = st[i];
            q2[++l2] = st[i + 1];
        }
    }
    if (!l1) q1[++l1] = ld;
    if (!l2) q2[++l2] = ru;
    // cout << endl;
    // cout << l1 << ' ' << l2 << endl;
    // for (int i = 1; i <= l1; ++i) cout << a[q1[i]].x << ',' << a[q1[i]].y << ' ';
    // cout << endl;
    // for (int i = 1; i <= l2; ++i) cout << a[q2[i]].x << ',' << a[q2[i]].y << ' ';
    // cout << endl;
    int i = 1, j = l2;
    while (i <= l1 && j) {
        if (q1[i] == q2[j]) i++, j--;
        else if (mk(a[q1[i]], a[q2[j]])) {
            if (j > 1) mk(a[q1[i]], a[q2[j + 1]]), j--;
            i++;
        }
        else {
            if (a[q1[i]].x == a[q2[j]].x) j++;
            else if (a[q1[i]].x > a[q2[j]].x) i++;
            else j--;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    mark = vector<vector<int>>(n + 2, vector<int>(m + 2, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int c;
            cin >> c;
            v[c].emplace_back(i, j);
        }
    }
    // work(v[2]);
    for (int i = 1; i <= n * m; ++i) {
        // cout << "marking " << i << endl;
        work(v[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            mark[i][j] += mark[i - 1][j] + mark[i][j - 1] - mark[i - 1][j - 1];
            if (mark[i][j]) cout << 1;
            else cout << 0;
        }
        cout << '\n';
    }
    return 0; 
}

I. Swap master ^(补)

数学
贪心
前缀和

看了题解发现还挺简单，但是确实不好想。每个位置的贡献去绝对值之后这位的系数很小（只可能是 -2, -1, 0, 1, 2），枚举了这个，然后预处理了前缀 max。

cpp

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 500010;
LL a[N], f[5][5];
int n;

vector<pair<int, int>> get(int i) {
    if (i == 1) {
        return {{-1, a[i + 1]}, {1, -a[i + 1]}};
    }
    else if (i == n) {
        return {{-1, a[i - 1]}, {1, -a[i - 1]}};
    }
    else {
        return {{-2, a[i - 1] + a[i + 1]}, {0, -a[i - 1] + a[i + 1]}, {0, a[i - 1] - a[i + 1]}, {2, -a[i - 1] - a[i + 1]}};
    }
}

LL base(int i) {
    if (i == 1) return abs(a[i] - a[i + 1]);
    else if (i == n) return abs(a[i] - a[i - 1]);
    else return abs(a[i] - a[i - 1]) + abs(a[i] - a[i + 1]);
}

void calc_f(int j) {
    LL t = base(j);
    for (auto [kj, bj] : get(j)) {
        for (int ki = -2; ki <= 2; ++ki) {
            f[kj + 2][ki + 2] = max(f[kj + 2][ki + 2], ki * a[j] + bj - t);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        memset(f, -0x3f3f3f3f, sizeof(f));

        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        
        LL s = 0, d = 0;
        for (int i = 1; i < n; ++i) s += abs(a[i] - a[i + 1]);

        if (n == 2) {
            cout << s << '\n';
            continue;
        }

        // adjacent 
        d = max(d, abs(a[1] - a[3]) - abs(a[2] - a[3]));
        d = max(d, abs(a[n] - a[n - 2]) - abs(a[n - 1] - a[n - 2]));
        for (int i = 2; i < n - 2; ++i) {
            d = max(d, (abs(a[i + 1] - a[i - 1]) + abs(a[i] - a[i + 2])) - (abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i + 2])));
        }

        // f(swap(j, i)) = k_i a_j + b_j - base_j + k_j a_i + b_i - base_i
        for (int i = 3; i <= n; ++i) {
            calc_f(i - 2);
            LL t = base(i);
            for (auto [ki, bi] : get(i)) {
                for (int kj = -2; kj <= 2; ++kj) {
                    d = max(d, f[kj + 2][ki + 2] + kj * a[i] + bi - t);
                }
            }
        }

        cout << s + d << '\n';
    }
    return 0;
}

J. Tree.zip

树
树形 DP

几何
实现

签到

cpp

#include <iostream>
#define int long long

using namespace std;

const int N = 100010;
int x[N], y[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
        for (int i = 2; i < n; ++i) {
            int dx1 = x[i] - x[i - 1], dx2 = x[i + 1] - x[i];
            int dy1 = y[i] - y[i - 1], dy2 = y[i + 1] - y[i];
            int cross = dx1 * dy2 - dx2 * dy1;
            if (cross > 0) cout << "LEFT" << ' ';
            else if (cross == 0) cout << "STRAIGHT" << ' ';
            else cout << "RIGHT" << ' ';
        }
        cout << endl;
    }
    return 0;
}

L. Uphill Duel

博弈论
深度优先搜索
动态规划

博弈论签到，难得博弈论能让我一眼就会

cpp

#include <iostream>
#include <cstring>
#include <vector>
#include <set>

using namespace std;

const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> h(n + 2, vector<int>(m + 2)), v(n + 2, vector<int>(m + 2, 0)), f(n + 2, vector<int>(m + 2, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> h[i][j];
            }
        }
        auto dfs = [&](auto &&self, int x, int y) -> void {
            if (v[x][y]) return;
            v[x][y] = 1;
            set<int> s;
            for (int i = 0; i < 4; ++i) {
                int tx = x + dx[i], ty = y + dy[i];
                if (h[tx][ty] > h[x][y]) {
                    self(self, tx, ty);
                    s.insert(f[tx][ty]);
                }
            }
            while (s.count(f[x][y])) f[x][y]++;
        };
        int q;
        cin >> q;
        while (q--) {
            int x, y;
            cin >> x >> y;
            dfs(dfs, x, y);
            cout << (f[x][y] ? "First" : "Second") << '\n';
        }
    }
    return 0;
}

M. Wanderer

图论
图搜索

A. Bitmask ​

B. Buy One More ​

F. Not Aqre 2 ​

G. Matrix Marking (补) ​

I. Swap master (补) ​

J. Tree.zip ​

K. Turn-by-Turn Navigation ​

L. Uphill Duel ​

M. Wanderer ​