2000

Berserk And Fireball

出处：CF1380D

题目大意：一排有 $n$ 个士兵，每个士兵的力量是 $a_i$ ，所有的力量都互不相同。

有两种法术可以释放：

火球术：使用 $x$ 法力值然后摧毁 $k$ 个连续士兵。
狂乱：使用 $y$ 法力值然后选择两个连续士兵，力量较大的士兵摧毁力量较小的士兵。

现在给出初始的 $a_1,\ldots,a_n$ ，问是否能将它转变为 $b_1,\ldots,b_n$ ，若能请给出释放的最少法力值，若不能请输出 $-1$ 。

数据范围： $1 \leq n,m \leq 2 \cdot 10^5,1 \leq x,y \leq 10^9,1 \leq k \leq n,1 \leq a_i \leq n,1 \leq b_i \leq n$ 。

思路：首先非常显然的是验证 $b$ 是否为 $a$ 的子序列，如果不是则直接输出 $-1$ ，如果是的话找出它在 $a$ 中对应的点并分割。

然后，就可以对 $a$ 中分割的段进行处理，注意本题一看就是一个贪心大模拟，我们要仔细分类讨论：

首先入股段长大于等于 $k$ ，可以使用狂乱到最近的 $k$ 倍数，然后再用多次火球术。
如果当前段内最大值小于端点最大值，那么可以直接全用狂乱。
如果当前段内最大值大于端点最大值，但是段长小于 $k$ ，那么直接输出 $-1$ 。
如果当前段内最大值大于端点最大值，但是段长大于等于 $k$ ，那么可以直接让他们使用狂乱到 $k$ 后再用一次火球术（这里用了贪心，因为尽量大地用火球术的版本前文已经讨论过了，这里看一下尽量小的）。

由于每个段互相独立，因此加起来即可。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107


void solve() {
    int n, m;
    cin >> n >> m;
    ll x, y, k;
    cin >> x >> k >> y;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vi b(m);
    rep(i, 0, m - 1) cin >> b[i];
    if (n == m) {
        bool flag = true;
        rep(i, 0, n - 1) {
            if (a[i] != b[i]) {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << 0 << endl;
        else
            cout << -1 << endl;
        return;
    }
    map<int, int> ma;
    rep(i, 0, n - 1) ma[a[i]] = i;
    rep(i, 0, m - 1) {
        if (!ma.count(b[i])) {
            cout << -1 << endl;
            return;
        }
        b[i] = ma[b[i]];
    }
    rep(i, 0, m - 2) {
        if (b[i] >= b[i + 1]) {
            cout << -1 << endl;
            return;
        }
    }
    SegmentTree tree(a);
    ll ans = 0;
    rep(i, 0, m - 1) {
        if (i == 0 && b[i] != 0) {
            ll tem4 = LLONG_MAX;
            int tem3 = b[i];
            int tem2 = tree.query(0, b[i] - 1);
            if (tem3 < k && tem2 > a[b[i]]) {
                cout << -1 << endl;
                return;
            }
            if (tem2 < a[b[i]]) {
                tem4 = min(tem4, 1LL * tem3 * y);
            } else {
                int tem5 = tem3 - k;
                tem4 = min(tem4, 1LL * tem5 * y + 1LL * x);
            }
            if (tem3 >= k) {
                int tem5 = tem3 % k;
                tem4 = min(tem4, 1LL * y * tem5 + 1LL * x * (tem3 / k));
            }
            ans += tem4;
        }
        if (i == m - 1) {
            ll tem4 = LLONG_MAX;
            int tem3 = n - 1 - b[i];
            if (tem3 == 0) continue;
            int tem2 = tree.query(b[i] + 1, n - 1);
            if (tem3 < k && tem2 > a[b[i]]) {
                cout << -1 << endl;
                return;
            }
            if (tem2 < a[b[i]]) {
                tem4 = min(tem4, 1LL * tem3 * y);
            } else {
                int tem5 = tem3 - k;
                tem4 = min(tem4, 1LL * tem5 * y + 1LL * x);
            }
            if (tem3 >= k) {
                int tem5 = tem3 % k;
                tem4 = min(tem4, 1LL * y * tem5 + 1LL * x * (tem3 / k));
            }
            ans += tem4;
        } else {
            int tem = b[i + 1];
            if (tem == b[i] + 1) continue;
            int tem2 = tree.query(b[i] + 1, tem - 1);
            int tem3 = tem - b[i] - 1;
            ll tem4 = LLONG_MAX;
            if (tem3 < k && tem2 > max(a[b[i]], a[tem])) {
                cout << -1 << endl;
                return;
            }
            if (tem2 < max(a[b[i]], a[tem])) {
                tem4 = min(tem4, 1LL * tem3 * y);
            } else {
                int tem5 = tem3 - k;
                tem4 = min(tem4, 1LL * y * tem5 + 1LL * x);
            }
            if (tem3 >= k) {
                int tem5 = tem3 % k;
                tem4 = min(tem4, 1LL * y * tem5 + 1LL * x * (tem3 / k));
            }
            ans += tem4;
        }
    }
    cout << ans << endl;
    return;
}

Bitwise Queries(Easy)

出处：CF1451E1

题目大意：交互题，给定一个隐藏序列 $a$ ，现在要求在 $n+2$ 次操作内找出 $a$ 中所有元素的值，每次可以任意选择两个不同 $i,j$ ，求出 $a_i \ xor \ a_j$ ， $a_i \ or \ a_j$ 或者 $a_i \ and \ a_j$ 。

数据范围： $4 \leq n \leq 2^{16}$ ， $n$ 是 $2$ 的次幂。

思路：事实上好像在Easy Version中 $n$ 是 $2$ 的次幂完全没有用诶。

好的，看到题目给出了三种位运算形式，显然会回想起一个经典结论，那就是或运算可以用与运算跟异或运算表示出来，然后还有 $a+b=a \ and \ b \times 2+a \ xor \ b$ 。

于是，看到本题，可以想到先求出一个数，然后跟后续所有的数作异或运算。

然而，怎么求出一个数，注意到只给出两个数的三种运算是无法精确求出这两个数的，因此考虑三个数，有了三个数的两两之和，那么就求出来了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


int And(int l, int r) {
    cout << "AND " << l << ' ' << r << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
int Or(int l, int r) {
    cout << "OR " << l << ' ' << r << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
int Xor(int l, int r) {
    cout << "XOR " << l << ' ' << r << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
void report(vi& res) {
    cout << "! ";
    rep(i, 0, sz(res) - 1) cout << res[i] << ' ';
    cout << '\n';
    cout.flush();
}
void solve() {
    int n;
    cin >> n;
    vi res(n);
    int op = And(1, 2);
    int op2 = Xor(1, 2);
    int tem1 = op2 + 2 * op;
    int op3 = And(2, 3);
    int op4 = Xor(2, 3);
    int op5 = And(1, 3);
    int op6 = op2 ^ op4;
    int tem2 = op4 + 2 * op3;
    int tem3 = op6 + 2 * op5;
    res[0] = (tem3 + tem1 - tem2) / 2;
    res[1] = (tem1 + tem2 - tem3) / 2;
    res[2] = (tem2 + tem3 - tem1) / 2;
    rep(i, 3, n - 1) {
        int tem = Xor(1, i + 1);
        res[i] = res[0] ^ tem;
    }
    report(res);
    return;
}

Finding Zero

出处：CF1634D

题目大意：交互题，给定 $a_1,\ldots,a_n$ ，其中有一个元素是 $0$ ，现在需要在至多 $2 \cdot n-2$ 次查询中找出 $a_x$ 和 $a_y$ ，其中 $a_x=0$ 或者 $a_y=0$ ，每次查询给出互不相同的 $i,j,k$ ，返回 $\max(a_i,a_j,a_k)-\min(a_i,a_j,a_k)$ 。

数据范围：$4 \leq n \leq 1000$

思路：首先很好的一个习惯是，这里 $n \geq 4$ ，代表我们一开始可以对多少个元素进行初始操作。

接着看，这道题介绍了一个很新的思路，就是动态维护当前可能的元素，因为注意到只考虑 $\max(a_i,a_j,a_k)-\min(a_i,a_j,a_k)$ 是完全无法求出到底哪个是最大值哪个是最小值的，因此考虑维护当前最大值最小值，而最后的最小值就必定是 $0$ 。

然后，就要考虑怎么处理了，还是一样的思路，如果固定两个每次拉入第三个，那么完全不好处理，于是考虑拉入第四个，每组可以查询四次，则最后可以得出极差最大的两组，它们重复的部分就是当前最大跟最小值。

如果最后还剩余一个，那么拉一个之前查过的，不是当前最大跟最小值的元素，再查一次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


int ask(int l, int r, int m) {
    cout << "? " << l << ' ' << r << ' ' << m << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
void report(ll sum, ll sum2) {
    cout << "! " << sum << ' ' << sum2 << '\n';
    cout.flush();
}
void solve() {
    int n;
    cin >> n;
    int op, op2;
    pii ans = make_pair(1, 2);
    auto upd = [&](int x, int y) {
        int op1 = ask(ans.first, ans.second, x);
        int op2 = ask(ans.first, ans.second, y);
        int op3 = ask(ans.first, x, y);
        int op4 = ask(ans.second, x, y);
        int tem = max({op1, op2, op3, op4});
        if (op1 == tem && op2 == tem) ans = make_pair(ans.first, ans.second);
        else if (op1 == tem && op3 == tem) ans = make_pair(ans.first, x);
        else if (op1 == tem && op4 == tem) ans = make_pair(ans.second, x);
        else if (op2 == tem && op3 == tem) ans = make_pair(ans.first, y);
        else if (op2 == tem && op4 == tem) ans = make_pair(ans.second, y);
        else if (op3 == tem && op4 == tem) ans = make_pair(x, y);
        return;
    };
    for (int i = 3; i <= n; i += 2) {
        if (i == n) {
            int idx = -1;
            rep(j, 1, n - 1) {
                if (j != ans.first && j != ans.second) {
                    idx = j;
                    break;
                }
            }
            upd(idx, n);
        } else {
            upd(i, i + 1);
        }
    }
    report(ans.first, ans.second);
    return;
}

GCD Guess

出处：CF1665D

题目大意：交互题，需要在 $30$ 次查询内猜出一个 $1 \leq x \leq 10^9$ 的元素 $x$ ，每次可以选择 $a \not ={b}$ 的 $a,b$ ，返回 $gcd(x+a,x+b)$ 。

数据范围：$1 \leq x \leq 10^9$

思路：好的，看到这个数据范围，非常显然地，我们会想到二分，或者按位查找，但是很不幸的是，前者并没有显著的单调性，因此只能按位查找。

然后，我们要怎么查找当前位是 $0$ 还是 $1$ 呢？首先如果从高位查找的话，无法屏蔽对低位的影响，因此考虑从低位开始查找。

设当前查找的是 $i$ 位，那么固定 $b-a=2^{i+1}$ ，为了屏蔽低位影响，由于低位已经求出，那么直接加上补值使其进位，如果在第 $i$ 位也进位，那么显然地，这里需要原来的位为 $1$ ，反之为 $0$ 。

这题参考了题解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


void ask(int l, int r) {
    cout << "? " << l << ' ' << r << '\n';
    cout.flush();
}
void report(ll sum) {
    cout << "! " << sum << '\n';
    cout.flush();
}
void solve() {
    ll a, b;
    ll ans = 0;
    ll op;
    rep(i, 0, 29) {
        a = (1 << i) - ans, b = a + (1 << (i + 1));
        ask(a, b);
        cin >> op;
        if (((op >> i) & 1) == 0) ans |= (1 << i);
    }
    report(ans);
    return;
}

Small GCD

出处：CF1900D

题目大意：对于给定的 $a,b,c$ 三个数，排序后使它变为 $a \leq b \leq c$ ，然后令 $f(a,b,c)=gcd(a,b)$ 。

现在给定 $a_1,\ldots,a_n$ ，请求出 $\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\sum\limits_{k=j+1}^{n}f(a_i,a_j,a_k)$ 。

数据范围：$3 \leq n \leq 8 \cdot 10^4,1 \leq a_i \leq 10^5$

思路：由于最大值完全没有必要，因此考虑排序后枚举中间值，只需要考虑左边所有数与它的最大公因数之和。

好了，到这里就不会了，现在介绍一种求公因数和的常见方法：欧拉反演，因为注意到这个 $a_i$ 的值域，它必然可以用一些数学上的方法来做。

首先要知道，欧拉反演和莫比乌斯反演最核心的用途有以下几个：

把按照gcd/因子统计的题，变成按倍数或者因子枚举的题
把看上去 $O(n^2)$ 的题，降到 $O(V \log V)$ 量级
把已知前缀和式/倍数和式，反求原函数时作逆变换

欧拉反演定义：设 $f$ 是算术函数，定义

$$ \begin{aligned} F(n)&=\sum\limits_{d \mid n} f(d),\\\\ G(n)&=\sum\limits_{d \mid n}\phi(d)f\!\left(\frac{n}{d}\right)=(\phi * f)(n). \end{aligned} $$

这里的 $*$ 表示狄利克雷卷积，也就是

$$ (a*b)(n)=\sum\limits_{d \mid n}a(d)b\!\left(\frac{n}{d}\right). $$

此时，可以用下面两条式子把值函数和因子求和函数互相改写：

$$ \begin{aligned} \sum\limits_{d \mid n}\phi(d) &= n, \\\\ \sum\limits_{d \mid \gcd(x,y)}\phi(d) &= \gcd(x,y)=\sum\limits_{d \mid x,\ d \mid y}\phi(d). \end{aligned} $$

本题中，可以化为

$$ \begin{aligned} \sum\limits_{i=2}^{n}(n-i)\sum\limits_{j=1}^{i-1}\gcd(a_j,a_i) &=\sum\limits_{i=2}^{n}\sum\limits_{j=1}^{i-1}\sum\limits_{d \mid a_i,\ d \mid a_j}\phi(d)(n-i) \\\\ &=\sum\limits_{i=2}^{n}(n-i)\sum\limits_{d \mid a_i}\phi(d)\sum\limits_{j=1}^{i-1}(d \mid a_j) \\\\ &=\sum\limits_{i=2}^{n}(n-i)\sum\limits_{d \mid a_i}\phi(d)\cdot cnt_{i-1,d}. \end{aligned} $$

于是就能做了。

然后我们介绍莫比乌斯反演。设 $f,g$ 是算术函数，若

$$ g(n)=\sum\limits_{d \mid n}f(d). $$

则

$$ \begin{aligned} f(n)&=\sum\limits_{d \mid n}\mu(d)g\!\left(\frac{n}{d}\right) \\\\ \Leftrightarrow\quad f(n)&=\sum\limits_{k \geq 1}\mu(k)g(kn). \end{aligned} $$

此处有

$$ \mu(n)= \begin{cases} 1, & n=1 \\\\ 0, & n \text{ 含有平方因子} \\\\ (-1)^k, & n \text{ 是 } k \text{ 个互不相同质因子的乘积} \end{cases} $$

并且有常用恒等式：

$$ \begin{aligned} \sum\limits_{d \mid n}\mu(d)&=[n=1],\\\\ \phi(d)&=\sum\limits_{g \mid d}g\,\mu\!\left(\frac{d}{g}\right). \end{aligned} $$

在本题中，我们定义 $E(g)$ 为 $a_1,\ldots,a_{i-1}$ 中 $gcd(a_j,a_i)=g$ 的个数，以及 $C(d)$ 为 $a_1,\ldots,a_{i-1}$ 中 $d \mid a_j$ 的个数。

于是有，$\gcd(a_j,a_i)=g\ (g \mid a_i)$，等价于 $g \mid a_j$ 且 $\frac{a_j}{g}$ 与 $\frac{a_i}{g}$ 互质。用莫比乌斯函数展开即得到

$$ \begin{aligned} [\gcd(x,m)=1] &=\sum\limits_{t \mid \gcd(x,m)}\mu(t) \\\\ &=\sum\limits_{t \mid x,\ t \mid m}\mu(t). \end{aligned} $$

因此有

$$ \begin{aligned} E(g) &=\sum\limits_{j=1,\ g \mid a_j}^{i-1}\left[\gcd\!\left(\frac{a_j}{g},\frac{a_i}{g}\right)=1\right] \\\\ &=\sum\limits_{j=1,\ g \mid a_j}^{i-1}\sum\limits_{t \mid \frac{a_i}{g},\ t \mid \frac{a_j}{g}}\mu(t) \\\\ &=\sum\limits_{t \mid \frac{a_i}{g}}\mu(t)C(gt). \end{aligned} $$

于是

$$ \begin{aligned} \sum\limits_{j=1}^{i-1}\gcd(a_j,a_i) &=\sum\limits_{g \mid a_i}g\sum\limits_{t \mid \frac{a_i}{g}}\mu(t)C(gt) \\\\ &=\sum\limits_{d \mid a_i}C(d)\sum\limits_{g \mid d}g\,\mu\!\left(\frac{d}{g}\right) \\\\ &=\sum\limits_{d \mid a_i}\phi(d)C(d). \end{aligned} $$

做法同上，作者脑子烧了，先学欧拉反演吧。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


constexpr int MX = 1e5 + 1;
int phi[MX];
auto init = [] {
    auto Phi = [](int n) -> int {
        int res = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) res = res / n * (n - 1);
        return res;
    };
    rep(i, 1, MX - 1) { phi[i] = Phi(i); }
    return 0;
}();
vector<int> divisors[MX];
auto init2 = [] {
    for (int i = 1; i < MX; i++) {
        for (int j = i; j < MX; j += i) {
            divisors[j].push_back(i);
        }
    }
    return 0;
}();
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    ranges::sort(a);
    vi cnt(MX + 1);
    rep(i, 0, n - 1) {
        for (int& p : divisors[a[i]]) {
            ans += 1LL * (n - 1 - i) * phi[p] * cnt[p];
        }
        for (int& p : divisors[a[i]]) {
            cnt[p]++;
        }
    }
    cout << ans << endl;
    return;
}

New Year and Ancient Prohpecy

出处：CF611D

题目大意：给定一个 $n$ 位数，要求将其拆分为若干数字，满足数字的顺序要严格递增，都是正整数，且没有前导零，求所有可能的方案数，最后模 $10^9+7$ 。

数据范围：$1 \leq n \leq 5000$

思路：很容易能想到划分式DP，用 $dp[i][j]$ 表示当前结尾为 $i$ ，同时最后一段长度为 $j$ 的方案数，然后，如果前一段的长度小于这一段，那么就直接加上去（注意这里可以用前缀和优化）。

然后，如果前一段的长度跟这一段相等呢？这里采用LCP优化，即找到两段到结尾的子段最长的公共前缀，然后下一个字符就可以判断它们的大小关系了。

最后，记得判断前导零，这题疑似有点份。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vvi dp(n + 1, vi(n + 1));
    vvi pre(n + 1, vi(n + 1));
    vvi lcp(n + 2, vi(n + 2));
    frep(i, n, 1) {
        frep(j, n, 1) {
            if (s[i - 1] == s[j - 1]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
        }
    }
    rep(i, 1, n) dp[i][i] = 1;
    rep(i, 1, n) {
        rep(j, 1, i) {
            if (j < i) {
                if (i - 2 * j >= 0 && s[i - j] != '0') {
                    int l = lcp[i - 2 * j + 1][i - j + 1];
                    if (l < j && s[i - 2 * j + l] < s[i - j + l]) dp[i][j] = (dp[i][j] + dp[i - j][j]) % MOD;
                }
                if (s[i - j] != '0') dp[i][j] = (dp[i][j] + pre[i - j][j - 1]) % MOD;
            }
            pre[i][j] = (pre[i][j - 1] + dp[i][j]) % MOD;
        }
        rep(j, i + 1, n) pre[i][j] = pre[i][i];
    }
    ll ans = 0;
    rep(i, 1, n) {
        ans += dp[n][i] % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return;
}