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;
}

Directing Edges

出处：CF1385E

题目大意：

数据范围：

思路：

 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


void solve() {
    int n, m, x, y, op;
    cin >> n >> m;
    vi ord(n);
    vi deg(n);
    vvi ma(n);
    vector<pii> ma2;
    vector<pii> ma3;
    queue<int> q;
    rep(i, 0, m - 1) {
        cin >> op >> x >> y;
        if (op == 0) {
            ma2.emplace_back(x - 1, y - 1);
        } else {
            ma[x - 1].push_back(y - 1);
            ma3.emplace_back(x - 1, y - 1);
            deg[y - 1]++;
        }
    }
    int cnt = 0;
    vi tem;
    rep(i, 0, n - 1) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        tem.push_back(node);
        for (int& p : ma[node]) {
            if (--deg[p] == 0) q.push(p);
        }
    }
    if (sz(tem) != n) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    rep(i, 0, n - 1) ord[tem[i]] = i;
    for (auto& p : ma2) {
        if (ord[p.first] > ord[p.second]) swap(p.first, p.second);
    }
    for (auto& p : ma2) cout << p.first + 1 << ' ' << p.second + 1 << endl;
    for (auto& p : ma3) cout << p.first + 1 << ' ' << p.second + 1 << endl;
    return;
}

Interacdive Problem

出处：CF1624F

题目大意：

数据范围：

思路：

 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


int ask(int l) {
    cout << "+ " << l << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
void report(ll a) {
    cout << "! " << a << '\n';
    cout.flush();
}
void solve() {
    int n;
    cin >> n;
    int l = 1, r = n - 1, mid;
    int sum = 0;
    int ans = 1;
    while (l <= r) {
        mid = (l + r) / 2;
        int tem = n - mid;
        int tem2 = (tem - sum % n + n) % n;
        sum += tem2;
        int tem3 = ask(tem2);
        if (tem3 == sum / n) {
            r = mid - 1;
        } else {
            ans = mid;
            l = mid + 1;
        }
    }
    report(ans + sum);
    return;
}

Salyg1n and Array (simple version)

出处：CF1867E1

题目大意：

数据范围：

思路：

 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


int ask(int l) {
    cout << "? " << l << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
void report(ll a) {
    cout << "! " << a << '\n';
    cout.flush();
}
void solve() {
    int n, k;
    cin >> n >> k;
    if (n % k == 0) {
        int tem = 0;
        for (int i = 1; i <= n; i += k) {
            int op = ask(i);
            tem ^= op;
        }
        report(tem);
        return;
    }
    int tem = 0;
    for (int i = 1; i <= n / k * k; i += k) {
        int op = ask(i);
        tem ^= op;
    }
    int idx = n / k * k + 1;
    rep(i, idx, n) {
        int op = ask(i - k + 1);
        tem ^= op;
    }
    report(tem);
    return;
}

Geo Game

出处：CF1903E

题目大意：

数据范围：

思路：

  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
108
109
110
111


void ask(int l) {
    cout << l << '\n';
    cout.flush();
}
void report(ll a, ll b, ll c, ll d) {
    cout << "! " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
    cout.flush();
}
void solve() {
    int n, op;
    cin >> n;
    ll sx, sy;
    cin >> sx >> sy;
    vector<pll> ma(n);
    rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
    set<int> ma1;
    set<int> ma2;
    rep(i, 0, n - 1) {
        if ((ma[i].first + ma[i].second) % 2 == 1)
            ma1.insert(i + 1);
        else
            ma2.insert(i + 1);
    }
    ll tem = (sx + sy) % 2;
    if (tem == 0) {
        if (sz(ma1) > sz(ma2)) {
            cout << "Second" << endl;
            cout.flush();
            rep(i, 1, n) {
                if (i % 2) {
                    cin >> op;
                    if (ma1.count(op))
                        ma1.erase(op);
                    else
                        ma2.erase(op);
                } else {
                    if (!ma2.empty()) {
                        ask(*ma2.begin());
                        ma2.erase(ma2.begin());
                    } else {
                        ask(*ma1.begin());
                        ma1.erase(ma1.begin());
                    }
                }
            }
        } else {
            cout << "First" << endl;
            cout.flush();
            rep(i, 1, n) {
                if (i % 2) {
                    if (!ma1.empty()) {
                        ask(*ma1.begin());
                        ma1.erase(ma1.begin());
                    } else {
                        ask(*ma2.begin());
                        ma2.erase(ma2.begin());
                    }
                } else {
                    cin >> op;
                    if (ma1.count(op))
                        ma1.erase(op);
                    else
                        ma2.erase(op);
                }
            }
        }
    } else {
        if (sz(ma1) >= sz(ma2)) {
            cout << "First" << endl;
            cout.flush();
            rep(i, 1, n) {
                if (i % 2) {
                    if (!ma2.empty()) {
                        ask(*ma2.begin());
                        ma2.erase(ma2.begin());
                    } else {
                        ask(*ma1.begin());
                        ma1.erase(ma1.begin());
                    }
                } else {
                    cin >> op;
                    if (ma1.count(op))
                        ma1.erase(op);
                    else
                        ma2.erase(op);
                }
            }
        } else {
            cout << "Second" << endl;
            cout.flush();
            rep(i, 1, n) {
                if (i % 2) {
                    cin >> op;
                    if (ma1.count(op))
                        ma1.erase(op);
                    else
                        ma2.erase(op);
                } else {
                    if (!ma1.empty()) {
                        ask(*ma1.begin());
                        ma1.erase(ma1.begin());
                    } else {
                        ask(*ma2.begin());
                        ma2.erase(ma2.begin());
                    }
                }
            }
        }
    }
    return;
}

Infinite Maze

出处：CF196B

题目大意：

数据范围：

思路：

 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


int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
void solve() {
    int m, n;
    cin >> m >> n;
    vector<string> ma(m);
    rep(i, 0, m - 1) cin >> ma[i];
    int idx1 = -1, idx2 = -1;
    rep(i, 0, m - 1) {
        rep(j, 0, n - 1) {
            if (ma[i][j] == 'S') {
                idx1 = i, idx2 = j;
                break;
            }
        }
    }
    vector<vector<pii>> vis(m, vector<pii>(n, make_pair(-1, -1)));
    auto dfs = [&](this auto&& dfs, int x, int y, int tx, int ty) -> bool {
        vis[x][y] = {tx, ty};
        rep(i, 0, 3) {
            int ax = (x + dx[i] + m) % m, ay = (y + dy[i] + n) % n;
            int bx = tx + dx[i], by = ty + dy[i];
            if (ma[ax][ay] == '#') continue;
            if (vis[ax][ay] == make_pair(-1, -1)) {
                if (dfs(ax, ay, bx, by)) return true;
            } else {
                if (vis[ax][ay] != make_pair(bx, by)) return true;
            }
        }
        return false;
    };
    bool flag = dfs(idx1, idx2, idx1, idx2);
    cout << (flag ? "Yes" : "No") << endl;
    return;
}

Appleman and Tree

出处：CF461B

题目大意：

数据范围：

思路：

 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


const ll MOD = 1e9 + 7;
void solve() {
    int n, x;
    cin >> n;
    vvi ma(n);
    rep(i, 1, n - 1) {
        cin >> x;
        ma[x].push_back(i);
        ma[i].push_back(x);
    }
    vi c(n);
    rep(i, 0, n - 1) cin >> c[i];
    auto dfs = [&](this auto&& dfs, int x, int pa) -> pll {
        ll tem = 0, tem2 = 0;
        if (c[x] == 0)
            tem = 1;
        else
            tem2 = 1;
        for (int& p : ma[x]) {
            if (p == pa) continue;
            auto [l1, l2] = dfs(p, x);
            ll temp = tem, temp2 = tem2;
            tem = temp * (l1 + l2) % MOD;
            tem2 = (temp * l2 % MOD + temp2 * (l1 + l2) % MOD) % MOD;
        }
        return {tem, tem2};
    };
    auto [tem, tem2] = dfs(0, -1);
    cout << tem2 << endl;
    return;
}

Array Queries

出处：CF797E

题目大意：

数据范围：

思路：

 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


void solve() {
    int n, q, p, k;
    cin >> n;
    int B = sqrt(n);
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    cin >> q;
    vvi suf(B + 1, vi(n));
    rep(i, 1, B) {
        frep(j, n - 1, 0) {
            suf[i][j] = 1;
            if (j + a[j] + i <= n - 1) suf[i][j] += suf[i][j + a[j] + i];
        }
    }
    rep(i, 0, q - 1) {
        cin >> p >> k;
        p--;
        if (k > B) {
            int tem = 0;
            while (p <= n - 1) {
                tem++;
                p += a[p] + k;
            }
            cout << tem << endl;
        } else {
            cout << suf[k][p] << endl;
        }
    }
    return;
}

Mahmoud and Ehab and the binary string

出处：CF862D

题目大意：

数据范围：

思路：

 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


int ask(string l) {
    cout << "? " << l << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
void report(ll a, ll b) {
    cout << "! " << a << ' ' << b << '\n';
    cout.flush();
}
void solve() {
    int n;
    cin >> n;
    int idx0 = -1, idx1 = -1;
    string s, t;
    rep(i, 0, n - 1) s.push_back('0');
    t = s;
    int tem = ask(s);
    s[0] = '1';
    int tem2 = ask(s);
    if (tem == tem2 + 1) {
        idx1 = 0;
    } else {
        idx0 = 0;
    }
    if (idx1 != -1) {
        int l = 0, r = n - 1, mid, ans = 0;
        while (l <= r) {
            mid = (l + r) / 2;
            string tem3 = t;
            rep(i, l, mid) tem3[i] = '1';
            int tem4 = ask(tem3);
            if ((mid - l + 1) - (tem + mid - l + 1 - tem4) / 2 > 0) {
                ans = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        idx0 = ans;
    } else {
        int l = 0, r = n - 1, mid, ans = 0;
        while (l <= r) {
            mid = (l + r) / 2;
            string tem3 = t;
            rep(i, l, mid) tem3[i] = '1';
            int tem4 = ask(tem3);
            if ((tem + mid - l + 1 - tem4) / 2 > 0) {
                ans = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        idx1 = ans;
    }
    report(idx0 + 1, idx1 + 1);
    return;
}

Yet Another Yet Another Task

出处：CF1359D

题目大意：

数据范围：

思路：

  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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122


struct Info {
    ll sum, pre, suf, ans;
    Info(ll x = 0) : sum(x), pre(x), suf(x), ans(x) {}
};
Info operator+(const Info& a, const Info& b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.pre = max(a.pre, a.sum + b.pre);
    c.suf = max(b.suf, b.sum + a.suf);
    c.ans = max({a.ans, b.ans, a.suf + b.pre});
    return c;
}
template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return a + b; }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }  // 若遇到固定左端点的情况，需要使用全局变量（或者传入引用）记录前缀分段最大值，加一个被待求区间完全覆盖的剪枝

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }  // 传入一个数组维护

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中第一个满足条件的下标

    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vector<Info> b(n);
    rep(i, 0, n - 1) b[i] = Info(a[i]);
    SegmentTree<Info> seg(b);
    vector<int> r(n, n);
    vector<int> l(n, -1);
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[s.top()] <= a[i]) s.pop();
        if (!s.empty()) r[i] = s.top();
        s.push(i);
    }  // 求右边第一个小于的下标
    while (!s.empty()) s.pop();
    for (int i = 0; i <= n - 1; i++) {
        while (!s.empty() && a[s.top()] <= a[i]) s.pop();
        if (!s.empty()) l[i] = s.top();
        s.push(i);
    }  // 求左边第一个小于的下标
    ll ans = 0;
    rep(i, 0, n - 1) {
        Info left = seg.query(l[i] + 1, i);
        Info right = seg.query(i, r[i] - 1);
        ans = max(ans, left.suf + right.pre - 2 * a[i]);
    }
    cout << ans << endl;
    return;
}

Odd-Even Subsequence

出处：CF1370D

题目大意：

数据范围：

思路：

 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


void solve() {
    int n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    auto check = [&](int mid) -> bool {
        int cnt = 0;
        rep(i, 0, n - 1) {
            if (cnt % 2 == 0) {
                if (a[i] > mid)
                    continue;
                else
                    cnt++;
            } else
                cnt++;
        }
        if (cnt >= k) return true;
        cnt = 0;
        rep(i, 0, n - 1) {
            if (cnt % 2 == 1) {
                if (a[i] > mid)
                    continue;
                else
                    cnt++;
            } else
                cnt++;
        }
        return cnt >= k;
    };
    int l = 1, r = 1e9, mid, ans = 1;
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
    return;
}

Count Paths

出处：CF1923E

题目大意：

数据范围：

思路：

 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


void solve() {
    int n, x, y;
    cin >> n;
    vi co(n);
    rep(i, 0, n - 1) cin >> co[i];
    vvi ma(n);
    rep(i, 1, n - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    ll ans = 0;
    auto dfs = [&](this auto&& dfs, int x, int pa) -> map<int, int> {
        map<int, int> ma2;
        int c = co[x];
        for (int& p : ma[x]) {
            if (p == pa) continue;
            auto ma3 = dfs(p, x);
            if (sz(ma2) < sz(ma3)) {
                swap(ma2, ma3);
            }
            if (ma2.count(c)) {
                ans += 1LL * ma2[c];
                ma2.erase(c);
            }
            for (auto& [y, z] : ma3) {
                if (y == c)
                    ans += 1LL * z;
                else {
                    if (ma2.count(y)) ans += 1LL * ma2[y] * z;
                    ma2[y] += z;
                }
            }
        }
        ma2[c] = 1;
        return ma2;
    };
    dfs(0, -1);
    cout << ans << endl;
    return;
}