Educational Codeforces Round 162 (Rated for Div. 2)

比赛链接

A

[Codeforces 1923A] Moving Chips.cpp >folded

#include <bits/stdc++.h>
// #define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int a[N];
void solve()
{
    int n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    int p = 1, q = n, ans = 0;
    while (p <= n and a[p] != 1) p++;
    while (q >= 1 and a[q] != 1) q--;
    for (int i = p; i <= q; i++) ans += a[i] == 0;
    cout << ans << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

B

[Codeforces 1923B] Monsters Attack!.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
struct Node
{
    int a, x;
    bool friend operator < (Node a, Node b) { return a.x == b.x ? a.a < b.a : a.x < b.x; }
} a[N];
void solve()
{
    int n = read(), k = read();
    for (int i = 1; i <= n; i++) a[i].a = read();
    for (int i = 1; i <= n; i++) a[i].x = abs(read());
    std::sort(a + 1, a + 1 + n);
    int flag = 1;
    for (int i = 1, j = 1, tot = 0; i <= n; i++)
    {
        tot += k;
        for (; j <= n and a[j].x == i; j++) tot -= a[j].a;
        if (tot < 0) { flag = 0; break; }
    }
    puts(flag ? "YES" : "NO");
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("B.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

C

赛时的时候乱想想到一个构造

全部填 mex，发现不够的话就随便挑几个补上就行了

一开始思维混乱不会做，然后直觉想出来可以这样，感性理解一下显然正确（

[Codeforces 1923C] Find B.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, a[N], q, b[N], c[N];
void solve()
{
    n = read(), q = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = b[i - 1] + (a[i] == 1);
    for (int i = 1; i <= n; i++) c[i] = c[i - 1] + a[i];
    for (int l, r; q--; )
    {
        l = read(), r = read();
        if (l == r) { puts("NO"); continue; }
        int sum = c[r] - c[l - 1];
        int num = b[r] - b[l - 1];
        int cost = num * 2 + (r - l + 1 - num);
        puts(cost <= sum ? "YES" : "NO");
    }
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("C.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

D

赛时降智了只想着固定往一个方向吃。其实如果任意方向吃的话，一段如果不是一样的话，最大的那个必然可以左吃右吃吃出来。这样的话只要区间和够大就行了，二分这个位置即可

[Codeforces 1923D] Slimes.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mid ((L + R) >> 1)
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
int n, a[N];
int las[N], sum[N];
vector<int> work()
{
    vector<int> ans(n, n);
    for (int i = 1; i <= n; i++)
    {
        las[i] = a[i] == a[i - 1] ? las[i - 1] : i;
        sum[i] = sum[i - 1] + a[i];
        if (a[i - 1] > a[i]) { ans[i - 1] = 1; continue; }
        for (int L = 1, R = i - 1; L <= R; )
            if (sum[i - 1] - sum[mid - 1] > a[i] and las[i - 1] > mid)
                ans[i - 1] = i - mid, L = mid + 1;
            else R = mid - 1;
    }
    return ans;
}
void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    auto l = work();
    std::reverse(a + 1, a + 1 + n);
    auto r = work();
    for (int i = 0; i < n; i++)
    {
        int now = std::min(l[i], r[n - 1 - i]);
        printf("%lld ", now == n ? -1 : now);
    }
    puts("");
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("D.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

E

[Codeforces 1923E] Count Paths.cpp >folded

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int n, a[N], cnt[N], ans;
std::vector<int> g[N];
void dfs(int u, int fa)
{
    ans += cnt[a[u]];
    int tmp = cnt[a[u]];
    for (auto v : g[u])
        if (v ^ fa)
            cnt[a[u]] = 1, dfs(v, u);
    cnt[a[u]] = tmp + 1;
}
void solve()
{
    n = read(), ans = 0;
    for (int i = 1; i <= n; i++) a[i] = read(), g[i].clear(), cnt[i] = 0;
    for (int i = 1, u, v; i < n; i++) u = read(), v = read(), g[u].pb(v), g[v].pb(u);
    dfs(1, 0);
    cout << ans << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("D.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}