1900

Absolute Beauty

出处：CF1898D

题目大意：给定 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_n$ ，定义美丽值为 $\sum\limits_{i=1}^{n}|a_i-b_i|$ ，现在可以交换任意 $b_i,b_j$ 至多一次，问能达到的最大美丽值是多少？

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

思路：其实是个不难的题目，首先求出原来的美丽值，考虑每次变化对原来的贡献。

通过画图表示交换的两对分别为大于和小于的所有情况，可以将每对数表示为一条线段，观察得出这两条线段交换的贡献就是中间的空白区域长度乘2，于是贪心即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int n;
    cin >> n;
    vl a(n);
    vl b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    ll tot = 0;
    ll maxx = 0;
    rep(i, 0, n - 1) { tot += 1LL * abs(a[i] - b[i]); }
    maxx = max(maxx, tot);
    vector<pll> ma;
    rep(i, 0, n - 1) ma.emplace_back(min(a[i], b[i]), max(a[i], b[i]));
    ll mixx2 = ma[0].second;
    ll maxx2 = ma[0].first;
    rep(i, 1, n - 1) {
        if (maxx2 >= ma[i].second) maxx = max(maxx, tot + 2 * (maxx2 - ma[i].second));
        if (mixx2 <= ma[i].first) maxx = max(maxx, tot + 2 * (ma[i].first - mixx2));
        maxx2 = max(maxx2, ma[i].first);
        mixx2 = min(mixx2, ma[i].second);
    }
    cout << maxx << endl;
    return;
}

Perform Easily

出处：CF1413C

题目大意：给定 $a_1,a_2,\ldots,a_6$ ，现在给定 $b_1,b_2,\ldots,b_n$ ，要求每个 $b_j$ 变为 $b_j-a_i$ ，从而使最大值和最小值之差最小，请求出这个最小差值。

数据范围：$1 \leq n \leq 10^5, 1 \leq b_i \leq 10^9, b_i \geq a_j$。

思路：这道题跟LC3854 相似，只需要求出所有可能值，排序后做不定长滑窗，保证当前滑窗内有原来全部元素即可。

 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
void solve() {
    vi a(6);
    rep(i, 0, 5) cin >> a[i];
    int n;
    cin >> n;
    vi b(n);
    rep(i, 0, n - 1) cin >> b[i];
    vector<pii> tem;
    rep(i, 0, 5) {
        rep(j, 0, n - 1) { tem.emplace_back(b[j] - a[i], j); }
    }
    ranges::sort(tem);
    int l = 0;
    map<int, int> ma;
    int ans = INT_MAX;
    rep(r, 0, sz(tem) - 1) {
        ma[tem[r].second]++;
        if (sz(ma) == n) {
            while (true) {
                if (ma[tem[l].second] == 1) break;
                ma[tem[l].second]--;
                l++;
            }
        }
        if (sz(ma) == n) ans = min(ans, tem[r].first - tem[l].first);
    }
    cout << ans << endl;
    return;
}

Split Plus K

出处：CF1909D

题目大意：有 $n$ 个数 $a_1,\ldots,a_n$ ，现在要进行下列操作任意次数：找一个 $x$ ，将其替换为 $y+z=x+k$ ，问最后是否能使剩下的所有数相等？如果可以，最小操作数量是多少？

数据范围：$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{12},1 \leq a_i \leq 10^{12}$。

思路：首先，分裂可以看成合并，那么考虑最后有 $t$ 个 $b$ ，得到 $t_i \cdot b=(t_i-1) \cdot k+a_i$ ，也就是 $t_i(b-k)=a_i-k$ ，那么此时需要让 $\sum\limits_{i=1}^{n}t_i$ 最小，也就是 $b-k$ 需要是所有 $a_i-k$ 的最大公因数（注意如果出现异号的 $a_i-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
void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    bool pd = true;
    rep(i, 1, n - 1) {
        if (a[i] != a[0]) {
            pd = false;
            break;
        }
    }
    if (pd) {
        cout << 0 << endl;
        return;
    }
    rep(i, 0, n - 1) a[i] -= k;
    rep(i, 0, n - 1) {
        if (a[i] == 0) {
            cout << -1 << endl;
            return;
        }
    }
    ll mixx = *min_element(all(a));
    ll maxx = *max_element(all(a));
    if (mixx < 0 && maxx > 0) {
        cout << -1 << endl;
        return;
    }
    ll ans = __gcd(abs(a[0]), abs(a[1]));
    rep(i, 0, n - 1) { ans = __gcd(ans, abs(a[i])); }
    ll res = 0;
    rep(i, 0, n - 1) { res += abs(a[i]) / ans; }
    cout << res - n << endl;
    return;
}

Pashmak and Graph

出处：CF459E

题目大意：给定一个 $n$ 个点 $m$ 条边的加权无向图，需要找到一条边数尽可能多的路径（可以不是简单路径），使得路径上每一条边的权值都严格大于前一条边的权值。

数据范围：$2 \leq n \leq 3 \cdot 10^5, 1 \leq m \leq \min(n \cdot (n-1),3 \cdot 10^5)$。

思路：就是在图上求LIS，注意由于是LIS因此必然不可能形成自环，此处可以将边按照权值排序，然后做DP，注意这里由于多条边的权值可能相等，因此不能分次序更新，应该同时转移后再重新合并。

 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
void solve() {
    int n, m, x, y, z;
    cin >> n >> m;
    vector<tri> ma;
    rep(i, 0, m - 1) {
        cin >> x >> y >> z;
        ma.emplace_back(x - 1, y - 1, z);
    }
    int l = 0;
    vi dp(n);
    int ans = 0;
    map<int, vector<pii>> ma2;
    for (auto& [x, y, z] : ma) {
        ma2[z].emplace_back(x, y);
    }
    for (auto& [a, b] : ma2) {
        vector<pii> tem;
        for (auto& [x, y] : b) {
            tem.emplace_back(y, dp[x] + 1);
        }
        for (auto& p : tem) {
            dp[p.first] = max(dp[p.first], p.second);
            ans = max(ans, dp[p.first]);
        }
    }
    cout << ans << endl;
    return;
}

Fafa and Ancient Alphabet

出处：CF935D

题目大意：给定一个字符集，其中字符为 $1 \sim m$ ，给定两个字符串 $S_1$ 和 $S_2$ ，它们中部分已经缺失，用 $0$ 表示，每个 $0$ 位置等概率填上字符集中的数字，问字典序上 $S_1$ 大于 $S_2$ 的概率，请用模 $10^9+7$ 的逆元表示。

数据范围：$1 \leq n,m \leq 10^5$。

思路：考虑从前往后遍历，考虑以下四种情况：

若 $a_i \not ={0} \wedge b_i=0$ ，那么大于的概率为 $\frac{a_i-1}{m}$ ，等于的概率为 $\frac{1}{m}$ 。
若 $a_i=0 \wedge b_i \not ={0}$ ，那么大于的概率为 $\frac{m-b_i}{m}$ ，等于的概率为 $\frac{1}{m}$ 。
若 $a_i=0 \wedge b_i=0$ ，那么大于的概率为 $\frac{m-1}{2m}$ ，等于的概率为 $\frac{1}{m}$ 。
若 $a_i \not ={0} \wedge b_i \not ={0}$ ，那么分以下三种情况：
- $a_i>b_i$ ，那么答案加上之前相等的概率，并输出
- $a_i
- $a_i=b_i$ ，无变化，继续遍历

 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
void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n);
    vi b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vector<pii> ma(n);
    ll tem = 1;
    ll ans = 0;
    rep(i, 0, n - 1) {
        if (a[i] != 0 && b[i] != 0) {
            if (a[i] < b[i]) {
                cout << ans << endl;
                return;
            } else if (a[i] == b[i]) {
                continue;
            } else {
                ans += tem;
                ans %= MOD;
                cout << ans << endl;
                return;
            }
        } else if (a[i] != 0 && b[i] == 0) {
            ans += mul(tem, mul(a[i] - 1, qpow(m, MOD - 2)));
            ans %= MOD;
            tem = mul(tem, qpow(m, MOD - 2));
        } else if (a[i] == 0 && b[i] != 0) {
            ans += mul(tem, mul(m - b[i], qpow(m, MOD - 2)));
            ans %= MOD;
            tem = mul(tem, qpow(m, MOD - 2));
        } else {
            ans += mul(tem, mul(m - 1, qpow(2 * m, MOD - 2)));
            ans %= MOD;
            tem = mul(tem, qpow(m, MOD - 2));
        }
    }
    cout << ans << endl;
    return;
}

Classy Numbers

出处：CF1036C

题目大意：多组询问给定区间 $[L,R]$ ，统计十进制表示中非零数字个数不超过 $3$ 的整数数量。

数据范围： $1 \leq T \leq 10^4, 1 \leq L_i \leq R_i \leq 10^{18}$

思路：

 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() {
    string num1, num2;
    cin >> num1 >> num2;
    int n = num2.length();
    int dif = n - num1.length();
    const int INF = 1e9 + 7;
    map<pair<int, int>, ll> ma;
    auto dfs = [&](this auto&& dfs, int cnt, int s, bool limit_low, bool limit_high) -> int {
        if (cnt == n) return s <= 3;
        if (s > 3) return 0;
        if (!limit_low && !limit_high && ma.count({cnt, s})) return ma[{cnt, s}];
        ll res = 0;
        int lo = limit_low && cnt >= dif ? num1[cnt - dif] - '0' : 0;
        int hi = limit_high ? num2[cnt] - '0' : 9;
        int d = lo;
        if (limit_low && cnt < dif) {
            res += dfs(cnt + 1, s, true, false) % INF;
            res %= INF;
            d = 1;
        }
        for (; d <= hi; d++) {
            res += dfs(cnt + 1, s + (d != 0), limit_low && d == lo, limit_high && d == hi) % INF;
            res %= INF;
        }
        if (!limit_high && !limit_low) ma[{cnt, s}] = res;
        return res;
    };
    cout << dfs(0, 0, true, true) << endl;
    return;
}

Dwarves, Hats and Extrasensory Abilities

出处：CF1063C

题目大意：交互题。每次得到一个新点坐标，需要输出一条直线，把已出现的点按隐藏颜色分到直线两侧。

数据范围： $1 \leq n \leq 30, |x_i|,|y_i| \leq 10^9$

思路：

 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
string ask(int l, int r) {
    cout << l << ' ' << r << '\n';
    cout.flush();
    string op;
    cin >> op;
    return op;
}
void report(ll a, ll b, ll c, ll d) {
    cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
    cout.flush();
}
void solve() {
    int n;
    cin >> n;
    string s;
    int r = 1e9, l = 0;
    string op = ask(1, 0);
    rep(i, 1, n - 1) {
        int mid = (l + r) / 2;
        string op2 = ask(1, mid);
        if (op == op2) {
            l = mid;
        } else
            r = mid;
    }
    report(0, l, 2, r);
    return;
}

Cow and Fields

出处：CF1307D

题目大意：给定无向连通图和 $k$ 个特殊点，可以在两个特殊点之间加一条边，最大化加边后 $1$ 到 $n$ 的最短路。

数据范围： $2 \leq n \leq 2 \cdot 10^5, n-1 \leq m \leq 2 \cdot 10^5, 2 \leq k \leq n$

思路：

 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
void solve() {
    int n, m, k, x, y;
    cin >> n >> m >> k;
    vi a(k);
    rep(i, 0, k - 1) {
        cin >> a[i];
        a[i]--;
    }
    vvi ma(n);
    rep(i, 1, m) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    vi dis1(n, -1);
    vi dis2(n, -1);
    queue<int> q;
    q.push(0);
    dis1[0] = 0;
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        for (int& p : ma[node]) {
            if (dis1[p] == -1) {
                dis1[p] = dis1[node] + 1;
                q.push(p);
            }
        }
    }
    dis2[n - 1] = 0;
    while (!q.empty()) q.pop();
    q.push(n - 1);
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        for (int& p : ma[node]) {
            if (dis2[p] == -1) {
                q.push(p);
                dis2[p] = dis2[node] + 1;
            }
        }
    }
    int ans = dis1[n - 1];
    vector<pii> ma2;
    for (int& p : a) ma2.emplace_back(dis1[p], dis2[p]);
    sort(all(ma2), [&](const pii& x, const pii& y) { return x.first - x.second < y.first - y.second; });
    int tem = ma2[0].first;
    int ans2 = 0;
    rep(i, 1, k - 1) {
        ans2 = max(ma2[i].second + tem + 1, ans2);
        tem = max(ma2[i].first, tem);
    }
    cout << min(ans, ans2) << endl;
    return;
}

Guessing the Greatest (hard version)

出处：CF1486C2

题目大意：交互题。每次询问区间会返回区间内次大值的位置，需要在 $20$ 次询问内找出全局最大值的位置。

数据范围： $2 \leq n \leq 10^5$

思路：

 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(int l, int r) {
    cout << "? " << l << ' ' << r << '\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 idx = ask(1, n);
    int idx2 = -1;
    if (idx == 1) {
        int l = idx + 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            int tem = ask(idx, mid);
            if (tem == idx) {
                idx2 = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        report(idx2);
        return;
    }
    int tem2 = ask(1, idx);
    if (tem2 == idx) {
        int l = 1, r = idx - 1, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            int tem = ask(mid, idx);
            if (tem == idx) {
                idx2 = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        report(idx2);
        return;
    }
    int l = idx + 1, r = n, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        int tem = ask(idx, mid);
        if (tem == idx) {
            idx2 = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    report(idx2);
    return;
}

River Locks

出处：CF1700D

题目大意：给定每个闸门容量 $v_i$ 和多组注水速度询问，求在该速度下填满整个系统的最短时间，无法完成则输出 $-1$ 。

数据范围： $1 \leq n \leq 2 \cdot 10^5, 1 \leq v_i \leq 10^9, 1 \leq q \leq 2 \cdot 10^5, 1 \leq t_j \leq 10^9$

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int n, q, x;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl pre(n);
    pre[0] = a[0];
    rep(i, 1, n - 1) pre[i] = pre[i - 1] + a[i];
    ll maxx = 0;
    rep(i, 0, n - 1) { maxx = max(maxx, (pre[i] + i) / (i + 1)); }
    cin >> q;
    rep(i, 0, q - 1) {
        cin >> x;
        if (maxx > x) {
            cout << -1 << endl;
            continue;
        }
        cout << (pre[n - 1] + x - 1) / x << endl;
    }
    return;
}

Counting Arrays

出处：CF1749D

题目大意：给定 $n,m$ ，统计长度为 $n$ 且满足题目删除条件的数组数量，答案对 $m$ 取模。

数据范围： $2 \leq n \leq 3 \cdot 10^5, 1 \leq m \leq 10^{12}$

思路：

 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
constexpr int MOD = 998244353;
int mul(int x, int y) { return x * 1LL * y % MOD; }
int qpow(int x, int y) {
    int z = 1;
    while (y > 0) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}  // 求x**y%MOD

// 注意：当MOD为质数时， (x/y)%MOD=(x*(y**(MOD-2)))%MOD，即y在模MOD意义下的逆元为b^{-1} \equiv b^{p-2} mod p

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<bool> vis(n + 1, true);
    vis[0] = false, vis[1] = false;
    rep(i, 2, n) {
        if (vis[i]) {
            if (1LL * i * i <= n) {
                for (ll j = 1LL * i * i; j <= n; j += i) vis[j] = false;
            }
        }
    }
    ll tem = 1;
    ll tot = 1;
    ll tem2 = 1;
    ll ans = 0;
    rep(i, 1, n) {
        tot = mul(tot, m % MOD);
        if (vis[i]) {
            if (tem <= m / i)
                tem *= i;
            else
                tem = m + 1;
        }
        ll cnt = m / tem;
        tem2 = mul(tem2, cnt % MOD);
        ans = (ans + tot - tem2 + MOD) % MOD;
    }
    cout << ans << endl;
    return;
}

Color Rows and Columns

出处：CF2000F

题目大意：给定 $n$ 个矩形和目标得分 $k$ ，每次可以给某个矩形的一整行或一整列染色并获得分数，求达到至少 $k$ 分的最小操作次数。

数据范围： $1 \leq t \leq 100, 1 \leq n \leq 1000, 1 \leq k \leq 100, 1 \leq a_i,b_i \leq 100$

思路：

 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
void solve() {
    int n, k;
    cin >> n >> k;
    vector<pii> ma(n);
    rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
    vvi g(n, vi(k + 1, INT_MAX / 2));
    rep(i, 0, n - 1) {
        g[i][0] = 0;
        rep(j, 0, ma[i].first) {
            rep(v, 0, ma[i].second) {
                int tem = j + v;
                if (tem <= k) g[i][tem] = min(g[i][tem], j * ma[i].second + v * ma[i].first - j * v);
            }
        }
    }
    vvi dp(n + 1, vi(k + 1, INT_MAX / 2));
    int ans = INT_MAX;
    dp[0][0] = 0;
    rep(i, 1, n) {
        dp[i][0] = 0;
        rep(j, 1, k) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            rep(v, 0, j - 1) { dp[i][j] = min(dp[i][j], dp[i - 1][v] + g[i - 1][j - v]); }
        }
        if (dp[i][k] != INT_MAX / 2) ans = min(ans, dp[i][k]);
    }
    cout << (ans == INT_MAX ? -1 : ans) << endl;
    return;
}

Finding OR Sum

出处：CF2077B

题目大意：交互题。隐藏两个数 $x,y$ ，可以询问若干个 $n$ 并获得 $(n|x)+(n|y)$ ，最后给定 $m$ ，需要回答 $(m|x)+(m|y)$ 。

数据范围： $1 \leq t \leq 10^4, 0 \leq x,y,m < 2^{30}$

思路：

 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
const int tem1 = 715827882;
const int tem2 = 357913941;
ll ask(ll l) {
    cout << l << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
ll report() {
    cout << "! " << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
void report2(ll x) {
    cout << x << '\n';
    cout.flush();
}
void solve() {
    ll tem3 = ask(tem1);
    tem3 -= 2 * tem1;
    ll tem4 = ask(tem2);
    tem4 -= 2 * tem2;
    ll m = report();
    ll x = 0, y = 0;
    for (int i = 0; i < 30; i += 2) {
        if ((tem3 >> i) & 1)
            x |= (1LL << i);
        else if ((tem3 >> (i + 1)) & 1)
            x |= (1LL << i), y |= (1LL << i);
    }
    for (int i = 1; i < 30; i += 2) {
        if ((tem4 >> i) & 1)
            x |= (1LL << i);
        else if ((tem4 >> (i + 1)) & 1)
            x |= (1LL << i), y |= (1LL << i);
    }
    report2((x | m) + (y | m));
    return;
}

Find the Last Number

出处：CF2156D

题目大意：交互题。隐藏一个长度为 $n$ 的排列，只能询问前 $n-1$ 个位置与给定数的按位与是否为零，要求确定最后一个数。

数据范围： $1 \leq t \leq 10^3, 2 \leq n \leq 2 \cdot 10^4, \sum n \leq 2 \cdot 10^4$

思路：

 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
int ask(int l, int r) {
    cout << "? " << l << ' ' << r << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
void report(ll a) {
    cout << "! " << a << '\n';
    cout.flush();
}
void solve() {
    int n;
    cin >> n;
    vi tem;
    vi tem2;
    rep(i, 1, n) tem.push_back(i);
    rep(i, 1, n - 1) tem2.push_back(i);
    int ans = 0;
    int tot = 0;
    while ((1 << tot) <= n) tot++;
    rep(i, 0, tot - 1) {
        vi a0, a1;
        vi b0, b1;
        for (auto& p : tem2) {
            int tem3 = ask(p, (1 << i));
            if (tem3 == 0)
                a0.push_back(p);
            else
                a1.push_back(p);
        }
        for (auto& p : tem) {
            if (p & (1 << i))
                b1.push_back(p);
            else
                b0.push_back(p);
        }
        if (sz(a0) == sz(b0)) {
            ans |= (1 << i);
            tem = b1;
            tem2 = a1;
        } else {
            tem = b0;
            tem2 = a0;
        }
    }
    report(ans);
    return;
}

Modulo Sum

出处：CF577B

题目大意：给定数组 $a$ 和模数 $m$ ，判断是否存在非空子序列，其元素和能被 $m$ 整除。

数据范围： $1 \leq n \leq 10^6, 2 \leq m \leq 10^3, 0 \leq a_i \leq 10^9$

思路：

 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, m;
    cin >> n >> m;
    vi a(n);
    rep(i, 0, n - 1) {
        cin >> a[i];
        a[i] = a[i] % m;
    }
    if (n >= m) {
        cout << "YES" << endl;
        return;
    }
    vector<vector<bool>> dp(n, vector<bool>(m, false));
    rep(i, 0, n - 1) {
        dp[i][a[i]] = true;
        if (i == 0) continue;
        rep(j, 0, m - 1) {
            dp[i][j] = dp[i][j] | dp[i - 1][j];
            dp[i][(j + a[i]) % m] = dp[i][(j + a[i]) % m] | dp[i - 1][j];
        }
    }
    rep(i, 0, n - 1) {
        if (dp[i][0]) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
    return;
}

Imbalanced Array

出处：CF817D

题目大意：给定数组 $a$ ，求所有子数组的最大值与最小值之差的总和。

数据范围： $1 \leq n \leq 10^6, 1 \leq a_i \leq 10^6$

思路：

 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;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vi r1(n, n);
    vi l1(n, -1);
    vi r2(n, n);
    vi l2(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()) r1[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()) l1[i] = s.top();
        s.push(i);
    }  // 求左边第一个小于的下标
    while (!s.empty()) s.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[s.top()] <= a[i]) s.pop();
        if (!s.empty()) r2[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()) l2[i] = s.top();
        s.push(i);
    }  // 求左边第一个大于的下标
    while (!s.empty()) s.pop();
    ll maxx = 0;
    rep(i, 0, n - 1) { maxx += 1LL * a[i] * (i - l1[i]) * (r1[i] - i); }
    ll mixx = 0;
    rep(i, 0, n - 1) { mixx += 1LL * a[i] * (i - l2[i]) * (r2[i] - i); }
    cout << mixx - maxx << endl;
    return;
}

Bash and a Tough Math Puzzle

出处：CF914D

题目大意：维护数组，支持单点修改，并回答区间内是否能至多修改一个元素，使该区间的 $\gcd$ 变成给定值 $x$ 。

数据范围： $1 \leq n \leq 5 \cdot 10^5, 1 \leq a_i \leq 10^9, 1 \leq q \leq 4 \cdot 10^5, 1 \leq x,y \leq 10^9$

思路：

  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
template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return __gcd(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);
    }

    int cnt(int node, int l, int r, int ql, int qr, T x) const {
        if (r < ql || l > qr) return 0;
        if (ql <= l && r <= qr) {
            if (tree[node] % x == 0) return 0;
            if (l == r) return 1;
        }
        int m = (l + r) / 2;
        int res = cnt(node * 2, l, m, ql, qr, x);
        if (res > 1) return res;
        res += cnt(node * 2 + 1, m + 1, r, ql, qr, x);
        return res;
    }

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]中最后一个满足条件的下标

    int cnt(int ql, int qr, T x) const { return cnt(1, 0, n - 1, ql, qr, x); }
};
void solve() {
    int n, q, op, x, y, z;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    cin >> q;
    SegmentTree<ll> tree(a);
    rep(i, 0, q - 1) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            x--, y--;
            int tem = tree.cnt(x, y, z);
            if (tem <= 1)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        } else {
            cin >> x >> y;
            x--;
            tree.update(x, y);
        }
    }
    return;
}

Tufurama

出处：CF961E

题目大意：给定数组 $a$ ，统计满足 $i

数据范围： $1 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^9$

思路：

 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
template <typename T = long long>
class Tree {
    vector<T> tree;

public:
    // 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
    Tree(int n, T val = 0) : tree(n + 1) {
        for (int i = 1; i <= n; i++) {
            tree[i] += val;
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
    Tree(const vector<T>& data) {
        int n = data.size();
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            tree[i] += data[i - 1];  // data是 0-based
            int nxt = i + (i & -i);
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    // 单点修改：将 0-based 下标 i 处的元素增加 val
    void add(int i, T val = 1) {
        for (++i; i < tree.size(); i += i & (-i)) {
            tree[i] += val;
        }
    }

    // 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
    T pre(int i) const {
        T res = 0;
        for (++i; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }

    // 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
    T query(int l, int r) const {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);  // 当 l=0 时, pre(-1) 会合理地返回 0
    }

    // 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
    int lower_bound(T val) const {
        int w = bit_width(tree.size() - 1);
        int res = 0;
        T s = 0;
        for (int i = w - 1; i >= 0; i--) {
            int nxt = res + (1 << i);
            if (nxt < tree.size() && tree[nxt] + s < val) {
                res += (1 << i);
                s += tree[nxt];
            }
        }
        return res;  // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
    }
};
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    vvl queries(n);
    rep(i, 1, n - 1) queries[min(1LL * i - 1, a[i] - 1)].push_back(i);
    Tree tree(n + 1);
    rep(i, 0, n - 1) {
        tree.add(min(a[i], 1LL * n));
        if (queries[i].empty()) continue;
        for (auto& p : queries[i]) {
            ll tem = i + 1 - tree.query(0, p);
            ans += tem;
        }
    }
    cout << ans << endl;
    return;
}

Kilani and the Game

出处：CF1105D

题目大意：给定网格、障碍和多个玩家的扩张速度，模拟玩家轮流扩张领地，输出最终每个玩家占据的格子数。

数据范围： $1 \leq n,m \leq 1000, 1 \leq p \leq 9, 1 \leq s_i \leq 10^9$

思路：

 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
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
void solve() {
    int n, m, p;
    cin >> n >> m >> p;
    vi a(p);
    rep(i, 0, p - 1) cin >> a[i];
    vector<vector<char>> ma(n, vector<char>(m));
    queue<pii> q[p];
    vi res(p);
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            cin >> ma[i][j];
            if (ma[i][j] >= '1' && ma[i][j] <= '9') {
                q[ma[i][j] - '0' - 1].emplace(i, j);
                res[ma[i][j] - '0' - 1]++;
            }
        }
    }
    while (true) {
        bool flag = false;
        rep(i, 0, p - 1) {
            rep(j, 1, a[i]) {
                if (q[i].empty()) break;
                int tem = sz(q[i]);
                rep(v, 1, tem) {
                    auto [x, y] = q[i].front();
                    q[i].pop();
                    rep(l, 0, 3) {
                        int ax = x + dx[l], ay = y + dy[l];
                        if (ax < 0 || ax >= n || ay < 0 || ay >= m || ma[ax][ay] != '.') continue;
                        ma[ax][ay] = (char)('0' + i + 1);
                        res[i]++;
                        q[i].emplace(ax, ay);
                        flag = true;
                    }
                }
            }
        }
        if (!flag) break;
    }
    rep(i, 0, p - 1) cout << res[i] << ' ';
    cout << endl;
    return;
}

Beautiful Array

出处：CF1155D

题目大意：给定数组 $a$ 和整数 $x$ ，可以选择一个连续子段并将其中所有数乘以 $x$ ，求操作后最大子段和。

数据范围： $1 \leq n \leq 3 \cdot 10^5, -10^9 \leq x,a_i \leq 10^9$

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int n;
    ll x;
    cin >> n >> x;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    vvl dp(n, vl(3, LLONG_MIN / 2));
    dp[0][0] = a[0];
    dp[0][1] = x * a[0];
    ans = max({0LL, dp[0][0], dp[0][1]});
    rep(i, 1, n - 1) {
        dp[i][0] = max(dp[i - 1][0] + a[i], a[i]);
        dp[i][1] = max({dp[i - 1][0] + x * a[i], x * a[i], dp[i - 1][1] + x * a[i]});
        dp[i][2] = max(dp[i - 1][1] + a[i], dp[i - 1][2] + a[i]);
        ans = max({ans, dp[i][0], dp[i][1], dp[i][2]});
    }
    cout << ans << endl;
    return;
}

K-periodic Garland

出处：CF1353E

题目大意：给定 01 串和整数 $k$ ，每次可以翻转一个字符，求把它变成满足亮灯位置间隔为 $k$ 的最小操作数。

数据范围： $1 \leq t \leq 10^4, 1 \leq k \leq n \leq 10^6, \sum n \leq 10^6$

思路：

 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
void solve() {
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    ll ans = LLONG_MAX;
    vl pre(n + 1, 0);
    rep(i, 1, n) pre[i] = pre[i - 1] + (s[i - 1] == '1');
    vvl dp(n, vl(3));
    rep(i, 0, k - 1) {
        dp[i][0] = (s[i] == '1') + pre[i];
        dp[i][1] = (s[i] == '0') + pre[i];
        dp[i][2] = (s[i] == '1') + pre[i];
        for (int j = i; j <= n - 1; j += k) {
            if (j != i) {
                dp[j][0] = (s[j] == '1') + dp[j - k][0] + pre[j] - pre[j - k + 1];
                dp[j][1] = (s[j] == '0') + min(dp[j - k][0], dp[j - k][1]) + pre[j] - pre[j - k + 1];
                dp[j][2] = (s[j] == '1') + min(dp[j - k][1], dp[j - k][2]) + pre[j] - pre[j - k + 1];
            }
            if (j + k >= n) ans = min(ans, min({dp[j][0], dp[j][1], dp[j][2]}) + pre[n] - pre[j + 1]);
        }
    }
    cout << ans << endl;
    return;
}

Education

出处：CF1512F

题目大意：给定每天在各职位的收入、升职花费和电脑价格 $c$ ，求攒够买电脑所需的最少天数。

数据范围： $1 \leq t \leq 10^4, 1 \leq n \leq 2 \cdot 10^5, 1 \leq c \leq 10^9, 1 \leq a_i,b_i \leq 10^9, \sum n \leq 2 \cdot 10^5$

思路：

 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
void solve() {
    ll n, c;
    cin >> n >> c;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl b(n - 1);
    rep(i, 0, n - 2) cin >> b[i];
    ll tem = 0;
    vvl dp(n, vl(2, 0));
    dp[0][0] = (c + a[0] - 1) / a[0];
    dp[0][1] = (b[0] + a[0] - 1) / a[0] + 1;
    tem = (dp[0][1] - 1) * a[0] - b[0];
    ll ans = dp[0][0];
    rep(i, 1, n - 1) {
        dp[i][0] = dp[i - 1][1] + (c > tem ? (c - tem + a[i] - 1) / a[i] : 0);
        if (i < n - 1) {
            dp[i][1] = dp[i - 1][1] + (b[i] > tem ? (b[i] - tem + a[i] - 1) / a[i] : 0) + 1;
            ll tem2 = 0;
            if (b[i] > tem) tem2 = (b[i] - tem + a[i] - 1) / a[i];
            tem = tem + tem2 * a[i] - b[i];
        }
        ans = min(ans, dp[i][0]);
    }
    cout << ans << endl;
    return;
}

Vasilije Loves Number Theory

出处：CF1878F

题目大意：维护整数 $n$ ，支持乘上给定数以及恢复初始值，询问当前 $d(n)$ 是否整除 $n$ 。

数据范围： $1 \leq t \leq 100, 1 \leq n \leq 10^6, 1 \leq q \leq 1000, 1 \leq x \leq 10^6$

思路：

 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
constexpr int MX = 1e6 + 5;
int lpf[MX];
vi primes;
auto init = [] {
    for (int i = 2; i < MX; i++) {
        if (lpf[i] == 0) {
            lpf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (1LL * i * p >= MX) break;
            lpf[i * p] = p;
            if (p == lpf[i]) break;
        }
    }
    return 0;
}();

// 支持分解 <= 1e9 的数，返回 pair<素因子, 指数>
vector<pair<ll, int>> cnt(ll x) {
    vector<pair<ll, int>> res;
    for (int p : primes) {
        if (1LL * p * p > x) break;
        if (x % p == 0) {
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            res.emplace_back(p, e);
        }
    }
    if (x > 1) {
        res.emplace_back(x, 1);
    }
    return res;
}
void solve() {
    ll n, q, op, sn, x;
    cin >> n >> q;
    map<ll, ll> ma;
    map<ll, ll> ma2;
    ll tem = 1;
    auto tem2 = cnt(n);
    for (auto& [x, y] : tem2) {
        ma[x] += y;
        tem *= (y + 1);
    }
    ma2 = ma;
    ll tem3 = tem;
    auto check = [&](ll x) -> bool {
        auto tem2 = cnt(x);
        for (auto& [a, b] : tem2) {
            if (ma[a] < b) return false;
        }
        return true;
    };
    rep(i, 0, q - 1) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            auto tem2 = cnt(x);
            for (auto& [a, b] : tem2) {
                tem = tem / (ma[a] + 1) * (ma[a] + b + 1);
                ma[a] += b;
            }
            bool flag = check(tem);
            cout << (flag ? "YES" : "NO") << endl;
        } else {
            ma = ma2;
            tem = tem3;
        }
    }
    cout << endl;
    return;
}

Time Travel

出处：CF1887B

题目大意：给定按时间分组出现的无向边和一串允许使用的时间编号，求从 $1$ 到 $n$ 最早需要读到序列中的哪个位置。

数据范围： $2 \leq n \leq 2 \cdot 10^5, 1 \leq t \leq 2 \cdot 10^5, 1 \leq k \leq 2 \cdot 10^5, \sum l_i \leq 2 \cdot 10^5$

思路：

 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, t, l, x, y, k;
    cin >> n >> t;
    vector<vector<pii>> ma(n);
    vvi tem(t);
    rep(i, 0, t - 1) {
        cin >> l;
        rep(j, 0, l - 1) {
            cin >> x >> y;
            ma[x - 1].emplace_back(y - 1, i);
            ma[y - 1].emplace_back(x - 1, i);
        }
    }
    cin >> k;
    vi a(k + 1);
    rep(i, 1, k) {
        cin >> a[i];
        tem[a[i] - 1].push_back(i);
    }
    priority_queue<pii, vector<pii>, greater<>> q;
    vi dis(n, INT_MAX);
    dis[0] = 0;
    q.emplace(0, 0);
    while (!q.empty()) {
        auto [d, node] = q.top();
        q.pop();
        if (d > dis[node]) continue;
        for (auto& [y, z] : ma[node]) {
            if (tem[z].empty()) continue;
            auto x = ranges::upper_bound(tem[z], d);
            if (x == tem[z].end()) continue;
            int new_y = *x;
            if (dis[y] > new_y) {
                dis[y] = new_y;
                q.emplace(new_y, y);
            }
        }
    }
    cout << (dis[n - 1] == INT_MAX ? -1 : dis[n - 1]) << endl;
    return;
}