NOI Promax 2025 复盘

Ling_zeroo · 2025-12-05 11:39:25 · 个人记录

P14635 [NOIP2025] 糖果店 / candy

简单贪心。

发现只有一种糖果会买到第二颗，这种糖果即为 x_i+y_i 最小的一种。

把这种糖果拿出来，剩下糖果按照 x 升序，枚举购买一个前缀，剩下的钱全部买拿出来的这种糖果，所有情况取最大值即可。

时间复杂度 O(n\log n)。记得判断买不买得起某个前缀！

P14636 [NOIP2025] 清仓甩卖 / sale

遗失的赋值 喵了个喵 遗失的赋值 喵了个喵

看好了 NOIP2024，这才是真正的计数！

记原价为 \{a_i\}，重定价为 \{b_i\}。

部分分做法较为简单，此处略去。

考虑正解。好的定价的限制不好刻画，考虑什么时候一个定价是不好的，发现本质只一种情况。

把所有 a 降序排序，初始钦定所有 b_i=2，我们选一些 b_i\leftarrow 1。

枚举 x,i,j（可能不存在 j），满足： b_x=2；i 是最后一个满足 a_x>a_i>\frac{a_x}{2} 且 b_i=1 的位置；j 是继 i 下一个 b_j=1 的位置且 a_j+a_i<a_x。

这样 i 会排到 x 前面，j 会排到 x 后面。我们要求：购买时买到 x 时，我们恰好只剩下一块钱。这样我们买不起 x，只能买到 j，又 a_i+a_j<a_x，所以这种情况是不合法的！

接下来细化条件：

设 [1,x-1] 中选了 t 个 2，那么 x+1,i-1 里面要选 m-1-x-t 个 1 翻到前面，方案数为：

这是一个经典的卷积，由组合数的定义，得到其即为：

发现 j 是一段后缀，设 y 是第一个满足 a_i+a_j<a_x 的 j，这可以双指针简单求出，那么总方案即为：

只需要枚举 x,i 再双指针求出 y 即可。预处理组合数即可做到 O(\sum n^2)。

::::info[Code]

const int maxn = 5005;
const ll mod = 998244353;

ll qpow(ll x, ll y){
    ll res = 1, base = x;
    while(y){
        if(y & 1) res = res * base % mod;
        base = base * base % mod;
        y >>= 1;
    } return res;
}
ll fac[maxn<<1], inv[maxn<<1], pw[maxn];
ll C(int n, int m){
    if(n < m || m < 0 || n < 0) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

void init(){
    pw[0] = 1;
    for(int i = 1; i < maxn; i++) pw[i] = pw[i - 1] * 2 % mod;
    fac[0] = 1;
    for(int i = 1; i < (maxn<<1); i++) fac[i] = fac[i - 1] * i % mod;
    inv[(maxn<<1) - 1] = qpow(fac[(maxn<<1) - 1], mod - 2);
    for(int i = (maxn<<1) - 2; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}

int n, m, a[maxn];

void sol(){
    n = read(), m = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    sort(a + 1, a + 1 + n, greater<int>());
    ll ans = 0;
    for(int i = 2; i <= n; i++){
        int y = n + 1;
        for(int x = i - 1; x; x--){
            if(a[i] == a[x]) continue;
            if(a[i] * 2 <= a[x]) continue;
            while(y > i && a[y - 1] + a[i] < a[x]) --y;
            ans += C(i - 2, m - 1 - x) * pw[n - y + 1] % mod;
            ans %= mod; 
        }
    }
    ans = (pw[n] - ans + mod) % mod;
    cout << ans << "\n";
}

::::

P14638 [NOIP2025] 序列询问 / query

T4 < T3 这一块，感觉没有黑

DS 题，做法很多，介绍一种自己想出来的做法，非常简单。

你可能需要绘图帮助理解！

设 \{s_i\} 表示原数列的前缀和。

我们把一个区间 [l,r] 映射到平面直角坐标系上一个点 (l,r)，点权为 s_r-s_{l-1}。于是你会发现，对于每个固定的 L,R，有贡献的点实际上为一个梯形区域，随着 i 的增大而平移。而我们知道，一个梯形可以被分成三个平行四边形和一个正方形，于是分别对这个几个区域求解即可。

平行四边形区域，实际上是若干条线段，每条线段的 l 或者 r 固定，预处理 st 表即可 O(1) 求出每条线段的贡献，然后用单调队列维护即可。

正方形区域，可以直接求解。实际上即询问 \max\limits_{l_1\leq i\leq r_1}s_i-\min\limits_{l_2\leq i\leq r_2}s_i，预处理 st 表即可 O(1) 求出。

总时间复杂度 O(nq+n\log n)。

不需要开 long long，注意常数影响。

::::info[Code]

const int maxn = 5e4 + 5;

int n, q, a[maxn];

int lg[maxn];
int mx[maxn][16], mn[maxn][16];

il int qryMx(int l, int r){
    l = max(l, 1);
    r = min(r, n);
    if(l > r) return -iinf;
    int k = lg[r - l];
    return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
il int qryMn(int l, int r){
    l = max(l, 1);
    r = min(r, n);
    if(l > r) return iinf;
    int k = lg[r - l];
    return min(mn[l][k], mn[r - (1 << k) + 1][k]);
}

int ans[maxn], v[maxn<<1];

int qu[maxn], t, h;

void sol(){
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read(), a[i] += a[i - 1];
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; i++) mn[i][0] = a[i - 1], mx[i][0] = a[i];
    for(int k = 1; k <= 15; k++) for(int i = 1; i <= n; i++){
        if(i + (1 << k) - 1 <= n){
            mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
            mn[i][k] = min(mn[i][k - 1], mn[i + (1 << (k - 1))][k - 1]);
        }
    }
    q = read();
    while(q--){
        int L = read(), R = read();
        for(int i = 1; i <= n; i++) ans[i] = -iinf;
        for(int i = 1; i <= n; i++){
            if(i + L - 1 > n) v[i + L - 1] = -iinf;
            else v[i + L - 1] = a[i + L - 1] - qryMn(i + L - R, i);
        }
        t = 1, h = 0;
        for(int i = 1; i <= n; i++){
            while(h >= t && qu[t] < i) ++t;
            while(h >= t && v[i + L - 1] >= v[qu[h]]) --h;
            qu[++h] = i + L - 1;
            chkmx(ans[i], v[qu[t]]);
        }
        int len = L + R >> 1, del = (R - L >> 1) + ((R - L) & 1);
        for(int i = 1; i <= n; i++){
            if(i + len - 1 > n) v[i + len - 1] = -iinf;
            else v[i + len - 1] = a[i + len - 1] - qryMn(i - del, i);
        }
        t = 1, h = 0;
        for(int i = 1; i <= n; i++){
            while(h >= t && qu[t] < i + L - 1) ++t;
            while(h >= t && v[i + len - 1] >= v[qu[h]]) --h;
            qu[++h] = i + len - 1;
            chkmx(ans[i], v[qu[t]]);
        }
        del = R - L >> 1;
        for(int i = 1; i <= n; i++){
            v[i] = qryMx(i + len - 1, i + R - 1) - a[i - 1];
        }
        t = 1, h = 0;
        for(int i = 1; i <= n; i++){
            while(h >= t && qu[t] < i - del) ++t;
            while(h >= t && v[i] >= v[qu[h]]) --h;
            qu[++h] = i;
            chkmx(ans[i], v[qu[t]]);
        }
        for(int i = 1; i <= n; i++){
            int tmp = qryMx(i + L - 1, i + len - 1) - qryMn(i - del, i);
            chkmx(ans[i], tmp);
        }
        ull res = 0;
        for(int i = 1; i <= n; i++){
            res ^= 1ull * i * ans[i];
        }
        cout << res << "\n";
    }
}

::::

P14637 [NOIP2025] 树的价值 / tree

千呼万唤始出来

Sol 1

各种状压 DP，时间复杂度据实现而定。

Sol 2

考虑延迟贡献计算。仅仅填入小于当前 mex 的数字，设 f_{i,j,k} 表示对于节点 i，mex 为 j，儿子中还有 k 个位置没有填数字的最大价值。

这个过程类似于树上背包，时间复杂度 O(n^4)，加上前缀 max 优化可以做到 O(n^3)。

Sol 3

上面的状态严格强于背包问题，似乎已经没有优化的空间了。

考虑实际上我们的转移在做什么。对于节点 i，如果什么新的数字也不填入，其将会继承所有儿子中 mex 的最大值，定义被继承的那个儿子为 i 的重儿子，类似定义重链。于是每一种填入数字的方式实际上对应到了一个剖分。

把贡献拆到点上，假如节点 j 在其祖先 i 处被填上数字，使得 i 的 mex 变大。那么 j 实际上会影响所有能够继承到 i 节点的祖先，使得他们都变大 1。也就是影响了从 i 开始向上的一段重链前缀，j 的贡献即为这段前缀的点的个数。

显然，对于一个确定的剖分，贪心地填数，每个节点的贡献是确定的，即为其某个祖先处最长的重链前缀。

把所有贡献加起来，即为这个剖分的价值。

设 f_{i,j,k} 表示到 i 位置，之前最长的重链前缀长度为 j，i 所在的重链长度为 k 时，子树内贡献和的最大值。转移即枚举一个儿子 w 把重链延续下去：

时间复杂度 O(nm^2)。

Sol 4

考虑优化上述状态。发现实际上重要的状态只有两个：f_{i,j,1} 和 f_{i,j,j}。

设 f_{i,j} 表示当 i 为重链顶端，之前最长的重链前缀长度为 j 时，子树内贡献和的最大值。也就是之前定义的 f_{i,j,1}。

设 g_{i,j} 表示当 i 所在重链长度为 j，之前最长的重链前缀长度也为 j 时，子树内贡献和的最大值。也就是之前定义的 f_{i,j,j}。