P10143 [WC2024] 代码堵塞题解

Cuiyi_SAI · 2024-02-06 21:11:05 · 题解

WC2024 T1。

还记得去年 WC 24pts 就能铜牌，89 就 Au，今年居然给了一道送分题。

\large{\text{Question}}

一共有 n~(1\le n\le 200) 道题目和时间 T~(1\le T\le 3\cdot 10^5)，每道题有三种属性：a_i\in\{0,1\}，1\le t_i \le 3\cdot 10^5，1\le v_i \le 3\cdot 10^5，表示做完第 i 题需要花费 c_i 的时间，可以得到 v_i 的分数。小 A 会按照先从左到右做完 a_i=0 的题目，再从左到右做 a_i=1 的题目，如果做到完这题的时间超过 t 则不得分。a 是未知的，对于 2^n 种 a 问小 A 能得到的分数和是多少？

\large{\text{Solution}}

我们并不关心具体的 a 是怎么样的，所以可以考虑求出每道题对答案产生的贡献。而每道题的贡献就是他的分数乘以在不同的 a 中能被选中的次数。因此我们求出对于每道题有共多少种 a 使得这道题可以被选上即可。

我们分类讨论 a_i=0 和 1 的情况：

若 a_i=0：容易发现当 j>i 时无论 a_j 对第 i 道题产生影响，所以后面的 a_j 怎么选都可以，根据乘法原理，最终贡献得乘上一个 2^{n-i}。

现在我们只需要考虑 j<i 的 a_j 即可，而容易发现只有当 a_j=0 时才会对这道题有影响（因为我们做题是先做完 0 再做 1）。设前面的题总共做题时间为 S，那么只有当 S+t_i\le T 时我们才可以做第 i 题。移一下项就变成 S\le T-t_i。

此时我们再回顾现在要解决的问题：选出一些 j<i 令 a_j=0，若它们 T_j 之和（即 S）小于 T-t_i 则称为合法，要求一共有多少种合法方案。可以发现这就是一个背包问题，t_j 就是费用， T-t_i 就是背包的容量，方案数就是要求的东西，动态规划解决即可。

至此，我们求出当 a_i=0 时第 i 题的贡献： v_i\cdot 2^{n-i}\cdot f_{i-1,T-t_i}，其中 f_{i,j} 表示在前 i 道题中选若干道做总用时不超过 j 的选法，按照 01 背包转移即可。
若 a_i=1：根据题意，对于 j<i 无论 a_j 是什么我们都要先完成 j 才能轮到 i。所以当 \sum\limits_{j=1}^{i-1}t_j+t_i>T 时第 i 题不得分，因为做不了。否则，根据上述分析的经验可知，无论 a_j 怎么选，i 都是有贡献的，所以也要乘上一个 2^{i-1}。

而对于 j>i 的题显然只有当 a_j=0 时才会对贡献产生影响。那到底有多少种情况呢？可以发现这也是一个 01 背包计算方案的问题，原理同上面分析 a_i=0 时一样。此时费用就是 t_j，背包容量就是 T-\sum\limits_{k=1}^{i}t_k。

所以此时第 i 题的贡献为 v_i\cdot 2^{i-1}\cdot g_{i+1,T-sumt_i}，其中 sumt_i 表示 \sum\limits_{k=1}^{i}t_k，g_{i,j} 表示从 [i,n] 这些题中选若干道使得用时和不超过 j 的方案数。因为是从后面选所以要倒着背包。

至此，这道题就做完了，我们只需要 O(n) 的处理出每道题的贡献然后相加即可。显然这个过程是可以和背包同时完成的，所以总复杂度时 O(nT)。

\large{\text{Code}}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int T,n,t,c[210],v[210],sumc[210];
int ans,f[300010],g[300010],sf[300010],sg[300010];
int ksm(int a,int b){
    int res=1ll;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T>>n>>t;
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++) cin>>c[i],sumc[i]=(sumc[i-1]+c[i])%mod;
    f[0]=g[0]=sf[0]=sg[0]=1;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=t;j++) sf[j]=(sf[j-1]+f[j])%mod;
        if(sumc[i]<=t) ans=(ans+1ll*v[i]*sf[t-sumc[i]]%mod*ksm(2,i-1)%mod)%mod;
        for(int j=t;j>=c[i];j--){
            f[j]=(f[j]+f[j-c[i]])%mod;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=t;j++) sg[j]=(sg[j-1]+g[j])%mod;
        if(c[i]<=t) ans=(ans+1ll*v[i]*sg[t-c[i]]%mod*ksm(2,n-i)%mod)%mod;
        for(int j=t;j>=c[i];j--){
            g[j]=(g[j]+g[j-c[i]])%mod;
        }
    }
    cout<<ans;
    return 0;
}

P10143 [WC2024] 代码堵塞 题解

\large{\text{Question}}

\large{\text{Solution}}

\large{\text{Code}}

P10143 [WC2024] 代码堵塞题解