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

ran_qwq · 2025-02-10 20:35:52 · 题解

下文的 l_i 表示题目的 k_i。

数据范围提示也太明显了吧。

注意到 \sum l_i\cdot s\le10^7，一个 O(\sum l_i\cdot s) 的 dp 呼之欲出：f_{i,j,k,0/1} 表示第 i 题第 j 个 subtask，总分为 k，这道题目前有没有得分是否可行。

转移几种情况：

• 当前是第一个 subtask：
  • 不拿分，f_{i,1,k,0}\leftarrow f_{i-1,l_{i-1},k,1}。
  • 拿分，f_{i,1,k,1}\leftarrow f_{i-1,l_{i-1},k-c_{i,1},1}。
• 当前不是第一个 subtask：
  • 不拿分：
  • 这道题之前没拿过分，f_{i,j,k,0}\leftarrow f_{i,j-1,k,0}。
  • 这道题之前拿过分，f_{i,j,k,1}\leftarrow f_{i,j-1,k,1}。
  • 拿分：
  • 这道题之前没拿过分，f_{i,j,k,1}\leftarrow f_{i,j-1,k-c_{i,j},0}。
  • 这道题之前拿过分，f_{i,j,k,1}\leftarrow f_{i,j-1,k-c_{i,j},1}。

需要输出方案，dp 数组可以记录“这道题当前拿不拿分”和“这道题之前有没拿过分”，构造时不断往前跳。

直接开 vector 会 MLE，需要开一维数组 dp。

int n,m,l[N],sl[N]; pii f[N*210]; vi c[N]; vi as[N];
il int gt(int x,int y,int z,int p) {return (m+1)*2*(sl[x-1]+y)+z*2+p;}
void prt(int x,int y,int z,int p) {
    if(!x) return;
    auto [s,t]=f[gt(x,y,z,p)];
    int u=x,v=y-1; if(!v) u--,v=l[u];
    if(s==1) prt(u,v,z,t);
    else as[x].pb(y),prt(u,v,z-c[x][y],t);
}
void QwQ() {
    n=rd(),m=rd(),sl[0]=1;
    for(int i=1;i<=n;i++) {
        l[i]=rd(),c[i].resize(l[i]+1),sl[i]=sl[i-1]+l[i];
        for(int j=1;j<=l[i];j++) c[i][j]=rd();
    }
    f[gt(0,0,0,1)]={-1,-1};
    for(int i=1;i<=n;i++) {
        for(int k=0;k<=m;k++) {
            if(f[gt(i-1,l[i-1],k,1)].fir) f[gt(i,1,k,0)]={1,1};
            if(k>=c[i][1]&&f[gt(i-1,l[i-1],k-c[i][1],1)].fir) f[gt(i,1,k,1)]={2,1};
        }
        for(int j=2;j<=l[i];j++) for(int k=0;k<=m;k++) {
            if(f[gt(i,j-1,k,0)].fir) f[gt(i,j,k,0)]={1,0};
            if(f[gt(i,j-1,k,1)].fir) f[gt(i,j,k,1)]={1,1};
            else if(k>=c[i][j])
                if(f[gt(i,j-1,k-c[i][j],0)].fir) f[gt(i,j,k,1)]={2,0};
                else if(f[gt(i,j-1,k-c[i][j],1)].fir) f[gt(i,j,k,1)]={2,1};
        }
    }
    if(!f[gt(n,l[n],m,1)].fir) puts("No");
    else {
        puts("Yes"),prt(n,l[n],m,1);
        for(int i=1;i<=n;i++,puts("")) {
            wr(as[i].size(),"\n"),reverse(as[i].begin(),as[i].end());
            for(int j:as[i]) wr(j," ");
        }
    }
}