计数和 dp

· · 算法·理论

来我的博客里读。

P14636 [NOIP2025] 清仓甩卖

前提:NOIP2025 考场上得了 4 分,特此来重新做一下。

经过 3h 奋战,以下思路由 AI 整理。

先将所有商品按原价从大到小排序,考虑一个贪心失败的关键结构:u(1)\to v(2)\to w(1)。其中 u 的售价为 1,v 的售价为 2。买完 u 后只剩 1 元,因此 v 无法购买,之后还可能再买到一个售价为 1 的商品 w。

考虑对 u,v 这个结构进行枚举,为了避免重复统计,我们钦定 v 为买完 u 后第一个因为只剩 1 元而被跳过的 2 元商品。这样,在实际贪心顺序中 u 和 v 之间不能再出现售价为 2 的商品,从而每个失败方案只会被统计一次。

首先,在买 u 之前必须恰好花掉 m-2 元。对于其他商品 z,若其售价为 1,想排在 u 前面需要 a_z\ge a_u;设这样的商品有 x 个。若其售价为 2 仍能排在 u 前面,则需要 a_z\ge 2a_u;设这样的商品有 y 个。显然后一类包含在前一类中。

假设这 y 个商品中有 t 个售价为 2,则它们总共花费 2t+(y-t)=y+t。还需要从另外 x-y 个商品中选出 m-2-y-t 个售价为 1,因此方案数为 \sum_t\binom yt\binom{x-y}{m-2-y-t}。由范德蒙德卷积,这一部分可以直接化为 \binom{x}{m-y-2}。至此前面的计数处理完毕。

接着考虑 u 和 v 的关系。由于 u(1) 必须排在 v(2) 前面,需要 a_u>\frac{a_v}{2},即 2a_u>a_v。同时按原价排序后有 a_u<a_v,因此要求 a_u<a_v<2a_u。

买完 u 后只剩 1 元,所以 v 被跳过。如果后面买到了 w(1),贪心得到的价值是 a_u+a_w;而如果不买 u、直接购买 v,价值为 a_v。因此贪心失败需要 a_u+a_w<a_v,也就是 a_w<a_v-a_u。

于是,对于后面的商品,如果满足 a_w\ge a_v-a_u,它就绝对不能售价为 1,否则贪心可以买到它并得到 a_u+a_w\ge a_v,不再失败。所以这些商品都必须售价为 2。而从第一个满足 a_w<a_v-a_u 的位置开始,后面的商品如何定价都不会影响失败条件,因此这一整段可以自由选择;若长度为 k,贡献就是 2^k。

因此总体就是:枚举关键的 u,v,满足 a_u<a_v<2a_u;前面用组合数统计恰好花掉 m-2 元的方案;后面找到第一个满足 a_w<a_v-a_u 的位置,之后贡献 2^{\text{后缀长度}}。累计得到坏方案数 \text{bad},最终答案为 2^n-\text{bad}。利用单调性双指针维护后缀起点,总复杂度为 O(n^2)。

这里是一份 AI 的实现:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=5005;
int c,T;
int n,m;
int a[5005];
int f[5005],invf[5005],pw[5005];
int qpow(int a,int b){
    int h=a,ans=1;
    while(b){
        if(b&1){
            ans*=h;
            ans%=mod;
        }
        h*=h;
        h%=mod;
        b>>=1;
    }
    return ans;
}
int C(int x,int y){
    if(x<0||y<0||y>x) return 0;
    int ans=f[x];
    ans*=invf[y];
    ans%=mod;
    ans*=invf[x-y];
    ans%=mod;
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    f[0]=invf[0]=1;
    for(int i=1;i<N;i++){
        f[i]=f[i-1]*i%mod;
        invf[i]=qpow(f[i],mod-2);
    }
    pw[0]=1;
    for(int i=1;i<N;i++){
        pw[i]=pw[i-1]*2%mod;
    }
    cin>>c>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+n+1,greater<int>());
        int bad=0;
        for(int i=1;i<=n;i++){
            int pos=i;
            while(pos+1<=n&&a[pos+1]==a[i]){
                pos++;
            }
            int k=n+1;
            for(int j=pos+1;j<=n&&2*a[j]>a[i];j++){
                while(k-1>j&&a[j]+a[k-1]<a[i]){
                    k--;
                }
                int front=C(j-2,m-i-1);
                int back=pw[n-k+1];
                bad+=front*back%mod;
                bad%=mod;
            }
        }
        int ans=(pw[n]-bad+mod)%mod;
        cout<<ans<<"\n";
    }
    return 0;
}

CF1920E Counting Binary Strings

转化一下,一个“好”子串是由中心的一个 1 和周围的若干 0 组成,考虑对这个去做计数,设 1 的个数为 t。

考虑把字符串拆为一串 0 和一些单个的 1 交替组成,一共有 t+1 个互相被 1 隔段的 0 串,设第 i 个长度为 b_i。

现在变为求满足以下条件的非负整数 b 序列问题:

考虑设 dp_{i,j} 表示上一个数填的是 i,此时 sum 为 j。转移很容易,最后复杂度为 O(n^2 \log n)。

CF1521D Nastia Plays with a Tree

不难发现删边数等于加边数,将问题转化为删边。

设 dp_{u,0/1} 为 u 的子树变为若干条链所需的最小删边数,其中 u 为一条链上的点或 u 为一条链的端点。

:::info[为什么这样定义]

如果只有一维,我们无法得知一个 v 是否能与 u 结合为一条链。

:::

分三种情况:

dp_{u,0}=\min{P1,P2,P3},dp_{u,1}=\min{P1,P2}

方案简单记录一下。

CF1989E Distance to Different

我怎么还是不会做。

考虑 a 可以剖成若干个数字相同的段,手动模拟一下:

:::info[一个例子]

:::

这时候发现,b 与 a 具体数值无关,且为上升后再下降的形式。

这里是 a 在串中间的情况。若 a 在首尾时,则为 ...,5,4,3,2,1 与 1,2,3,4,5...。

每个长度为 n 的在中间的 a 串都有对应的不同的 b 吗?这里有一种反例:

这样可能算重复,不考虑长度为 2 的串即可。

这时候,考虑对串统计。dp_{i,j} 表示当前在第 i 个数,分了 j 段的方案数。此时中间段长度不能为 2。前缀和优化即可。

CF1336C Kaavi and Magic Spell

设 dp_{l,r} 表示用 S 中的前 r-l+1 个字符匹配好 T 的 r-l+1 的方案数。

当 i>m 时,我们将没有匹配要求。

初始化时若 S_1 = T_i 或 i > m,则 dp_{i,i}=2。(这是因为放到开头和末尾视为两种不同方案)。

转移时考虑分左边与右边,左边当 l>m 或 S_{r-l+1} = T_l 时,dp_{l,r}=dp_{l,r}+dp_{l+1,r}。右边的转移是类似的。

答案就是 \sum_{j=m}^n dp_{1,j}。

P6146 [USACO20FEB] Help Yourself G

洛谷题解区非常神奇,都是使用 dp 的。

考虑连通块数量等于 1 加上相邻连通块之间的间隔数,先令答案为 2^n-1。

将所有线段端点离散化,统计每个坐标作为左、右端点的线段数量,并预处理左端点后缀和 g_1 与右端点前缀和 g_2。

接着,枚举每对相邻离散化坐标 x_i,x_{i+1},统计在此处形成间隔的方案数。左侧从右端点不超过 x_i 的线段中任选非空子集,方案数为 2^{g_2[i]}-1;右侧从左端点不小于 x_{i+1} 的线段中选择,且至少选择一条左端点恰为 x_{i+1} 的线段,方案数为 2^{g_1[i+1]}-2^{g_1[i+1]-f_1[i+1]}。

两侧选择相互独立,将方案数的乘积累加至答案,最后对 10^9+7 取模。

时间复杂度为 O(n\log n),空间复杂度为 O(n)。

CF1918D Blocking Elements

考虑直接二分答案,设当前答案为 x。

固定完答案,设 dp_i 表示在 i 这个位置阻断了的,之前每个段总和 \le x,整体的最小代价。

转移为 dp_i = a_i + \min dp_j 且 sum_{j+1,i-1} \le x。不难发现这个可以单调队列,随便优化即可。

答案为 \min dp_n,dp_i(sum_{i+1,n} \le x)。

CF1666F Fancy Stack

面对可能重复的序列,我们先不去重,最后再除以每种数字出现次数的阶乘。

设 dp_{i,v} 表示当前填写了 2i 个数,此时 b_{2i} 为 v 的总方案数。p_v 为严格 <v 的 a 数量。

转移将从 dp_{i-1,j} 且 j<v 转移。

考虑 b_{2i-1}<b_{2i-2} 且 b_{2i-1}<b_{2i},又因为 b_{2i}>b_{2i-2},所以只需考虑 b_{2i-1}<b_{2i-2}。

不难发现,在前 2i-2 个数中,只有 b_{2i-2}=b_{2i-2},其他的 2i-3 个数都会 <b_{2i-2},故方案有 p_{b_{2i-2}}-(2i-3) 种。(p_{b_{2i-2}}-(2i-3) 为 0 不应该转移)

现在考虑 b_{2i},由于前面都没有出现过 v,所以方案有 cnt_v 种。

所以转移就是 dp_{i,v}={cnt_v}dp_{i-1,j}\times{[p_{b_{2i-2}}-(2i-3)]}。

这个转移不依赖 j,前缀和优化一下就变成了 O(n^2)。

CF1799D2 Hot Start Up (hard version)

超级好的 dp 题,好像是 CSP2024 T3。

不难发现在一次运行之后,一台 CPU 最后一次操作一定为 a_i。考虑直接设计状态 dp_j 在操作 i 之后,另一台 CPU 的状态为 j。

  1. 当使用新的一台 CPU 时

实际上为 dp_{a_{i-1}}=\min{dp_{a_i}+hot_{a_i},dp_j+cold_{a_i}}。

  1. 当使用旧的一台 CPU 时

这是一个线段树的区间修改和单点赋值,直接做就好了。