Martian148's blog
martian148
2024-09-19
目录

Sakura Tears training 4

# Sakura Tears training #4

# A - Firefly's Queries

# Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;

void solve() {
    int n; cin >> n; int m; cin >> m;
    vector<ll> a(n), s(2 * n);
    for (int i = 0; i < n; i++) cin >> a[i];
    s[0] = a[0];
    for (int i = 1; i < n; i++) s[i] = s[i - 1] + a[i];
    for (int i = n; i < 2 * n; i++) s[i] = s[i - 1] + a[i - n];

    auto calc = [&] (int x) -> ll {
        if (x == -1) return 0;
        int cnt = (x + 1) / n;
        int rem = (x + 1) % n;
        ll ret = 0;
        ret += cnt * s[n - 1];
        ret += s[cnt + rem - 1] - (cnt - 1 < 0 ? 0 : s[cnt - 1]);
        return ret;
    };

    while (m--) {
        int l, r; cin >> l >> r; l--; r--;
        cout << calc(r) - calc(l - 1) << '\n';
    }
}

signed main() {
    freopen ("A.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 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

# B - Sakurako's Task

# Question

CF2008G Sakurako's Task (opens new window)

给定一个长度为 nn 的数组 {a}\{a\}，可以进行无数次下列操作：

  • 选择任意一个 i,j(i≠j)i,j\ (i \ne j)，然后令 ai=ai+aja_i=a_i+a_j 或 ai=ai−aja_i=a_i-a_j

求，要求操作后的 mexkmex_k 最大

# Solution

想要 mexkmex_k 最大，那么肯定让 aia_i 越小越好，根据裴蜀定理，令 gg 为数组中数的 gcd⁡\gcd ，最后 aia_i 的值肯定是 0,g,2g,3g,⋯0,g,2g,3g,\cdots

所以 mexkmex_k 就是其中的空位，可以用二分求得最后的答案，二分枚举一个答案 xx，那么被占的位置的个数就是 min⁡(n,x/g+1)\min(n, x/g+1)，没有被占领的位置就是 x−min⁡(n,x/g+1)x-\min(n, x/g+1) ，如果没有被占领的位置大于等于 k−1k-1 个，说明 check 成功

# Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long

void solve() {
    int n, k; cin >> n >> k;
    int g = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        g = __gcd(g, x);
    }

    if (n == 1) {
        cout << (k <= g ? k - 1 : k) << '\n';
        return ;
    }

    ll L = -1, R = 1e18;
    
    auto check = [&] (ll x) -> bool {
        ll cnt = 0;
        ll num = x / g + 1;
        cnt = x - min(n, num);
        return cnt >= k - 1;
    };


    while (L + 1 < R) {
        ll mid = (L + R) >> 1;
        if (check(mid)) R = mid;
        else L = mid;
    }
    cout << R << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 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

# C - Yunli's Subarray Queries (easy version)

# Question

Yunli's Subarray Queries (easy version) (opens new window)

给定一个长度为 nn 的数组 bb，定义一个操作为：

  • 令一个 bi=xb_i=x，xx 为任意整数

记 f(b)f(b) 为需要执行最少次数，使得 bb 中至少存在长度为 kk 的连续子数组

# Solution

这个好像是 easy 版，没什么思维难度

连续子数组的管用套路，定义 ci=bi−ic_i=b_i-i

所以从 [i,i+k−1][i,i+k-1] 里面 cic_i 相同的值就能满足一个公差为 11 的等差数列

所以需要维护 [i,i+k−1][i,i+k-1] 里面 cic_i 众数的个数，用一个滑动窗口 + 优先队列来维护即可

# Code

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef long long ll;

void solve() {
    int n, k, q; cin >> n >> k >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<ll> ans(n + 1);
    vector<ll> b(n + 1);

    for (int i = 1; i <= n; i++) b[i] = a[i] - i;

    map<int, int> mp;
    priority_queue<pair<int, int>> pq;
    
    auto in = [&] (int x) {
        if (mp.find(x) == mp.end()) mp[x] = 1;
        else mp[x]++;
        pq.push({mp[x], x});
    };

    auto del = [&] (int x) {
        if (mp.find(x) == mp.end()) return ;
        if (mp[x] == 1) mp.erase(x);
        else mp[x]--, pq.push({mp[x], x});
    };


    auto get_max = [&] () -> int {
        while (mp[pq.top().second] != pq.top().first) pq.pop();
        return pq.top().first;
    };
    
    for (int i = 1; i <= k; i++) in(b[i]);
    ans[1] = k - get_max();

    for (int i = 2; i + k - 1 <= n; i++) {
        del(b[i - 1]);
        in(b[i + k - 1]);
        ans[i] = k - get_max();
    }

    while (q--) {
        int l, r; cin >> l >> r;
        cout << ans[l] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 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
48
49
50
51
52
53
54
55
56
57

# D - Sakurako's Test

# Question

给定一个数组 {a}\{a\} ，一共有 qq 次询问，每次询问给出一个 xx，可以执行以下操作任意次

  • 若 ai≥xa_i\ge x ，ai=ai−xa_i=a_i-x

每次询问求当前 xx 下，序列的中位数最小是多少

# Solution

看到中位数就心酸

显然需要中位数最小，肯定是能减就减，所以最后 aia_i 肯定会变成 aimodxa_i\bmod{x}

先固定一个 xx ，如果直接去暴力计算会超时，考虑二分最后的答案 midmid，那么 [0,mid],[x,x+mid],[2x,2x+mid]⋯[0,mid],[x,x+mid],[2x,2x+mid]\cdots 都是最后小于中位数的数

由于值域不是很大，这个部分可以用值域前缀和在 O(max⁡{a}x)O(\frac{\max\{a\}}{x}) 的时间复杂度内求出

每次去求 xx 在 xx 都非常小时会超时，所以记录 ansxans_x 为答案，最后询问的时候 O(1)O(1) 回答就好了

# Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, q; cin >> n >> q;
    vector<int> s(n + 1,0);
    int m = -1;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x; m = max(m, x);
        s[x] += 1;
    }
    for (int i = 1; i <= n; i++) s[i] += s[i - 1];

    auto check = [&] (int x, int mid) -> bool {
        int ret = 0;
        for (int l = 0; l <= m; l += x) {
            int r = min(m, l + mid);
            ret += s[r] - (l == 0 ? 0 : s[l - 1]);
        }
        return ret >= n / 2 + 1;
    };

    vector<int> ans(n + 1);
    for (int x = 1; x <= n; x++) {
        int l = -1, r = x;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (check(x, mid)) r = mid;
            else l = mid;
        }
        ans[x] = r;
    }

    while (q--) {
        int x; cin >> x;
        cout << ans[x] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 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

# Summary

  • 中位数，考虑二分中位数，然后去 check 小于 mid 的个数
  • 多次询问一个答案可以记录下，然后 O(1)O(1) 回答

# E - Determine Winning Islands in Race

# Question

CF1998D Determine Winning Islands in Race (opens new window)

Elsie 和 Bessie 在一个 nn 个岛屿上比赛，有 n−1n-1 条主要桥梁，第 ii 条链接 ii 和 i+1i+1

有 mm 条备用桥梁，第 ii 条链接 uiu_i 和 viv_i

Bessie 从 11 岛屿出发，能用主要桥梁和备用桥梁，Elsie 从 ss 岛屿出发，只能走主要桥梁

当一个奶牛从一个岛屿 ii 离开时，岛屿 ii 崩塌，求谁能先到达 nn 岛屿

# Solution

Elsie 从 ss 出发，一路是 s+1,s+2,s+3,⋯s+1,s+2,s+3,\cdots

所以 Bessie 只能通过备用桥梁超过 Elsie

先预处理出 dis[x]dis[x] 表示 11 到 xx 的最短路

对于一个 u→vu\rightarrow v 的备用桥梁，如果 Elsie 的起点在 [u+1,v−(dis[v]+1)−1][u+1,v-(dis[v]+1)-1]，那么 Bessie 可以通过这座桥梁超过 Elsie

如果不存在一个桥梁能超过，那么就 Elsie 赢了

多个区间取并集可以用线段树，或者构造差分数组来求

# Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 0x3f3f3f3f;

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<pair<int, int>> e;
    vector<int> dis(n + 1, INF);
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        e.push_back({u, v});
    }
    for (int i = 1; i + 1 <= n; i++) {
        g[i].push_back(i + 1);
    }
    dis[1] = 0; queue<int> q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : g[u]) {
            if (dis[v] == INF) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }

    vector<int> pre(n + 10, 0);
    for (auto [u, v] : e) {
        int l = u + 1, r = v - dis[u] - 1 - 1;
        if (l > r) continue;
        pre[l]++; pre[r + 1]--;
    }

    int now = 0;
    for (int i = 1; i < n; i++) {
        now += pre[i];
        cout << (now == 0 ? "1" : "0");
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 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
48
49
50
51

# F - Level Up

# Question

CF1997E Level Up (opens new window)

Monocarp 从等级 11 开始游戏。他即将与 nn 只怪物进行战斗，按照从 11 到 nn 的顺序。第 ii 只怪物的等级为 aia_i

对于给定顺序中的每只怪物，Monocarp 的遭遇如下：

  • 如果 Monocarp 的等级严格高于怪物的等级，则怪物会逃跑；
  • 否则，Monocarp 会与怪物战斗。

在每次与怪物战斗 kk 次后，Monocarp 的等级会增加11

给出 qq 个查询

  • ixi~x：如果参数kk等于 xx ，Monocarp 是否会与第ii只怪物战斗（或者这只怪物会逃跑）

# Solution

法一: 根号分治

可以说，根号分治非常强大

首先，肯定要把询问离线下来，按照 kk 分组

对于一个 kk 如果 k≤Bk \le B 那么直接暴力跑就好了

如果 k>Bk>B，那么总的等级数不会超过 nB\frac{n}{B}，我们可以开 nB\frac{n}{B} 个前缀和 pre[j][i]pre[j][i] 表示 表示前 ii 个数中大于 jj 的数的个数

那么对于每个询问，假设我们现在的位置是 pospos，等级为 nownow，那么我们下一个升级的位置就是 第一个满足 pre[j][i]>=pre[now][pos]+kpre[j][i]>=pre[now][pos]+k 的位置，显然可以二分得出，这部分的时间复杂度是个调和计数，大约为 O(nlog⁡2n)O(n\log^2n)

取 B=1000B=1000 可以通过此题

# Code

#include <bits/stdc++.h>
using namespace std;

constexpr int M = 300, B = 1000;

void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> pre(M, vector<int>(n + 1, 0)); // pre[j][i] 表示前 i 个数中大于 j 的数的个数
    for (int j = 0; j < M; j++)
        for (int i = 1; i <= n; i++) 
            pre[j][i] = pre[j][i - 1] + (a[i] > j); 
    
    vector<vector<pair<int, int>>> ask(n + 1);
    vector<int> ans(q + 1, 0);
    for (int i = 1; i <= q; i++) {
        int id, k; cin >> id >> k;
        ask[k].push_back({id, i});
    }

    for (int k = 1; k <= n; k++) {
        if (ask[k].empty()) continue;
        sort(ask[k].begin(), ask[k].end());

        if (k <= B) {
            int now = 1, cnt = 0, it = 0;
            for (int i = 1; i <= n; i++) {
                while (it < ask[k].size() && ask[k][it].first == i) {
                    ans[ask[k][it].second] = a[i] >= now;
                    ++it;
                }
                if (a[i] >= now && ++cnt == k) ++now, cnt = 0;
            }
        }
        else {
            int pos = 0, now = 0, it = 0;
            while (pos <= n) {
                pos = lower_bound(pre[now].begin(), pre[now].end(), pre[now][pos] + k) - pre[now].begin();
                // 跳到第一个大于 pre[now][pos] + k 的位置
                now += 1;
                while (it < ask[k].size() && ask[k][it].first <= pos) {
                    ans[ask[k][it].second] = a[ask[k][it].first] >= now;
                    ++it;
                }
            }
        }
    }

    for (int i = 1; i <= q; i++) cout << (ans[i] ? "YES" : "NO") << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    int T; T = 1;
    while (T--) solve();
    return 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
48
49
50
51
52
53
54
55
56
57
58

# G - Penacony

# Question

CF1996G Penacony (opens new window)

有 nn 个房屋和 nn 条道路，形成一个环，所有道路都是双向的

存在 mm 对友谊关系，a,ba,b ，需要保证 a,ba,b 之间需要存在一条路径

求最小维护的道路数量

# Solution

一眼异或哈希

对于一个路径 a,ba,b，需要让 a→ba\rightarrow b 被标上一个记号，b→n→1→ab\rightarrow n\rightarrow 1\rightarrow a 标记上另外一个记号

所以只需要把 a,ba,b 点异或上一个相同的随机数即可

为了防止撞，我还写了一个双哈希

# Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    srand(20040318);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        vector<int> a(n + 1, 0), b(n + 1, 0);
        for (int i = 1; i <= m; i++) {
            int u, v; cin >> u >> v;
            int hsh1 = rand() * rand(), hsh2 = rand() * rand();
            a[u] ^= hsh1; a[v] ^= hsh1;
            b[u] ^= hsh2; b[v] ^= hsh2;
        }
        map<pair<int, int>, int> mp;
        int now1 = 0, ans = 0, now2 = 0;
        for (int i = 1; i <= n; i++) {
            now1 ^= a[i]; now2 ^= b[i];
            mp[{now1, now2}] += 1;
            ans = max(ans, mp[{now1, now2}]);
        }
        cout << n - ans << '\n';
    }
    return 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
上次更新: 2024/10/30, 18:42:16
【2024暑#110】ACM暑期第五次测验（个人赛）
Sakura Tears training 5

← Sakura Tears training 5→

最近更新
01
逻辑学
12-13
02
中华传统文化
12-12
03
欧拉回路
11-14
更多文章>
Theme by Vdoing | Copyright © 2024-2024 Martian148 | MIT License