Codeforces Round 1122 (Div. 3)

2026-09-22 23:42:29

昨天的，23 点发现有一场于是来看看。由于是 div.3 就直接看 F 题试试了，不出意外感觉很麻烦一点思路没有。于是去看 E 题了，有点思路但是思路不太对。今天想到了，确实挺简单的。

所以两个小时都在搞这两，前面的题也就没看了，毕竟想着前面的题都很简单，毕竟是 div.3。

今天才知道原来 std::println 可以直接输出 std::vector 的，之前没试过，和 python 的 print 效果差不多。然后 std::views 调试可能会比较方便，感觉语法挺简洁的，比起 java 的 Stream。

ABC 就没看了，10k 人过就没必要了，F 有点难，下次再看。

D

这有点抽象了吧，div.3 的 D 题不是应该很简单吗，虽然这题也不难。我自己没写出来来着，难道是太久没写了？感觉这个就没啥意思了。

说是由于每次操作，$a_i - i$ 的值并不会变化，所以就是找最长的连续段…… 确实，很简单，但是这种，感觉有点像 guess，不过 cf 是这样的。

/*
date: 2026-09-22 23:04:06
path: ~/Projects/cp_code/codeforces/2266/D.cpp
*/

#include <algorithm>
#include <cstdio>
#include <print>
#include <vector>

#define eprint(...) std::print(stderr, __VA_ARGS__)
#define eprintln(...) std::println(stderr, __VA_ARGS__)

void solve()
{
    int n;
    scanf("%d", &n);
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] -= i;
    }
    std::sort(a.begin() + 1, a.end());
    a.erase(std::unique(a.begin() + 1, a.end()), a.end());
    int ans = 0;
    // std::println(stderr, "{}", a);
    for(int i = 1, len = 0; i < a.size(); i++) {
        if(a[i] != a[i - 1] + 1)
            len = 0;
        len++;
        ans = std::max(ans, len);
    }
    std::println("{}", ans);
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
}

E

有一个多集，每次可以把一个数字 $x$ 除以它的一个质因子 $p$，然后增加 $p$ 个 $\frac{x}{p}$ 到集合里。需要使每个数字最后都小于 $k$，求最少的操作次数。

solution

很自然的就是正着想，小于 $k$ 的数字不需要操作，而刚刚大于 $k$ 的数字，它们除一个质因子就会 $\leq k$，所以只需要一次操作。那么我们正着遍历的话，更小的数字的花费都是已知的。就枚举看除哪个质因子会花费更小，$cost_x = \min (cost_i, 1 + cost_{\frac{i}{p}} \cdot p)$ 大概这样子。

/*
date: 2026-09-22 22:03:22
path: ~/Projects/cp_code/codeforces/2266/E.cpp
*/

#include <array>
#include <climits>
#include <cstdio>
#include <print>
#include <vector>

constexpr int N = 200'000;
std::array<int, N + 1> minp, a, cost;
std::vector<int> primes;

std::vector<int> get_primes(int x)
{
    std::vector<int> res;
    while (x > 1) {
        int p = minp[x];
        while (x % p == 0)
            x /= p;
        res.push_back(p);
    }
    return res;
}
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        a[i] = cost[i] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (x > k)
            a[x]++;
    }

    long long ans = 0;
    for (int i = k + 1; i <= n; i++) {
        cost[i] = INT_MAX;
        for (int p : get_primes(i)) {
            cost[i] = std::min(cost[i], 1 + cost[i / p] * p);
        }
        ans += 1LL * cost[i] * a[i];
    }
    // for (int i = 1; i <= n; i++)
    //     std/*
date: 2026-09-22 22:03:22
path: ~/Projects/cp_code/codeforces/2266/E.cpp
*/

#include <array>
#include <climits>
#include <cstdio>
#include <print>
#include <vector>

constexpr int N = 200'000;
std::array<int, N + 1> minp, a, cost;
std::vector<int> primes;

std::vector<int> get_primes(int x)
{
    std::vector<int> res;
    while (x > 1) {
        int p = minp[x];
        while (x % p == 0)
            x /= p;
        res.push_back(p);
    }
    return res;
}
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        a[i] = cost[i] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (x > k)
            a[x]++;
    }

    long long ans = 0;
    for (int i = k + 1; i <= n; i++) {
        cost[i] = INT_MAX;
        for (int p : get_primes(i)) {
            cost[i] = std::min(cost[i], 1 + cost[i / p] * p);
        }
        ans += 1LL * cost[i] * a[i];
    }
    // for (int i = 1; i <= n; i++)
    //     std::print(stderr, "{} ", cost[i]);
    // std::println(stderr);
    std::println("{}", ans);
}
int main()
{
    for (int i = 2; i <= N; i++) {
        if (!minp[i]) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > N)
                break;
            minp[i * p] = p;
            if (i % p == 0)
                break;
        }
    }
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
}::print(stderr, "{} ", cost[i]);
    // std::println(stderr);
    std::println("{}", ans);
}
int main()
{
    for (int i = 2; i <= N; i++) {
        if (!minp[i]) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > N)
                break;
            minp[i * p] = p;
            if (i % p == 0)
                break;
        }
    }
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
}