欸我去出题人怎么是go批，欸我去mygo还在追我

A. Tokitsukaze and Absolute Expectation

题意

对于一个长为 $n$ 的序列 $a$ ，第 $i$ 个元素 $a_i$ 的值将会从 $[l_i, r_i]$ 中独立等概率生成。定义：

$\displaystyle \text{val}(a) = \sum_{i=2}^n |a_{i - 1} - a_i|$

求 $\text{val}(a)$ 的期望。

思路

首先，因为每个元素值生成的事件是相互独立的，所以根据期望的可加性，将式子化简如下：

$E(\text{val}(a)) = E(\displaystyle \sum_{i=2}^n |a_{i - 1} - a_i|) = \displaystyle \sum_{i=2}^n E(|a_{i - 1} - a_i|)$

对于 $E(|a_{i - 1} - a_i|)$ ，记 $a_{i - 1} \in [l_1, r_1], a_i \in [l_2, r_2]$ ，并钦定 $l_1 < l_2$ 。那么分母是很显然的，为两个区间的长度之积，接下来我们考虑如何求分子。

可以发现，期望的计算涉及相交的区间和不相交的区间。记 $x = \max(l_1, l_2), y = \min(r_1, r_2), p = \max(r_1, r_2)$ ，那么我们可以将区间拆分为两两相交的 $[x, y], [x, y]$ ，以及两两不相交的 $[l_1, x - 1], [l_2, r_2]$ 和 $[x, y], [y + 1, p]$ 。

我们先来考虑简单的不相交。对于两个不相交的区间 $[l_1, r_1], [l_2, r_2]$ ，假设我们在第二个区间选择了左端点 $l_2$ ，那么由第一个区间所有选择构成的答案序列满足公差为 $1$ 的等差数列，首项为 $l_2 - r_1$ ，项数为第一个区间的长度。而当我们在第二个区间选择 $l_2 + 1$ 时，其距离第一个区间的所有点都增大了 $1$ ，所以对应地答案是原来的基础上增加一倍第一个区间的长度。以此类推，可以发现增大的倍数构成一个公差为 $1$ 的等差数列，首项为 $1$ ，项数为 $r_2 - l_2$ ，因而求得式子。

剩下的就是相交的情况，也就是 $[x, y]$ 。虽然注意力没那么好，但是打表发现貌似有规律。丢进 OEIS 发现确实有公式，即 $2 \cdot \binom{n + 1}{3}$ ，这里丢一个链接：A007290 - OEIS。

那么本题就做完了，不过注意一些边界的判断。

时间复杂度： $O(n)$

对应AC代码

constexpr int P = 1e9 + 7;
using Z = MInt<P>;

void solve() {
    int n;
    cin >> n;
    vector<int> l(n + 1), r(n + 1);
    for(int i=1;i<=n;i++) cin >> l[i] >> r[i];
    auto cal1 = [&](int l1, int r1, int l2, int r2) -> Z {
        return Z(l2 - r1 + l2 - l1) * (r1 - l1 + 1) * (r2 - l2 + 1) / 2 + Z(r1 - l1 + 1) * (r2 - l2 + 1) * (r2 - l2) / 2;
    };
    auto cal2 = [&](int l, int r) -> Z {
        int len = r - l + 1;
        return Z(len + 1) * len * (len - 1) / 3;
    };
    Z ans = 0;
    for(int i=2;i<=n;i++) {
        int l1 = l[i - 1], r1 = r[i - 1], l2 = l[i], r2 = r[i];
        if(l1 > l2) swap(l1, l2), swap(r1, r2);
        int x = max(l1, l2), y = min(r1, r2);
        Z now = 0;
        if(x > y) now += cal1(l1, r1, l2, r2);
        else {
            if(l1 != l2) now += cal1(l1, x - 1, l2, r2);
            if(r1 != r2) now += cal1(x, y, y + 1, max(r1, r2));
            now += cal2(x, y);
        }
        ans += now / (r1 - l1 + 1) / (r2 - l2 + 1);
    }
    cout << ans << '\n';
}

注意到我没有注意到，所以我没注意到

B. Tokitsukaze and Balance String (easy)

详见 $C$ ，区别是本题可以暴力

C. Tokitsukaze and Balance String (hard)

题意

定义当一个字符串满足连续子串中 $\mathtt{01}$ 和 $\mathtt{10}$ 的个数相等时，该字符串是平衡的。

定义一个字符串 $s$ 的 $\text{val}(s)$ 为满足将 $s_i$ 翻转后字符串变为平衡的下标 $i$ 的个数。

给定一个由 $\mathtt{'0', '1', '?'}$ 组成的字符串， $\mathtt{'?'}$ 可以被替换为 $\mathtt{'0', '1'}$ ，输出所有替换方案对应的 $\text{val}(s)$ 之和。

思路

首先，替换完成后我们会得到一个二进制串，只包含两种字符，所以除非 $\mathtt{01}$ 后面没有 $\mathtt{0}$ ，不然一定会出现一个与之对应的 $\mathtt{10}$ 。反过来也是一样的。

所以说，我们其实只需关注头尾两个字符的情况，而中间是无所谓的，因为可以被抵消。而若要让字符串平衡，我们只能让头尾两个字符相等。所以如果 $[2, n - 1]$ 中包含 $q$ 个 $\mathtt{?}$ ，那么这些位置都是无所谓的，我们在完成后续计算后乘上 $2^q$ 即可。

上述结论对于替换操作来说，替换 $[2, n - 1]$ 中的字符对平衡性毫无影响，反之能反转平衡性。所以对于一个平衡字符串， $\text{val}(s) = n - 2$ ，否则 $\text{val}(s) = 2$ 。

然后我们针对开头和结尾是否为 $\mathtt{?}$ 进行分讨即可。如果都不满足，那么我们根据平衡性即可得到答案；否则，我们就可以根据不同的选择得到不同的平衡性。

时间复杂度： $O(n)$

对应AC代码

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n == 1) {
        cout << (s[0] == '?' ? 2 : 1) << '\n';
        return;
    }
    int ans = 1;
    for(int i=1;i<n-1;i++) {
        if(s[i] == '?') ans = ans * 2 % mod;
    }
    if(s[0] != '?' && s[n - 1] != '?') {
        if(s[0] != s[n - 1]) ans *= 2;
        else ans *= n - 2;
    }else {
        if(s[0] == s[n - 1]) ans *= 2;
        ans *= n;
    }
    cout << ans % mod << '\n';
}

很思维

D. Tokitsukaze and Concatenate‌ Palindrome

题意

给定一个长为 $n$ 的字符串 $a$ 和一个长为 $m$ 的字符串 $b$ ，定义一次操作为选择任意字符串的任意位置，并将其替换为任意字符。输出使得两个字符串任意排列后拼接得到回文串的最小操作数。

思路

首先，钦定 $b$ 更长，便于后面的讨论。

因为需要操作数尽可能小，显然我们可以先把两者的相同字符排列在两端，然后考虑剩余的字符。

如果我们有 $x$ 个多余的字符，并想让其排列后构成回文串，那么我们只需修改其中的 $\lfloor \frac{x}{2} \rfloor$ 个字符即可，所以我们现在的目标是求得 $x$ 。

考虑拼接后的样子，剩下的大概是 $a$ 剩下的字符， $b$ 中的最多 $\lfloor \frac{m - n}{2} \rfloor$ 对字符（对称放在中间）， $b$ 剩下的字符。

所以我们只需处理中间的配对。不过可能会出现拼接后为奇数长度的情况，此时需要将 $x$ 减去 $1$ ，避免重复计算。

时间复杂度： $O(n + m)$

对应AC代码

void solve() {
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    if(n > m) swap(n, m), swap(a, b);
    int ans = 0;
    vector<int> cnt(26);
    for(auto &it : b) cnt[it - 'a'] ++;
    for(auto &it : a) {
        if(cnt[it - 'a']) cnt[it - 'a'] --;
        else ans ++;
    }
    int p = 0, q = 0; //(m - n) / 2 * 2
    for(auto &it : cnt) p += it, q += it / 2;
    if((n + m) % 2 == 1 && p > 0) p --;
    ans += p - min(q, (m - n) / 2) * 2;
    cout << ans / 2 << '\n';
}

细节太多了

E. Tokitsukaze and Dragon's Breath

题意

给定一个 $n \times m$ 的矩阵，定义一个格子 $(x, y)$ 的贡献为以这个格子为中心向 $(x−1,y−1), (x−1,y+1), (x+1,y−1), (x+1,y+1)$ 一直延伸得到的 "X" 形区域内格子的值的总和，求单个格子的最大贡献。

思路

我们可以将矩阵视为平面直角坐标系，以 $(1, 1)$ 为原点，并将格子全都视为坐标点，那么可以发现点全都位于 $x - y = a, x + y = b$ 直线上，且每个作为中心的格子延伸得到的区域恰好对应其中的两条直线。

所以我们将两类直线分开考虑，以 $a, b$ 作为偏移量，记录该偏移量所对应的直线上的点权总和。然后就只需枚举每个点作为中心，将两条直线的总和加起来，再减掉重叠区域，也就是中心即可。

时间复杂度： $O(n m \log (n + m))$

对应AC代码

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    map<int, int> p, q;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin >> a[i][j];
            p[i + j] += a[i][j], q[i - j] += a[i][j];
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            ans = max(ans, p[i + j] + q[i - j] - a[i][j]);
        }
    }
    cout << ans << '\n';
}

经典 map 题

F. Tokitsukaze and Kth Problem (easy)

题意

给定一个长为 $n$ 的序列 $a$ ，定义 $f(i, j) = (a_i + a_j) \bmod p$ 。给定一个整数 $k$ ，输出 $f(i, j)$ 的所有前 $k$ 大，不存在输出 $-1$ 。

思路

首先，因为数组位置对答案没有影响，所以我们可以先将数组取模，然后排序。其次，因为这是两个项相加，所以值域最多只会到 $2p - 2$ 。

针对前 $k$ 大，我们可以先二分出第 $k$ 大的大小 $V$ ，然后再根据 $V$ 找答案。 $\text{check}$ 函数可以用双指针实现，或者二分里面套二分。

因为值域可能会跑到 $[p, 2p - 2]$ 里去，所以我们可以记 $h_x$ 为满足 $a_i + a_j \geq x$ 的 $f(i, j)$ 数量，那么总数量就是 $h_V + h_{h + V} - h_p$ 。

除此之外还有一个坑，极端情况下数组可能由一种数字组成，这可能会导致求最后的数组的时候复杂度爆炸。所以我们可以求出大于 $V$ 的所有答案，然后用 $V$ 填充。

时间复杂度： $O(n \log p + k)$

对应AC代码

void solve() {
    int n, p, k;
    cin >> n >> p >> k;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        a[i] %= p;
    }
    sort(a.begin(), a.end());
    auto sum = [&](int x) -> int {
        int cnt = 0;
        for(int i=1,j=n;i<j;i++) {
            while(j > 0 && a[i] + a[j] >= x) j --;
            if(i >= j) break;
            cnt += j - i;
        }
        return n * (n - 1) / 2 - cnt;
    };
    auto check = [&](int x) -> bool {
        return sum(x) - sum(p) + sum(p + x) >= k;
    };
    int l = 0, r = p - 1, mid;
    while(l <= r) {
        mid = (l + r) >> 1ll;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    vector<int> ans;
    for(int i=1,j=n,t=n;i<=n;i++) {
        while(j > 0 && a[i] + a[j] >= l) j --;
        while(t > 0 && a[i] + a[t] >= l + p) t --;
        for(int x=max(i,j)+1;x<=n;x++) {
            if(a[i] + a[x] >= p) break;
            ans.emplace_back(a[i] + a[x]);
        }
        for(int x=max(i,t)+1;x<=n;x++) {
            ans.emplace_back(a[i] + a[x] - p);
        }
    }
    sort(ans.begin(), ans.end(), greater<>());
    for(auto &it : ans) cout << it << ' ';
    k -= ans.size();
    while(k --) cout << l - 1 << ' ';
    cout << '\n';
}

二分写麻了，参考了一下出题人题解

G. Tokitsukaze and Kth Problem (hard)

待补充

H. Tokitsukaze and Necklace

待补充

I. Tokitsukaze and Pajama Party

题意

给定一个字符串 $s$ ，对于模式串 $\mathtt{u*uwawauwa}$ ， $\mathtt{*}$ 代表匹配至少一个任意字符，输出 $s$ 中能匹配该模式串的子串数量。

思路

我们将模式串看成两部分，即 $\mathtt{u}$ 和 $\mathtt{uwawauwa}$ 。当我们枚举到位置 $p$ 时，如果 $p$ 开始的子串能匹配上模式串的右半部分，那么我们就只需知道 $[1,p-2]$ 中有多少 $\mathtt{u}$ 能作为模式串的左半部分，这些 $\mathtt{u}$ 可以和我们当前枚举到的右半部分组成模式串。

时间复杂度： $O(nm)$

对应AC代码

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string p = "uwawauwa";
    int m = p.size();
    int ans = 0, cnt = 0;
    for(int i=0;i+m-1<n;i++) {
        bool ok = true;
        for(int j=0;j<m;j++) {
            if(s[i + j] != p[j]) ok = false;
        }
        if(ok) {
            ans += cnt;
            if(i > 0 && s[i - 1] == 'u') ans --;
        }
        if(s[i] == 'u') cnt ++;
    }
    cout << ans << '\n';
}

兄弟

J. Tokitsukaze and Recall

题意

给定一个不一定连通的无向图，以及一个整数 $k$ 。提供 $k$ 次操作，一次操作为选择一个点并占领。可以从占领的任何位置通过边占领另一个位置。输出字典序最小的占领顺序。

思路

首先，我们可以用并查集找出所有连通块，并求出连通块中点的个数和编号最小的点。然后我们按照点的个数降序排序，个数相同时按照编号升序排序，得到若干个排序后的连通块，将前 $k$ 个连通块中编号最小的点放入优先队列。剩下的就是遍历优先队列，拿出队列里最小的元素，并将其占领，然后枚举其儿子，放入队列即可。

但是当 $k$ 很大时，这么做存在一个问题：我们可以用多余的 $k$ 先占领某些编号小的点，不然 $k$ 就浪费了。

不妨考虑贪心，只要 $k$ 还有剩余，我们一定会按照 $1, 2, 3, \ldots$ 顺序占领，所以我们只需在每次遍历队列前，判断队列的最小值是否过大，是则消耗 $k$ 然后放入当前能放入的最小值。

时间复杂度： $O(n \log n)$

对应AC代码

struct DSU {
    vector<int> pa, siz;
    void init(int n) { pa = vector<int>(n + 1), siz = vector<int>(n + 1, 1), iota(pa.begin(), pa.end(), 0); }
    int find(int x) { while(x != pa[x]) x = pa[x] = pa[pa[x]]; return x; }
    bool unite(int u, int v) {
        int f1 = find(u), f2 = find(v);
        if (f1 == f2) return false;
        siz[f1] += siz[f2];
        pa[f2] = f1;
        return true;
    }
    int size(int x){ return siz[find(x)]; }
}dsu;
 
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<set<int>> adj(n + 1);
    dsu.init(n);
    while (m --) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace(v), adj[v].emplace(u);
        dsu.unite(u, v);
    }
    vector<int> mn(n + 1, inf), cnt(n + 1);
    for(int i=1;i<=n;i++) {
        int pa = dsu.find(i);
        if(mn[pa] == inf) mn[pa] = i;
        cnt[pa] ++;
    }
    vector<pair<int, int>> g;
    for(int i=1;i<=n;i++) {
        if(cnt[i] > 0) g.emplace_back(-cnt[i], mn[i]);
    }
    sort(g.begin(), g.end());
    priority_queue<int, vector<int>, greater<>> q;
    for(int i=0;i<min((int)g.size(),k);i++) q.emplace(g[i].second);
    k -= min((int)g.size(), k);
    vector<int> st(n + 1), ans;
    int now = 1;
    while(!q.empty()) {
        if(now < q.top() && k > 0) {
            q.emplace(now);
            k --;
        }
        int x = q.top();
        q.pop();
        if(st[x]) continue;
        st[x] = true;
        ans.emplace_back(x);
        if(x == now) now ++;
        for(auto &y : adj[x]) {
            if(st[y]) continue;
            q.emplace(y);
        }
    }
    cout << ans.size() << '\n';
    for(auto &it : ans) cout << it << ' ';
    cout << '\n';
}

写起来麻烦了点，但不知道为啥过的人这么少

K. Tokitsukaze and Shawarma

题意

三个东西，分别需要 $x, y, z$ 个，做一个分别需要 $a, b, c$ 分钟，不同东西可以并行制作，计算至少需要多久做完。

思路

这能有什么思路。

时间复杂度： $O(1)$

对应AC代码

void solve() {
    int x, y, z, a, b, c;
    cin >> x >> y >> z >> a >> b >> c;
    cout << max({a * x, b * y, c * z}) << '\n';
}

没事至少不是Hello World

L. Tokitsukaze and XOR-Triangle

题意

给定两个长为 $n$ 的数组 $a, b$ ，对于 $q$ 次询问，每次询问给定一个区间 $[l, r]$ ，求：

$\displaystyle \sum_{i=l}^r\sum_{j=i}^r a_i \oplus b_j$

思路

首先，我们来考虑一下下面的式子怎么求：

$\displaystyle \sum_{i=l}^r\sum_{j=l}^r a_i \oplus b_j$

位运算一般来说拆位做会很方便，因为会出现一些奇妙的性质。假设 $a_i^k$ 为 $a_i$ 的第 $k$ 个二进制位，从 $0$ 开始计数， $b_i^k$ 同理，那么式子变成了下面这样：

$\displaystyle \sum_{k=0}^{30}\sum_{i=l}^r\sum_{j=l}^r a_i^k \oplus b_j^k$

假设我们有一个由 $0$ 和 $1$ 构成的长为 $n$ 的二进制序列 $A$ ，将其全都异或上 $1$ 相当于翻转二进制值， $0$ 则是不变。而一个二进制序列的总和等于 $1$ 的个数，我们记为 $p$ ，那么全都异或上 $1$ 后总和变为 $n - p$ ， $0$ 则是不变。

那么将上面的操作应用到这个式子上，我们相当于将 $a^k$ 中 $[l, r]$ 子序列视为 $A$ ，然后枚举 $b^k$ 中 $[l, r]$ 区间内的每个元素，分别求出 $A$ 全都异或上这个元素的值得到的总和，最后进行求和。

因为 $b^k$ 也是二进制序列，所以针对 $A$ 的操作只有两种， $0$ 和 $1$ 。所以我们只需分别求出 $[l, r]$ 内 $a^k$ 和 $b^k$ 中 $1$ 的个数，经过简单的计算即可得到结果，而前者用前缀和即可实现。

好的，现在我们回到原问题。直接求会很麻烦，但如果假设 $r = n$ ，我们就可以进行递推了。记：

$f_i = \displaystyle \sum_{i=l}^n\sum_{j=i}^n a_i \oplus b_j$

显然有：

$\displaystyle f_n = a_n \oplus b_n, f_i = f_{i + 1} + \sum_{k=i}^n a_i \oplus b_k$

上面的求和可以用后缀和与 $a_i$ 是否为 $1$ 来快速计算，具体方法在上面已经提到了。

而有趣的是，题目的式子可以用这个进行化简：

$\displaystyle \sum_{i=l}^r\sum_{j=l}^r a_i \oplus b_j = \displaystyle \sum_{i=l}^n\sum_{j=i}^n a_i \oplus b_j - \displaystyle \sum_{i=r+1}^n\sum_{j=i}^n a_i \oplus b_j - \displaystyle \sum_{i=l}^r\sum_{j=r+1}^n a_i \oplus b_j$

式子的左半部分即为 $f_l - f_{r + 1}$ ，类似于前缀和，而右边按照我们最开始考虑的式子的解法做即可。

时间复杂度： $O(nm)$

对应AC代码

constexpr int P = 1e9 + 7;
using Z = MInt<P>;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), b(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    vector<vector<Z>> pre_a(n + 1, vector<Z>(31)), pre_b(n + 1, vector<Z>(31));
    vector<vector<Z>> f(n + 2, vector<Z>(31));
    auto ret = [&](int t, int il, int ir, int jl, int jr) -> Z {
        Z cnt_a = pre_a[ir][t] - pre_a[il - 1][t], cnt_b = pre_b[jr][t] - pre_b[jl - 1][t];
        return cnt_a * (jr - jl + 1 - cnt_b) + (ir - il + 1 - cnt_a) * cnt_b;
    };
    for(int t=0;t<=30;t++) {
        for(int i=1;i<=n;i++) pre_a[i][t] = pre_a[i - 1][t] + (a[i] >> t & 1ll);
        for(int i=1;i<=n;i++) pre_b[i][t] = pre_b[i - 1][t] + (b[i] >> t & 1ll);
        for(int i=n;i>=1;i--) {
            f[i][t] = f[i + 1][t];
            if(a[i] >> t & 1ll) f[i][t] += n - i + 1 - (pre_b[n][t] - pre_b[i - 1][t]);
            else f[i][t] += pre_b[n][t] - pre_b[i - 1][t];
        }
    }
    while(q --) {
        int l, r;
        cin >> l >> r;
        Z ans = 0;
        for(int t=0;t<=30;t++) {
            Z now = f[l][t] - f[r + 1][t] - ret(t, l, r, r + 1, n);
            ans += (1ll << t) * now;
        }
        cout << ans << '\n';
    }
}

推式子题

2025牛客寒假算法基础集训营4 个人题解

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码

题意

思路

对应AC代码