2008(970div3)

A. Sakurako's Exam

今天，樱子要参加数学考试。老师给出了由 $a$ 个一和 $b$ 个二组成的数组。

在数组中，樱子必须在每个元素前面加上 "+"或"-"，这样数组中所有元素的和就等于 $0$ 。

樱子不确定是否有可能解决这个问题，那么请判断是否有办法分配符号，使数组中所有元素的和等于 $0$ 。

void solve() {
    int a, b;cin >> a >> b;
    if (a & 1) {
        cout << "NO\n";return;
    }
    if (b & 1) {
        if (a) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    } else {
        cout << "YES\n";
    }
}

B. Square or Not

漂亮的二进制矩阵是指边缘为 1、内部为 0 的矩阵。

您需要检查得到字符串 $s$ 的美丽矩阵是否可以平方。换句话说，你需要检查字符串 $s$ 是否可以从一个平方的美丽二进制矩阵（即 $r = c$ ）中得到。

void solve() {
    int n;cin >> n;
    string s;cin >> s;s = ' ' + s;
    int m = n;
    int idx = 0;
    for (int i = 2;i <= n;i++) {
        if (i * i == n) {
            idx = i;break;
        }
    }
    if (!idx) {
        cout << "No\n";return;
    }
    int ok = 1;
    for (int i = 1;i <= idx;i++) {
        for (int j = 1;j <= idx;j++) {
            int p = (i - 1) * idx + j;
            if (i == 1 || j == 1 || i == idx || j == idx) {
                if (s[p] != '1')ok = 0;
            } else {
                if (s[p] == '1')ok = 0;
            }
        }
    }
    if (ok) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

C. Longest Good Array

今天，樱子在学习数组。长度为 $n$ 的数组 $a$ 如果并且只有在以下情况下才被认为是好数组：

数组 $a$ 是递增的，即所有 $2 \leq i \leq n$ 都是 $a_{i - 1} < a_{i}$ ；
相邻元素之间的差值是递增的，即所有 $2 \leq i < n$ 的差值为 $a_{i} - a_{i - 1} < a_{i + 1} - a_{i}$ 。

樱子想到了边界 $l$ 和 $r$ ，并希望构造一个最大长度的好数组，其中 $l \leq a_{i} \leq r$ 代表所有 $a_{i}$ 。

请帮助樱子找出给定的 $l$ 和 $r$ 的最大长度。

void solve() {
    int l, r;cin >> l >> r;
    int cnt = 0, x = 0;
    for (int i = l;i <= r;i += x) {
        x++;cnt++;
    }
    cout << cnt << '\n';
}

D. Sakurako's Hobby

对于某个排列 $p$ $^{∗}$ 如果可以通过赋值 $i = p_{i}$ 一定次数使 $i$ 等于 $j$ ，则樱子称整数 $j$ 可以从整数 $i$ 到达。

如果是 $p = [3, 5, 6, 1, 2, 4]$ ，那么，举例来说， $4$ 可以从 $1$ 到达，因为： $i = 1$ $\to$ $i = p_{1} = 3$ $\to$ $i = p_{3} = 6$ $\to$ $i = p_{6} = 4$ .现在是 $i = 4$ ，所以 $4$ 可以从 $1$ 到达。

排列中的每个数字都被染成黑色或白色。

樱子将函数 $F (i)$ 定义为从 $i$ 可以到达的黑色整数的个数。

樱子对每个 $1 \leq i \leq n$ 的 $F (i)$ 都很感兴趣，但计算所有值变得非常困难，所以她请你作为她的好朋友来计算这个值。

void solve() {
    int n;cin >> n;
    vector<int> p(n + 1), q(n + 1);
    for (int i = 1;i <= n;i++)cin >> p[i], q[p[i]] = i;
    string s;cin >> s;s = ' ' + s;
    vector<int> ans(n + 1), vis(n + 1);
    int m = 0;
    auto dfs = [&](auto self, int x, int y)->void {
        if (vis[x])return;
        m++;
        vis[x] = 1;
        if (s[x] == '1')m--;
        self(self, y, p[y]);
        ans[x] = m;
        };
    for (int i = 1;i <= n;i++) {
        m = 0;
        if (!vis[i] && s[i] == '0') {
            dfs(dfs, i, p[i]);
        }
    }
    for (int i = 1;i <= n;i++) {
        cout << ans[i] << " \n"[i == n];
    }
}

F. Sakurako's Box

樱子有一个装有 $n$ 个球的盒子。每个球都有自己的价值。她想和她的朋友打赌，如果她的朋友从盒子里随机挑选两个球（可能是两个不同的球，但它们的价值可能相同），它们的价值的乘积将与樱子猜测的数字相同。

计算其期望值

#define int long long
constexpr int mod = 1e9 + 7;
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    int ans = 0;

    for (int i = 1;i < n;i++) {
        int p = (pre[n] - pre[i]) % mod * a[i] % mod;
        int q = n * (n - 1) / 2;q %= mod;
        ans += p * inv(q) % mod;ans %= mod;
    }
    cout << ans << '\n';
}

E. Alternating String

樱子非常喜欢交替字符串。如果满足

偶数位置上的字符相同
奇数位置上的字符相同
字符串的长度是偶数

她就会把由拉丁小写字母组成的字符串 $s$ 称为交替字符串。

作为好朋友，您决定赠送这样的字符串，但您找不到。幸运的是，您可以对字符串进行两种操作：

选择索引 $i$ 并删除字符串中的 $i$ -th 字符，这样字符串的长度就会减少 $1$ 。此类操作的**次数不超过 $1$ 次；
选择索引 $i$ 并将 $s_{i}$ 替换为任何其他字母。

由于时间紧迫，您需要确定使字符串成为交替字符串所需的最少操作次数。

Solution

看了题解，感觉和我之前的想法是一样的，不知道哪里出了问题。

这里是从最后一个位置开始，开始慢慢往前推，(刚开始是将最后一位删除掉，然后后面开始交替操作，将最后一位加回来，将当前位删掉)，通过这种方式可以完成所有可能。(Effective Code!)

#define all(a) a.begin(), a.end()
void solve() {
    int n;cin >> n;
    string s;cin >> s;
    vector<vector<int>> cnt(2, vector <int>(26));
    for (int i = 0; i < n; ++i) {
        cnt[i & 1][s[i] - 'a']++;
    }
    if (n & 1 ^ 1) {
        cout << n - *max_element(all(cnt[0])) - *max_element(all(cnt[1])) << '\n';
        return;
    }
    cnt[n - 1 & 1][s[n - 1] - 'a']--;
    int ans = *max_element(all(cnt[0])) + *max_element(all(cnt[1]));
    for (int i = n - 2; i >= 0; i--) {
        cnt[i & 1][s[i] - 'a']--;
        cnt[i & 1][s[i + 1] - 'a']++;
        ans = max(ans, *max_element(all(cnt[0])) + *max_element(all(cnt[1])));
    }
    cout << n - ans << '\n';
}

G. Sakurako's Task

樱子为你准备了一项任务：

她给了你一个由 $n$ 整数组成的数组，让你选择 $i$ 和 $j$ 这样的 $i \neq j$ 和 $a_{i} \geq a_{j}$ ，然后指定 $a_{i} = a_{i} - a_{j}$ 或 $a_{i} = a_{i} + a_{j}$ 。只要满足条件，您可以对任意 $i$ 和 $j$ 执行任意次数的操作。

樱子问你，数组的 $m e x_{k}$ $^{∗}$ 在任意多次操作后的最大可能值是多少？

$^{∗}$ $m e x_{k}$ 是数组中不存在的 $k$ 个非负整数。例如： $m e x_{1} ({1, 2, 3}) = 0$ ，因为 $0$ 是数组中不存在的第一个元素； $m e x_{2} ({0, 2, 4}) = 3$ ，因为 $3$ 是数组中不存在的第二个元素。

Solution

需要证明：根据操作，可以得到最终的的数组是 $a_{i} = (i - 1) \times gcd ({a_{i}})$
得到了这个数组，如何以一种较快的方式求出 ${mex}_{k}$

最终能凑出来的是 $0, g, 2 g, 3 g \dots, (n - 1) g$

在每个间隔有 $g - 1$ 个数没有凑出，一共有 $(n - 1)$ 个 $(g - 1)$ 凑不出来。

如果大于了这个数，说明已经超出了 $(n - 1) g$ ，在范围外面还有 $k - (n - 1) (g - 1)$ 个数，
即 $(n - 1) g + k - (n - 1) (g - 1) = n - 1 + k$ ，否则同理

按照这种方式来求 ${mex}_{k}$

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int g = a[1];
    for (int i = 1;i <= n;i++)g = __gcd(g, a[i]);
    if (n == 1) {
        cout << (a[1] >= k ? k - 1 : k) << '\n';return;
    }
    int t = (g - 1) * (n - 1);
    if (k > t) {
        cout << n - 1 + k << '\n';
    } else {
        if (k % (g - 1) == 0) {
            cout << k / (g - 1) * g - 1 << '\n';
        } else {
            cout << k / (g - 1) * g + k % (g - 1) << '\n';
        }
    }
}

H. Sakurako's Test

樱子即将参加一项测试。测试可以描述为一个整数数组 $n$ 和一个任务：

给定一个整数 $x$ ，樱子可以执行以下操作任意多次：

选择一个整数 $i$ ( $1 \leq i \leq n$ )，使得 $a_{i} \geq x$ ；
将 $a_{i}$ 的值改为 $a_{i} - x$ 。

任意多次使用此操作，她必须找出数组 $a$ 的最小中值 $^{∗}$ 。

樱子知道数组，但不知道整数 $x$ 。有人说漏了嘴， $x$ 的 $q$ 值中有一个会出现在下一次测试中，所以樱子问你每个这样的 $x$ 的答案是什么。

$^{∗}$ 长度为 $n$ 的数组的中位数是位于排序数组中间的元素（对于偶数 $n$ ，位于 $\frac{n + 2}{2}$ -th 位置；对于奇数，位于 $\frac{n + 1}{2}$ -th 位置）。

Solution

调和级数复杂度<->mod Q

根据贪心的思想， $a_{i} \to a_{i} mod x$

提前预处理出 $x \in [1, n]$ 的所有情况，对于每一种情况，答案范围是 $[0, x - 1]$ 。

可以二分答案(对于 $x$ ，数组 $a$ 的最小中位数)，对于每一个 $m i d$ ，可以计算出余数为 $[0, m i d]$ 区间内的数的个数，只需要判断个数是否占 $⌊ \frac{n}{2} ⌋ + 1$ 个即可。

时间复杂度: $O (n \log^{2} n)$

void solve() {
    int n, q;cin >> n >> q;
    vector<int> mp(n + 1);
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;mp[x]++;
    }

    for (int i = 1;i <= n;i++)mp[i] += mp[i - 1];
    vector<int> ans(n + 1);

    for (int i = 1;i <= n;i++) {//x
        int l = 0, r = i - 1;
        while (l < r) {
            int mid = l + r >> 1;
            int s = 0;
            for (int j = 0;j <= n;j += i) {
                s += mp[min(n, j + mid)] - (j == 0 ? 0 : mp[j - 1]);
            }
            if (s >= n / 2 + 1) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        ans[i] = l;
    }
    while (q--) {
        int x;cin >> x;
        cout << ans[x] << ' ';
    }
    cout << '\n';
}