Codeforces Round 922 (Div. 2)

比赛链接

A

[Codeforces 1918A] Brick Wall.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
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;
int n, a[N];

void solve()
{
    int n = read(), m = read();
        printf("%d\n", n * (m / 2));
}

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

B

[Codeforces 1918B] Minimize Inversions.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
// #define int long long
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 = 3e5 + 5;
int n;
struct Node
{
    int x, y;
    bool friend operator < (Node a, Node b)
    {
        return a.x + a.y < b.x + b.y;
    }
} a[N];

void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i].x = read();
    for (int i = 1; i <= n; i++) a[i].y = read();
    std::sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) printf("%d ", a[i].x);
    puts("");
    for (int i = 1; i <= n; i++) printf("%d ", a[i].y);
    puts("");
}

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

C

按位贪心即可

有个小坑是从第一个 1-0 的下一位开始操作

[Codeforces 1918C] XOR-distance.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define int long long
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;
}

void solve()
{
    int a = read(), b = read(), r = read();
    int k = 0, ans = 0;
    if (a < b) std::swap(a, b);
    for (int i = 63; i >= 0; i--)
        if (((a >> i) & 1LL) == 1 and ((b >> i) & 1LL) == 0) { k = i; break; }
    // printf("k : %lld\n", k);
    for (int i = k - 1; i >= 0; i--)
    {
        int x = (a >> i) & 1LL, y = (b >> i) & 1LL;
        if (x == 1 and y == 0)
        {
            if (ans + (1LL << i) <= r)
                ans += 1LL << i;
        }
    }
    // printf("[%lld]\n", ans);
    int x = a ^ ans;
    int y = b ^ ans;
    printf("%lld\n", x - y);
}

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

D

一眼二分，赛时不会 judge。不会处理断点的和。

一个常见的处理方法是把断点的和放到 dp 数组里面维护，转移的时候从距离小于限制的地方转移即可

可以转移的范围是一个滑动窗口

$$f_i = a_i + \min_{s_{i - 1} - s_j \leq lim}{f_j}$$

[Codeforces 1918D] Blocking Elements.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define int long long
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 = 1LL << 60;
int n, a[N], sum[N], q[N], f[N];
bool judge(int lim)
{
    int h = 1, t = 0;
    q[++t] = 0;
    for (int i = 0; i <= n + 1; i++) f[i] = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        for (; h <= t and sum[i - 1] - sum[q[h]] > lim; h++);
        f[i] = a[i] + f[q[h]];
        for (; h <= t and f[i] <= f[q[t]]; t--);
        q[++t] = i;
    }
    return f[n + 1] <= lim;
}
void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    a[n + 1] = 0;
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    int ans = 0;
    for (int L = 1, R = sum[n], mid; L <= R; )
        if (judge(mid = (L + R) >> 1)) ans = mid, R = mid - 1;
        else L = mid + 1;
    std::cout << ans << '\n';
}

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

E

>folded