M_sea

洛谷5289 [十二省联考2019]皮配
LuoguLOJ分析事实上这题知识点就只有背包啊...然而我就是不会做...先考虑 $k=0$ 怎么做。首先发现,...
扫描右侧二维码阅读全文
04
2019/06

洛谷5289 [十二省联考2019]皮配

Luogu

LOJ

分析

事实上这题知识点就只有背包啊...然而我就是不会做...


先考虑 $k=0$ 怎么做。

首先发现,在城市选择了阵营之后,学校相当于选择派系。

那么设 $f[i][j]$ 表示前 $i$ 个城市有 $j$ 人在蓝阵营的方案数,$g[i][j]$ 表示前 $i$ 个学校有 $j$ 个人在鸭派系的方案数。

$\mathrm{dp}$ 求出后乘起来累加即可求出答案。


再考虑扩展到 $k\neq 0$ 的情况。

注意到 $k$ 比较小,我们可以把有限制的和没有限制的分开计算。

重新设 $f[i][j]$ 表示前 $i$ 个没有限制学校的城市有 $j$ 人在蓝阵营的方案数,$g[i][j]$ 表示前 $i$ 个没有限制的学校有 $j$ 个人在鸭派系的方案数。

再设一个 $dp[i][x][y]$ 表示前 $i$ 个有限制学校的城市,有 $j$ 人在蓝阵营、$k$ 人在鸭派系的方案数。

同样 $\mathrm{dp}$ 后乘起来累加即可求出答案。


注意到空间开不小,需要滚动数组。

另外复杂度好像有点假,可以以转移过了的总人数为 $\mathrm{dp}$ 上界,然后就可以过了。

还有要注意一下可能会存在没有人参赛的城市。


具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2500+10;
const int mod=998244353;

inline void add(int& x,int y) { x=(x+y)%mod; }

int n,c,c0,c1,d0,d1,lim,sum;
int b[N],s_school[N],h[N],s_school_city[N],mark[N];
int f[N],g[N],dp[N][N],tmp[N][N];

inline int calc(int x,int y) {
    int i=max(sum-d1-y,0),j=d0-y,k=max(sum-c1-x,0),l=c0-x;
    if (i>j||k>l) return 0;
    return 1ll*(f[j]-f[i-1]+mod)*(g[l]-g[k-1]+mod)%mod;
}

inline void init() {
    sum=0;
    memset(s_school_city,0,sizeof(s_school_city));
    memset(h,-1,sizeof(h));
    memset(mark,0,sizeof(mark));
    memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    memset(dp,0,sizeof(dp)),memset(tmp,0,sizeof(tmp));
}

int main() {
    int T=read();
    while (T--) {
        init();
        
        n=read(),c=read(),c0=read(),c1=read(),d0=read(),d1=read();
        lim=max(max(c0,c1),max(d0,d1));
        for (re int i=1;i<=n;++i) {
            b[i]=read(),s_school[i]=read();
            sum+=s_school[i],s_school_city[b[i]]+=s_school[i];
        }
        for (re int i=1,k=read();i<=k;++i) {
            int x=read();
            h[x]=read(),mark[b[x]]=1;
        }
        
        f[0]=1;
        for (re int i=1;i<=n;++i) {
            if (~h[i]) continue;
            for (re int j=lim;j>=s_school[i];--j)
                add(f[j],f[j-s_school[i]]);
        }
        for (re int i=1;i<=lim;++i) add(f[i],f[i-1]);

        g[0]=1;
        for (re int i=1;i<=c;++i) {
            if (mark[i]||!s_school_city[i]) continue;
            for (re int j=lim;j>=s_school_city[i];--j)
                add(g[j],g[j-s_school_city[i]]);
        }
        for (re int i=1;i<=lim;++i) add(g[i],g[i-1]);
        
        dp[0][0]=1; int limx=0,limy=0;
        for (re int i=1;i<=c;++i) {
            if (!mark[i]) continue;
            for (re int x=0;x<=limx;++x)
                for (re int y=0;y<=limy;++y)
                    tmp[x][y]=dp[x][y];
            for (re int j=1;j<=n;++j) {
                if (b[j]!=i||h[j]==-1) continue;
                limy=min(limy+s_school[j],lim);
                if (h[j]==1) {
                    for (re int x=0;x<=limx;++x) {
                        for (re int y=limy;y>=s_school[j];--y)
                            dp[x][y]=dp[x][y-s_school[j]];
                        for (re int y=0;y<s_school[j];++y)
                            dp[x][y]=0;
                    }
                }
                if (h[j]>=2) {
                    for (re int x=0;x<=limx;++x)
                        for (re int y=limy;y>=s_school[j];--y)
                            add(dp[x][y],dp[x][y-s_school[j]]);
                }
                if (h[j]==3) {
                    for (re int x=0;x<=limx;++x) {
                        for (re int y=limy;y>=s_school[j];--y)
                            tmp[x][y]=tmp[x][y-s_school[j]];
                        for (re int y=0;y<s_school[j];++y)
                            tmp[x][y]=0;
                    }
                }
                if (h[j]<=1) {
                    for (re int x=0;x<=limx;++x)
                        for (re int y=limy;y>=s_school[j];--y)
                            add(tmp[x][y],tmp[x][y-s_school[j]]);
                }
            }
            limx=min(limx+s_school_city[i],lim);
            for (re int x=limx;~x;--x)
                for (re int y=0;y<=limy;++y) {
                    dp[x][y]=(x>=s_school_city[i])?
                             dp[x-s_school_city[i]][y]:0;
                    add(dp[x][y],tmp[x][y]);
                }
        }
        int ans=0;
        for (re int x=0;x<=limx;++x)
            for (re int y=0;y<=limy;++y)
                add(ans,1ll*dp[x][y]*calc(x,y)%mod);
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 06 月 04 日 11 : 49 AM

发表评论