Educational Codeforces Round 175 (Rated for Div.2)

Edu175

nuo534202

978人浏览 · 2025-03-05 20:31:53

nuo534202 · 2025-03-05 20:31:53 发布

比赛链接：Edu175

A. FizzBuzz Remixed

因为 $\% 3 = i \% 5$ ，所以 $i = 15 k$ ， $i = 15 k + 1$ ，或者 $i = 15 k + 2$ ( $\in N$ )。

时间复杂度： $O (1)$ 。

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

void solve() {
    int n;
    cin >> n;
    int num = n / 15, ans = 3 * num;
    int res = min(3, n - num * 15 + 1);
    cout << ans + res << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

B. Robot Program

$R$ 是右移，位置坐标 $+ 1$ ； $L$ 是左移，位置坐标 $- 1$ 。维护一个前缀和，首先找到一个 $pre_i + x = 0$ ，的位置记录花费的时间，再找到第一个 $pre_i = 0$ 的位置，计算剩余时间能走回多少次原点。如果找不到 $pre_i + x = 0$ 的位置，或者需要花费的时间 $i$ 大于 $k$ ，那么输出 $- 1$ 。

时间复杂度： $O (n)$ 。

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

#define int long long

const int N = 2e5 + 10;
int pre[N];

void solve() {
    int n, x, k; string s;
    cin >> n >> x >> k >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
        if (s[i] == 'L') pre[i] = pre[i - 1] - 1;
        else pre[i] = pre[i - 1] + 1;
    int num = -1;
    for (int i = 1; i <= n; i++)
        if (pre[i] + x == 0) {
            num = i;
            break;
        }
    int tot = -1;
    for (int i = 1; i <= n; i++)
        if (pre[i] == 0) {
            tot = i;
            break;
        }
    if (num == -1 || k < num) {
        cout << 0 << '\n';
        return;
    }
    k -= num;
    int ans = 1;
    if (tot != -1) ans += k / tot;
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

C. Limited Repainting

可以发现 $p e na lt y$ 满足单调性，所以可以二分 $p e na lt y$ ，再去这个 $p e na lt y$ 检查是不是合法的。

检查的实现：

如果 $s_i = B$ 且 $a_i > mid$ ，那么这个位置一定要画成蓝色。
如果 $s_i = R$ 且 $a_i > mid$ ，那么这个位置一定不能画成蓝色。

时间复杂度： $O(n\log A)$ ( $A$ 代表 $a_i$ 的最大值)。

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

const int N = 3e5 + 10;
int n, k, a[N];
string s;

bool check(int mid) {
    int num = 0, l = 1, r = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'R' && a[i] > mid) {
            if (l <= r) num++;
            l = i + 1, r = i;
        }
        if (s[i] == 'B' && a[i] > mid) {
            r = i;
        }
    }
    num += (l <= r);
    return num <= k;
}

void solve() {
    cin >> n >> k >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

D. Tree Jumps

设 $dp_i$ 是以 $i$ 节点结尾的路径数量，记 $tot_i$ 表示上一层所有节点的方案数， $u_i$ 是 $i$ 节点的父节点，转移方程为 $dp_i = tot_i - dp_{u_i}$ 。最后的结果为 $\sum_{i = 1}^n dp_i$ 。

时间复杂度： $O (n)$ 。

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

#define int long long

const int N = 3e5 + 10, mod = 998244353;
int n, d[N], head[N], sum[N], tot[N], f[N], num = 0;
struct edge { int to, nxt; } e[N];

void addEdge(int u, int v) { e[++num] = (edge){ v, head[u]}, head[u] = num; }

void bfs(int x) {
    queue<int> q;
    q.push(x);
    d[x] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= num; i++) e[i] = { 0, 0 };
    num = 0;
    for (int i = 1; i <= n; i++) head[i] = 0;
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        addEdge(p, i);
        sum[i] = f[i] = tot[i] = 0;
    }
    bfs(1);
    for (int i = 1; i <= n; i++) sum[d[i]]++;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 1 || d[i] == 2) f[i] = 1;
        if (d[i] == 2) q.push(i);
        tot[d[i]] += f[i];
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            f[v] = (tot[d[u]] - f[u]) % mod;
            tot[d[v]] += f[v];
            q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + f[i]) % mod;
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

E. Game with Binary String

对于第二个玩家，最优的操作是在剩余字符串还有 $0$ 的时候，选 $01$ ，否则选 $11$ 。所以当两个玩家刚好能一人选一次到游戏结束时，子串中一定满足 $num_0 = 3 \cdot num_1$ 。

当 $num_0 \ge 3 \cdot num_1 + 2$ 时，玩家一能在两人一人选一次后多选一次，玩家一获胜。
当 $num_0 < 3 \cdot num_1 + 2$ 时，
- 当 $num_0 = 3 \cdot num_1 - 1$ 时，在倒数第二轮选完之后，刚好只剩下两个 $0$ 、一个 $1$ 。玩家一获胜。
- 剩余其他情况下，带倒数第二轮选完之后会剩下两个 $0$ 和若干个 $1$ ，玩家二获胜。

玩家一获胜的数量就是所有满足的 $num_0 - 3 \cdot num_1 \ge 2$ 或 $num_0 - 3 \cdot num_1 = -1$ 的子串数量。

设 $sum_i$ 表示前 $i$ 位的 $num_0 - 3 \cdot num_1$ ，所有以第 $i$ 位结尾的子串中，玩家一获胜的数量为满足 $\le j < i$ 且 $sum_j \le sum_i - 2$ 或 $sum_j = sum_i + 1$ 的 $j$ 的数量（满足 $sum_i - sum_j \ge 2$ 或 $sum_i - sum_j = -1$ ，其中 $sum_i - sum_j$ 表示的是 $(j, i]$ 的子串中的 $num_0 - 3 \cdot num_1$ ）。最后利用树状数组维护前 $i$ 位的 $s u m$ 的数量和即可。

时间复杂度： $\log n)$ 。

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

using ll = long long;

const int SIZE = 3e6 + 10, N = 15e5; // N 是偏移量，防止结果小于 0
int n, t[SIZE];
string s;

void add(int x, int k) {
    while (x <= 2 * N) {
        t[x] += k;
        x += (x & (-x));
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += t[x];
        x -= (x & (-x));
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> s;
    s = " " + s;
    int sum = 0;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        add(sum + N, 1);
        if (s[i] == '0') sum++;
        else sum -= 3;
        ans += query(sum + N + 1) - query(sum + N) + query(sum + N - 2);
    }
    cout << ans << endl;
    return 0;
}