题解 | DEFG

D

学过筛的很容易发现 (有彩笔一开始没发现写了个三log做法，我不说是谁) ，这实际上就是个筛的过程。

输出最小的没出现的质数即可，显然可以双指针，当然也可以二分。

std::vector<int> ps, phi, mu;
void getPrime(int n = 3e6)
{
    phi.resize(n+1); mu.resize(n+1);
    std::vector<bool> vis(n+1, false);
    vis[1] = true; phi[1] = 1; mu[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(!vis[i]) ps.push_back(i), phi[i] = i-1, mu[i] = -1;
        for(auto p: ps)
        {
            if(1ll * i * p > n) break;
            vis[i*p] = true;
            if(!(i%p))
            {   
                mu[i*p] = 0;
                phi[i*p] = phi[i] * p; 
                break; 
            }
            phi[i*p] = phi[i] * phi[p];
            mu[i*p] = -mu[i];
        }
    }
}
void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n+1);
    for(int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    std::ranges::sort(a);
    for(int i = 0, j = 1; i < (int)ps.size() && j < (int)a.size(); ++i) {
        while(j < (int)a.size() && a[j] < ps[i]) ++j;
        if(j > n || a[j] != ps[i]) {
            std::cout << ps[i] << '\n';
            return;
        }
    }
}

E

补个并查集暴力合并并维护是否可以继续向后合并。每个点只会被合并一次，复杂度 。

最后把前 大的连通块统计出来即可。

void solve()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<pii> a(n+1);
    for(int i = 1; i <= n; ++i) {
        std::cin >> a[i].second;
    }
    for(int i = 1; i <= n; ++i) {
        std::cin >> a[i].first;
    }
    std::ranges::sort(a);
    Dsu dsu(n);
    std::vector<int> sz;
    for(int i = 1; i <= n; ++i) {
        if(dsu.size(i) != 1) continue;
        int r = a[i].first + a[i].second;
        int cur = i;
        while(1) {
            int p = std::ranges::upper_bound(a, pii(r, 2e9)) - a.begin() - 1;
            if(p == cur) break;
            for(int j = cur + 1; j <= p; ++j) {
                chkmax(r, a[j].first + a[j].second);
                dsu.merge(i, j);
            }
            cur = p;
        }
        sz.push_back(dsu.size(i));
    }
    std::ranges::sort(sz, std::greater<>());
    int ans = 0;
    for(int i = 0; i < m && i < int(sz.size()); ++i) {
        ans += sz[i];
    }
    std::cout << ans << '\n';
}

F

答案对应 , 为所有墙的区间长度。

首先发现只有相邻两项的距离有用(更远的可以逐个用相邻两项拼出来)。然后发现相同长度的只要一个，于是直接区间长度数量从 退化到 。

随后就是一个 完全背包，随便做做。

void solve()
{
    int n, m, t;
    std::cin >> n >> m >> t;
    t -= n;
    std::vector<int> x(m + 1);
    for(int i = 1; i <= m; ++i) {
        std::cin >> x[i];
    }
    if(t < 0) {
        std::cout << "0\n";
        return;
    }
    std::ranges::sort(x);
    x.erase(std::unique(x.begin(), x.end()), x.end());
    m = x.size() - 1;
    std::vector<int> dx(m);
    for(int i = 2; i <= m; ++i) {
        dx[i - 1] = x[i] - x[i-1];
    }
    std::ranges::sort(dx);
    dx.erase(std::unique(dx.begin(), dx.end()), dx.end());
    int tt = t / 2;
    std::vector<bool> dp(tt + 1); 
    dp[0] = true;
    for(int i = 1; i < int(dx.size()); ++i) {
        for(int j = dx[i]; j <= tt; ++j) {
            dp[j] = dp[j] | dp[j - dx[i]];
        }
    }
    int mx = 0;
    for(int i = tt; i >= 0; --i) {
        if(dp[i]) {
            mx = i;
            break;
        }
    }
    std::cout << mx * 2 + n << '\n';
}

G

跟965的E很相似的一个东西。

公式化区间转端点，然后每个点内统计答案的时候可以直接暴力向上合并。

为什么呢？

因为除了第一次是合并 的鱼, 每次合并的一定都在 的范围内, 这样只要有新值进来就能直接使答案倍增，因此暴力合并的次数是 的。

挂个线段树就是 。当然能有其他东西挂过来，但是线段树确实足够无脑。

void solve()
{
    int n, x;
    std::cin >> n >> x;
    std::vector<std::array<int, 3>> a(n+1);
    std::vector<int> b{0}, c{0, x};
    for(int i = 1; i <= n; ++i) {
        auto &[l, r, x] = a[i];
        std::cin >> l >> r >> x;
        b.push_back(l); b.push_back(r); c.push_back(x);
    }
    std::ranges::sort(b);
    b.erase(std::unique(b.begin(), b.end()), b.end());
    std::ranges::sort(c);
    c.erase(std::unique(c.begin(), c.end()), c.end());
    int m = b.size() - 1, t = c.size() - 1;
    std::vector<std::vector<int>> L(m + 1), R = L;
    for(int i = 1; i <= n; ++i) {
        auto &[l, r, x] = a[i];
        l = std::ranges::lower_bound(b, l) - b.begin();
        r = std::ranges::lower_bound(b, r) - b.begin();
        x = std::ranges::lower_bound(c, x) - c.begin();
        L[l].push_back(i); R[r].push_back(i);
    }
    i64 ans(0);
    SegmentTree<Info, Tag> st(t);
    for(int i = 1; i <= m; ++i) {
        for(auto id: R[i]) st.modify(a[id][2], -c[a[id][2]]);
        for(auto id: L[i]) st.modify(a[id][2], c[a[id][2]]);
        i64 sum = x;
        int lst = 1;
        while(1) {
            int cur = std::ranges::upper_bound(c, sum) - c.begin() - 1;
            auto tmp = st.query(lst, cur).sum;
            sum += tmp;
            lst = cur + 1;
            if(tmp == 0 || lst > t) break;
        }
        chkmax(ans, sum);
    }
    std::cout << ans << '\n';
}