Solved 10 of 12.

欸我去出题人怎么是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';
    }
}

推式子题