Featured image of post Codeforces Round #1046(Div.2)

Codeforces Round #1046(Div.2)

B

题目大意：给定一个长度为 $n$ 的二进制字符串 $s$，以及一个整数 $k$。Aquawave 想要构造一个长度为 $n$ 的排列 $p$，使得对于所有 $1 \le i \le n$ 且 $s_i = \mathtt{1}$ 的下标 $i$，满足如下条件： - 对于每一个长度不少于 $k$ 的区间 $[l, r]$（即 $r - l + 1 \geq k$）且覆盖位置 $i$（即 $l \leq i \leq r$），该区间内的最大元素 $p_l, p_{l+1}, \ldots, p_r$ 中，最大值不能等于 $p_i$。注意，对于 $s_i = \mathtt{0}$ 的下标 $i$ 没有上述限制。需要找出这样一个排列，或者判断不存在这样的排列。

数据范围：$1 \le t \le 10^4$，$1 \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq n$，$\sum n \le 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

using i128 = __int128_t;
void solve() {
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int maxx = 0;
    int i = 0;
    while (i <= n - 1) {
        if (s[i] == '1') {
            int j = i;
            while (j <= n - 1 && s[j] == '1') j++;
            if (j - i >= k) {
                cout << "NO" << endl;
                return;
            }
            i = j;
        } else
            i++;
    }
    cout << "YES" << endl;
    vl res(n);
    vl tem;
    rep(i, 0, n - 1) {
        if (s[i] != '1') tem.push_back(i);
    }
    int las = n;
    for (auto& p : tem) res[p] = las--;
    rep(i, 0, n - 1) {
        if (!res[i]) res[i] = las--;
    }
    rep(i, 0, n - 1) cout << res[i] << ' ';
    cout << endl;
    return;
}

C

题目大意：我们定义一个“块”为一个数组，其中所有元素均等于该数组的长度。如果一个数组可以通过任意多个块（可以为零个块）的拼接得到，则称该数组为“整洁的”。注意，空数组也视为整洁的。给定一个由 $n$ 个整数构成的数组 $a$。需要求出其最长整洁子序列的长度$^{\text{∗}}$。

数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 2\cdot10^5$，$1 \leq a_i \leq n$，$\sum n \le 2\cdot10^5$。

思路：

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

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vl a(n + 1);
    rep(i, 1, n) cin >> a[i];
    vl dp(n + 1);
    vector<deque<int>> q(n + 1);
    ll ans = 0;
    rep(i, 1, n) {
        dp[i] = dp[i - 1];
        q[a[i]].push_back(i);
        while (sz(q[a[i]]) > a[i]) {
            q[a[i]].pop_front();
        }
        if (sz(q[a[i]]) == a[i]) {
            dp[i] = max(dp[i], dp[q[a[i]].front() - 1] + a[i]);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return;
}

D

题目大意：本题为交互题。RiOI 团队正在举办一场机器人锦标赛！这一次，你的机器人被传送到一个无限的二维平面上（存在笛卡尔坐标系）。在平面上有 $n$ 个锚点，第 $i$ 个锚点的坐标为 $(x_i, y_i)$，其中 $-10^9 \le x_i, y_i \le 10^9$。当机器人被传送到平面后，评测程序会立即告知你这些锚点坐标。然而，机器人一开始并不知道自己的初始坐标。为了测试机器人的智商，RiOI 团队设计了一个有趣的游戏。你的机器人需要通过以下操作，找出其初始坐标 $(X, Y)$，其中 $-10^9 \le X, Y \le 10^9$。

数据范围：$1 \le t \le 100$，$1 \le n \le 100$，$-10^9 \le x_i, y_i \le 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

char dx[4] = {'U', 'L', 'D', 'R'};
ll ask(ll l, ll r) {
    cout << "? " << dx[l] << ' ' << r << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
void report(ll a, ll b) {
    cout << "! " << a << ' ' << b << ' ' << '\n';
    cout.flush();
}
void solve() {
    ll n;
    cin >> n;
    vector<pll> ma(n);
    ll maxx1 = LLONG_MIN, maxx2 = LLONG_MIN;
    rep(i, 0, n - 1) {
        cin >> ma[i].first >> ma[i].second;
        maxx1 = max(maxx1, ma[i].first + ma[i].second);
        maxx2 = max(maxx2, ma[i].second - ma[i].first);
    }
    const ll INF = 1e9;
    ll op = ask(0, INF);
    op = ask(0, INF);
    op = ask(3, INF);
    op = ask(3, INF);
    ll op2 = ask(1, INF);
    op2 = ask(1, INF);
    op2 = ask(1, INF);
    op2 = ask(1, INF);
    ll x, y;
    x = (op + maxx1 - op2 - maxx2) / 2, y = (op + op2 + maxx1 + maxx2 - 8LL * INF) / 2;
    report(x, y);
    return;
}

E

题目大意：给定一个无向连通图，包含 $n$ 个顶点，第 $i$ 个顶点的权值为 $v_i$。我们定义一条简单路径 $l_1, l_2, \ldots, l_m$ 的值为 $v_{l_1} \oplus v_{l_2} \oplus \cdots \oplus v_{l_m}$。我们称图是“平衡”的，当且仅当： - 对于任意 $1 \le p < q \le n$，所有从 $p$ 到 $q$ 的简单路径的值都相同。Aquawave 给你一个包含 $n$ 个顶点 $m$ 条边的无向连通图，每个顶点 $i$ 的权值为 $a_i$。但部分权值未知，以 $-1$ 表示。

数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$n-1 \le m \le \min\left(\frac{n(n-1)}{2}, 4 \cdot 10^5\right)$，$1 \le V \le 10^9$，$-1 \le a_i \le V-1$，$1 \le u, v \le n$，$\sum n \le 2 \cdot 10^5$，$\sum m \le 4 \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
 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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

const ll MOD = 998244353;
// 边双连通分量 Edge-BCC，无向图，点 0-based
struct EBCC {
    int n, m, tim, tot;
    vector<vector<pii>> g;  // {to, edge_id}
    vector<pii> edges;      // edges[id] = {u, v}
    vi dfn, low, is_bridge, bel;
    vvi comps;  // comps[i] 是第 i 个边双里的点

    EBCC(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        m = tim = tot = 0;
        g.assign(n, vector<pii>());
        edges.clear();
        dfn.assign(n, 0);
        low.assign(n, 0);
        is_bridge.clear();
        bel.assign(n, -1);
        comps.clear();
    }

    int add_edge(int u, int v) {
        edges.push_back({u, v});
        is_bridge.push_back(0);
        g[u].push_back({v, m});
        g[v].push_back({u, m});
        return m++;
    }

    void tarjan(int u, int pe) {
        dfn[u] = low[u] = ++tim;
        for (int i = 0; i < sz(g[u]); i++) {
            int v = g[u][i].first;
            int id = g[u][i].second;
            if (id == pe) continue;
            if (!dfn[v]) {
                tarjan(v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) is_bridge[id] = 1;
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }

    void dfs_comp(int u) {
        bel[u] = tot;
        comps.back().push_back(u);
        for (int i = 0; i < sz(g[u]); i++) {
            int v = g[u][i].first;
            int id = g[u][i].second;
            if (bel[v] != -1 || is_bridge[id]) continue;
            dfs_comp(v);
        }
    }

    vi work() {
        rep(i, 0, n - 1) {
            if (!dfn[i]) tarjan(i, -1);
        }
        rep(i, 0, n - 1) {
            if (bel[i] == -1) {
                comps.push_back(vi());
                dfs_comp(i);
                tot++;
            }
        }
        return bel;
    }

    // 建桥树，要求先 work()
    vvi build_tree() {
        vvi tree(tot);
        rep(id, 0, m - 1) {
            if (!is_bridge[id]) continue;
            int a = bel[edges[id].first];
            int b = bel[edges[id].second];
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        return tree;
    }
};

// 用法：
// EBCC ebcc(n);
// int id = ebcc.add_edge(u, v); // 无向边，id 是边编号
// vi bel = ebcc.work();         // bel[u] 是 u 所在边双编号
// ebcc.is_bridge[id];           // 这条边是否为桥
// ebcc.comps;                   // 每个边双的点集
// vvi tree = ebcc.build_tree(); // 桥树
// 注意：重边不会被误判成桥，因为每条无向边都有独立 edge_id。
void solve() {
    ll n, m, lim, x, y;
    cin >> n >> m >> lim;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    EBCC ebcc(n);
    vvl ma(n);
    rep(i, 0, m - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
        ebcc.add_edge(x - 1, y - 1);
    }
    ebcc.work();
    ll ans = 1;
    vl vis(n);
    rep(i, 0, ebcc.tot - 1) {
        ll tem = -1;
        for (auto& p : ebcc.comps[i]) {
            if (a[p] == -1) continue;
            if (tem == -1 || (a[p] == tem))
                tem = a[p];
            else {
                cout << 0 << endl;
                return;
            }
        }
        auto dfs = [&](this auto&& dfs, int x, int c) -> bool {
            vis[x] = c;
            for (auto& [p, q] : ebcc.g[x]) {
                if (ebcc.is_bridge[q]) continue;
                if (vis[p] == c || (vis[p] == 0 && !dfs(p, 3 - c))) return false;
            }
            return true;
        };
        bool flag = dfs(ebcc.comps[i][0], 1);
        if (!flag && (tem != 0 && tem != -1)) {
            cout << 0 << endl;
            return;
        }
        if (flag && tem == -1) ans = ans * lim % MOD;
    }
    cout << ans << endl;
    return;
}

F1

题目大意：这是该问题的简单版本。不同版本的区别在于，本版本中对于所有询问中所有文章长度之和没有限制。只有在你解决了该问题所有版本后，才能进行 hack。这是一个交互式问题。RiOI 团队最近开发了一款名为 RiOI Editor 的文本编辑器。该编辑器只包含一个整数参数 $W$ —— 每一行的宽度。已知 $1 \leq W \leq 10^5$。由于你无法理解 RiOI 语言，因此在你看来，不同的单词只在于其长度的不同。因此，一篇长度为 $n$ 的文章被定义为一个序列 $a$，包含 $n$ 个正整数，$a_i$ 表示第 $i$ 个单词的长度。

数据范围：$1 \leq t \leq 10$。

思路：

 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

ll ask(ll k, vl& res) {
    cout << "? " << k << ' ';
    rep(i, 0, k - 1) cout << res[i] << ' ';
    cout << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
void report(ll a) {
    cout << "! " << a << '\n';
    cout.flush();
}
void solve() {
    vl tem;
    rep(i, 1, 100000) tem.push_back(1);
    ll op = ask(sz(tem), tem);
    if (op == 1) {
        report(100000);
        return;
    }
    ll l = (100000 + op - 1) / op, r = 99999 / (op - 1);
    vl tem2;
    rep(i, 1, r - l + 1) {
        tem2.push_back(l);
        tem2.push_back(i);
    }
    ll op2 = ask(sz(tem2), tem2);
    ll res = l + 2 * (r - l + 1) - op2;
    report(res);
    return;
}

F2

题目大意：这是该问题的高难度版本。两种版本的区别在于，在本版本中，所有询问中所有文章的长度之和不得超过 $2.5\cdot 10^4$。你只有在解决了该问题的所有版本后才能进行 hack。这是一个交互题。RiOI 团队最近开发了一个名为 RiOI Editor 的文本编辑器。该编辑器只有一个整数参数 $W$ —— 每行的宽度。已知 $1 \leq W \leq 10^5$。由于你无法理解 RiOI 语言，在你看来，单词之间唯一的区别就是它们的长度。因此，长度为 $n$ 的一篇文章被定义为一个长度为 $n$ 的序列 $a$，其中 $a_i$ 表示第 $i$ 个单词的长度。

数据范围：$1 \le t \le 10$。

思路：

 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

ll ask(ll k, vl& res) {
    cout << "? " << k << ' ';
    rep(i, 0, k - 1) cout << res[i] << ' ';
    cout << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
void report(ll a) {
    cout << "! " << a << '\n';
    cout.flush();
}
void solve() {
    vl tem;
    ll B = 125, N = 8108;
    rep(i, 1, N) tem.push_back(B);
    ll op = ask(sz(tem), tem);
    if (op == 0) {
        vl tem2;
        rep(i, 1, B * B) tem2.push_back(1);
        ll op2 = ask(sz(tem2), tem2);
        ll res = (B * B - 1) / (op2 - 1);
        report(res);
        return;
    } else {
        ll l = (N + op - 1) / op * B, r = min(((N - 1) / (op - 1) + 1) * B - 1, 100000LL);
        vl tem2;
        rep(i, 1, r - l + 1) {
            tem2.push_back(l);
            tem2.push_back(i);
        }
        ll op2 = ask(sz(tem2), tem2);
        ll res = l + 2 * (r - l + 1) - op2;
        report(res);
    }
    return;
}