I - Union 2019ccpc女生赛

这是2019女生赛最难的一个题目，但是现在去写，我觉得没有想象之中的那么难。

把这个题目分成几个部分来考虑。

假设给你k个数，让你分成三个集合，满足这四个条件，且不需要考虑时间和空间的复杂度。

那么这个是不是就是一个8维的 \(dp\)

dp[i][j][x1][x2][x3][x4][x5][x6] 表示有三个集合i个不同的数，三个集合的数加起来是等于j。

第一个集合有x1个不同的数，第二个集合有x2个不同的数，第三个集合有x3个不同的数

第一个和第二个集合并起来有x4个不同的数，第二个和第三个并起来有x5个不同的数

第一个和第三个集合并起来有x6个不同的数。

这样其实就是让你划分这k个数到三个集合中满足条件的方案数。

这个朴素的写法是不是还比较简单而且好写。

但是如果开8个维度都是50这么大肯定是会爆空间而且时间也过不去。
仔细分析发现其实这个可以分成四类，第一类就是等于0，第二类等于1，第三类等于2，第四类大于等于3。
\(dp\) 的转移有7种转移方式，而且用刷表法进行转移，则对于一个状态，它转移到的7个状态都互不相同。
所以前三类还是正常转移，对于第四类其实可以一起转移，这是因为大于等于三的每一个状态肯定都要向上转移一次，而且转移到的状态都是一样的，所以这个时候可以同时转移，也只转移了一次，不会出现重复。

//朴素写法

int main(){

    init();

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=1;i<=7;i++) scanf("%d",&a[i]);

     dp[0][0][0][0][0][0][0][0]=1;

    for(int i=0;i<k;i++)

    for(int j=i;j<k;j++)

    for(int a=0;a<k;a++)

    for(int b=0;b<k;b++)

    for(int c=0;c<k;c++)

    for(int d=0;d<k;d++)

    for(int e=0;e<k;e++)

    for(int f=0;f<k;f++){

    	if(j!=a+b+c) continue;

        ll cur=dp[i][j][a][b][c][d][e][f];

        dp[i+1][j+1][3,a+1][b][c][3,d+1][e][3,f+1]+=cur;

        dp[i+1][j+1][a][b+1][c][d+1][e+1][f]+=cur;

        dp[i+1][j+1][a][b][c+1][d][e+1][f+1]+=cur;

        dp[i+1][j+2][a+1][b+1][c][d+1][e+1][f+1]+=cur;

        dp[i+1][j+2][a][b+1][c+1][d+1][e+1][f+1]+=cur;

        dp[i+1][j+2][a+1][b][c+1][d+1][e+1][f+1]+=cur;

        dp[i+1][j+3][a+1][b+1][c+1][d+1][e+1][f+1]+=cur;

    }

    ll ans=0;

    for(int i=a[7];i<=k;i++)

    for(int x=a[1];x<=k;x++)

    for(int y=a[2];y<=k;y++)

    for(int z=a[3];z<=k;z++)

    for(int b=a[4];b<=k;b++)

    for(int c=a[5];c<=k;c++)

    for(int d=a[6];d<=k;d++){

        if(x+y+z!=k) continue;

        ll cur=dp[i][k][x][y][z][b][c][d];

//        if(cur) printf("i=%d x=%d y=%d z=%d b=%d c=%d d=%d %lld\n",i,x,y,z,b,c,d,cur);

        ans=(ans+dp[i][k][x][y][z][b][c][d]*C[n][i]);

    }

    printf("%lld\n",ans);

}

优化之后的方法

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

const int mod=1e9+7;

typedef long long ll;

ll dp[55][55][4][4][4][4][4][4];

/*

    dp[i][j][x1][x2][x3][x4][x5][x6] 表示有三个集合i个不同的数，三个集合的数加起来是等于j。

    第一个集合有x1个不同的数，第二个集合有x2个不同的数，第三个集合有x3个不同的数

    第一个和第二个集合并起来有x4个不同的数，第二个和第三个并起来有x5个不同的数

    第一个和第三个集合并起来有x6个不同的数。

    所以对于新增加一个数，那么它可能在 A,B,C,AB,AC,BC,ABC

    dp[i+1][j+1][x1+1][x2][x3][x4+1][x5+1][x6]+=1

    现在重新对dp进行定义

    dp[i][j][x1][x2][x3][x4][x5][x6]

    表示有i个不同的数字，三个集合的和是j

*/

ll C[maxn][55];

ll init(){

    for(int i=0;i<maxn;i++){

        C[i][0]=1;

        for(int j=1;j<=min(i,50);j++){

            C[i][j]=C[i-1][j]+C[i-1][j-1];

        }

    }

}

int a[10];

int main(){

    init();

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=1;i<=7;i++) scanf("%d",&a[i]);

    dp[0][0][0][0][0][0][0][0]=1;

    for(int i=0;i<k;i++)

    for(int j=i;j<k;j++)

    for(int a=0;a<=3;a++)

    for(int b=0;b<=3;b++)

    for(int c=0;c<=3;c++)

    for(int d=0;d<=3;d++)

    for(int e=0;e<=3;e++)

    for(int f=0;f<=3;f++){

        ll cur=dp[i][j][a][b][c][d][e][f];

        dp[i+1][j+1][min(a+1,3)][b][c][min(d+1,3)][e][min(f+1,3)]+=cur;

        dp[i+1][j+1][a][min(b+1,3)][c][min(d+1,3)][min(3,e+1)][f]+=cur;

        dp[i+1][j+1][a][b][min(3,c+1)][d][min(3,e+1)][min(3,f+1)]+=cur;

        dp[i+1][j+2][min(3,a+1)][min(3,b+1)][c][min(3,d+1)][min(3,e+1)][min(3,f+1)]+=cur;

        dp[i+1][j+2][a][min(3,b+1)][min(3,c+1)][min(3,d+1)][min(3,e+1)][min(3,f+1)]+=cur;

        dp[i+1][j+2][min(3,a+1)][b][min(3,c+1)][min(3,d+1)][min(3,e+1)][min(3,f+1)]+=cur;

        dp[i+1][j+3][min(3,a+1)][min(3,b+1)][min(3,c+1)][min(3,d+1)][min(3,e+1)][min(3,f+1)]+=cur;

    }

    ll ans=0;

    for(int i=a[7];i<=k;i++)

    for(int x=a[1];x<=3;x++)

    for(int y=a[2];y<=3;y++)

    for(int z=a[3];z<=3;z++)

    for(int b=a[4];b<=3;b++)

    for(int c=a[5];c<=3;c++)

    for(int d=a[6];d<=3;d++){

        ans=(ans+dp[i][k][x][y][z][b][c][d]*C[n][i])%mod;

    }

    printf("%lld\n",ans);

}

巴特西

I - Union 2019ccpc女生赛

最新文章

热门文章