Codeforces Round 919 (Div. 2)

比赛链接

A

[Codeforces 1920A] Satisfying Constraints.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()
{
    n = read();
    int max = 1e9 + 5, min = 0;
    std::set<int> s;
    for (int i = 1; i <= n; i++)
    {
        int opt = read(), x = read();
        if (opt == 1) min = std::max(min, x);
        else if (opt == 2) max = std::min(max, x);
        else s.insert(x);
    }
    int ans = max - min + 1;
    for (auto x : s)
        if (min <= x and x <= max)
            ans --;
    ans = std::max(ans, 0);
    printf("%d\n", ans);
}

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

B

给定一个全都是正整数的数组，A 玩家可以先移去最多 k 个元素，随后 B 玩家可以最多给 x 个元素加上负号。A 希望最大化数组元素之和，而 B 希望最小化数组元素之和。如果双方都以最优方式进行游戏，求游戏结束后数组元素的总和。

n <= 2e5

B 的决策肯定是给最大的几个都加上负号。A 要删肯定是删大的，枚举即可

[Codeforces 1920B] Summation Game.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, k, x, a[N], pre[N];

void solve()
{
    n = read(), k = read(), x = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    std::sort(a + 1, a + 1 + n, [](int a, int b){return a > b;});
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    int ans = -1e9 + 5;
    for (int i = 0; i <= k; i++)
    {
        int p = std::min(i + x, n);
        ans = std::max(ans, -(pre[p] - pre[i]) + pre[n] - pre[p]);
    }
    printf("%d\n", ans);
}

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

C

把数组切成正好 k 块，然后把每个数都 mod m，问你有多少个 k，存在 m 使得 mod m 后每一块都相同

两个数如果在模意义下相等，那他们的差必然在模意义下为 0。对这些差求 gcd 即可 check 是否存在 m。

[Codeforces 1920C] Partitioning the Array.cpp >folded

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

void judge(int k)
{
    int cnt = 0, x = 0;
    for (int i = 1; i <= k; i++)
        for (int j = i + k; j <= n; j += k)
        {
            int val = abs(a[j] - a[j - k]);
            if (!val) continue;
            if (!x) x = val, cnt = 1;
            else x = std::gcd(x, val);
        }
    if (x >= 2 or cnt == 0) ans++;
}

void solve()
{
    n = read(), ans = 0;
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i * i <= n; i++)
            if (n % i == 0)
            {
                judge(n / i);
                if (n / i != i) judge(i);
            }
    printf("%d\n", ans);
}

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

D

给定一个空数组，两种操作，一种是末尾 push 进去一个数，一种是把自己复制 x 次，push 到末尾

多次询问，查询任意位置

赛时嘴巴秒了，但是不会实现。做法是不断取模，往前跳。

记录每一次操作后数组的长度和数组末尾的数的位置。对于一个询问，不断二分取模即可

[Codeforces 1920D] Array Repetition.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;
int las[N], dp[N];

void solve()
{
    int n = read(), q = read();
    for (int i = 0; i <= n; i++) las[i] = dp[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        int opt = read(), x = read();
        if (opt == 1)
            las[i] = x, dp[i] = dp[i - 1] + 1;
        else
            las[i] = las[i - 1],
            dp[i] = (x + 1) > 2e18 / dp[i - 1] ? (long long)2e18 : dp[i - 1] * (x + 1);
    }
    for (int k; q--; )
    {
        k = read();
        while (1)
        {
            int pos = std::lower_bound(dp + 1, dp + 1 + n, k) - dp;
            if (dp[pos] == k)
            {
                std::cout << las[pos] << ' ';
                break;
            }
            if (k % dp[pos - 1] == 0)
            {
                std::cout << las[pos - 1] << ' ';
                break;
            }
            k %= dp[pos - 1];
        }
    }
    puts("");
}

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

E

>folded