题解：P11703 [ROIR 2025] 个人 OI 比赛的原则

wzb13958817049 · 2025-02-10 22:13:44 · 题解

思路

首先考虑判断 Yes 和 No，可以看出来是 01 背包，内存较大可以用滚动数组，但是 bitset 也不会 MLE，代码如下：

for(int i=1;i<=n;i++){
    for(int j=0;j<v[i].size();j++){
        int u=v[i][j];
        for(int k=s;k>=u;k--){
            dp[i][k]=dp[i][k]|dp[i][k-u];
            dp[i][k]=dp[i][k]|dp[i-1][k-u];
        }
    }
}

再写 DFS 输出即可，题中指出 (k_1 + k_2 + … k_n) \times s \le 10^7 所以并不会 TLE。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s;
bitset<100000> dp[100005];
vector<ll> v[100005],ans[100005];
void dfs(int x,int u,int last){
    if(x==0){
        if(u==0){
            for(int i=1;i<=n;i++){
                cout<<ans[i].size()<<"\n";
                for(int j=0;j<ans[i].size();j++){
                    cout<<ans[i][j]<<" ";
                }
                cout<<"\n";
            }
            exit(0);
        }
        return ;
    }
    for(int i=last;i<v[x].size();i++){
        int y=v[x][i];
        if(u>=y && dp[x][u-y]){
            ans[x].push_back(i+1);
            dfs(x,u-y,i+1);
            ans[x].erase(--ans[x].end());
        }
        if(u>=y && dp[x-1][u-y]){
            ans[x].push_back(i+1);
            dfs(x-1,u-y,0);
            ans[x].erase(--ans[x].end());
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        for(int j=1;j<=x;j++){
            ll y;cin>>y;
            v[i].push_back(y);
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<v[i].size();j++){
            int u=v[i][j];
            for(int k=s;k>=u;k--){
                dp[i][k]=dp[i][k]|dp[i][k-u];
                dp[i][k]=dp[i][k]|dp[i-1][k-u];
            }
        }
    }
    if(dp[n][s]==0) cout<<"No";
    else{
        cout<<"Yes\n";
        dfs(n,s,0);
    }   
    return 0;
}