Codeforces Round 924 (Div. 2)

比赛链接

A

[Codeforces 1928A] Rectangle Cutting.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 = 1LL << 60;
int n, a[N];
void solve()
{
    int a = read(), b = read();
    if (a < b) std::swap(a, b);
    if (a % 2 == 0)
    {
        // a / 2, b * 2
        int c =  a / 2, d = b * 2;
        if (c < d) std::swap(c, d);
        if (a != c or b != d)
            return puts("YES"), void();
    }
    if (b % 2 == 0)
    {
        int c = b / 2, d = a * 2;
        if (c < d) std::swap(c, d);
        if (a != c or b != d)
            return puts("YES"), void();
    }
    puts("NO");
}

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

B

去重以后在数轴上滑动窗口

[Codeforces 1928B] Equalize.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 = 1LL << 60;
int n, a[N];
void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    std::sort(a + 1, a + 1 + n);
    int m = std::unique(a + 1, a + 1 + n) - a - 1, ans = 1;
    for (int i = 1; i <= m; i++)
    {
        int res = i;
        for (int L = i, R = m, mid; L <= R;)
            if (a[mid = (L + R) / 2] - a[i] < n) res = mid, L = mid + 1;
            else R = mid - 1;
        ans = std::max(ans, res - i + 1);
    }
    printf("%d\n", ans);
}

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

C

第一个出现的位置是 x 和 2k - x，循环节长度是 2k - 2

解方程

$n \equiv x \pmod{2k - 2}$ 和 $n \equiv {2k - x} \pmod{2k - 2}$

等价于 $n - x \equiv 0 \pmod{2k - 2}$ 和 $n + x - 2 \equiv 0 \pmod{2k - 2}$

枚举因数即可

[Codeforces 1928C] Physical Education Lesson.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;
int n, x, kmax, a, b;
std::set<int> S;
void push(int y)
{
    if (y % 2 != 0) return;
    int k = (y + 2) / 2;
    if (std::max(2, x) <= k and k <= kmax) S.insert(k);
}
void solve()
{
    n = read(), x = read(), S.clear();
    kmax = (n + x) / 2, a = n - x, b = n + x - 2;
    for (int i = 1; i * i <= a; i++)
        if (a % i == 0) push(i), push(a / i);
    for (int i = 1; i * i <= b; i++)
        if (b % i == 0) push(i), push(b / i);
    printf("%d\n", S.size());
}

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

D

假如队伍数固定以后贡献是固定的，而且贡献可以独立计算，直接一个预处理然后枚举队伍数

有一个小优化是每次 k 不用枚举到 max(c)，只需要枚举到当前 c 即可，后面都是一个人一个队了。但是这样的话最后算答案的时候就会漏，要加个计数器累计现在超过了的东西的贡献

[Codeforces 1928D] Lonely Mountain Dungeons.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 = 2e5 + 5;
const int INF = 1LL << 60;
int c[N], sum[N], add[N];
int calc(int n, int k)
{
    if (n & k == 0) return 0;
    int x = n / k;
    int l = n % k, r = k - l;
    int L = (x + 1) * l, R = x * r;
    return R * L + (R - x) * R / 2 + L * (L - x - 1) / 2;
}
void solve()
{
    int n = read(), B = read(), X = read();
    for (int i = 1; i <= n; i++) c[i] = read();
    int m = *std::max_element(c + 1, c + 1 + n);
    memset(sum, 0, (m + 1) * 8UL);
    memset(add, 0, (m + 1) * 8UL);
    for (int i = 1; i <= n; i++)
    {
        for (int k = 1; k <= c[i]; k++)
            sum[k] += calc(c[i], k);
        add[c[i]] += calc(c[i], c[i]);
    }
    int ans = 0, tot = 0;
    for (int k = 1; k <= m; k++)
        ans = std::max(ans, B * (sum[k] + tot) - (k - 1) * X),
        tot += add[k];
    printf("%lld\n", ans);
}

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

E

>folded