2 条题解

  • 0
    @ 2019-01-24 11:47:23
    /*
    
    */
    #define method_1
    #ifdef method_1
    /*
    
    */
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    #include<string>
    using namespace std;
    typedef long long ll;
    const int maxn=80+1;
    const int maxp=20+1;
    const int INF=0x3f3f3f3f;
    ll getbit(ll x) { //利用计算机补码性质 依次取出x的每一位的1 并且统计1的个数在ans中
        ll ans=0;
        while(x) {
            x-=x&-x;
            ans++;
        }
        return ans;
    }
    /*
    若选择f[i][j][k]表示到第i行第j列选k个有多少种方案,
    那么f[i][j][k] 由f[i-1][j][k1] 和 f[i][j-1][k2]得来,
    但是方阵两两之间不相连,行列之间的状态很难表示,所以选择用二进制表示状态。
    设f[i][j][k] 表示 目前到第i行已选k个,第i行状态为j的方案数,
    显然 j 要满足(j & (j>>1)) 为 0,i行自身的约束考虑好了,但是
    第i行还要受到i-1行的约束,于是我们枚举第i-1行的状态,第i-1
    行与第i行不冲突的条件为(t & (t>>1)) == 0和( t & j) == 0
    (t为第i-1行的状态),然后我们可以得出转移方程:
    f[i][j][k] += f[i-1][t][k-bit[j]](bit[k]为k的二进制中1的个数)
    接下来分析k, k的最大值为2^z-1,z为n,m中较小的数,因为n*m<=80,所以z最大为8而已
    
    */
    ll f[maxn][(1<<12)][maxp],bit[(1<<12)];
    ll c[maxn*maxn][maxp];
    int main() {
        ios::sync_with_stdio(false);
    //  freopen("陇西行四首.in","r",stdin);
        ll n,m,p;
        cin>>p>>n>>m;
        if(n<m) swap(n,m);
        for(ll i=0; i<(1<<m); i++) {
            bit[i]=getbit(i);
        }
        memset(f,0,sizeof(f));
        f[0][0][0]=1;
        ll ans=0;
        for(ll i=1; i<=n; i++) { //按行枚举
            for(ll j=0; j<(1<<m); j++) { //枚举这一行的作弊者放置情况
                for(ll k=0; k<=p; k++) { //枚举当前总共放置的作弊者的数目
                    if(!(j&(j>>1))&&k>=bit[j]) {
                        //枚举这一行的状态
                        //无法作弊 且 这一行放置的作弊者(bit[j])小于总共放置的作弊者数目
                        for(ll t=0; t<(1<<m); t++) { //枚举上一行的状态
                            //if(!(t&(t>>1))&&!(t&j)&&bit[t]<=k-bit[j]){
                            if(!(t&j)) {
                                //上一行不冲突 且 上下两行不冲突 且
                                //上一行放置的作弊者 小于等于 总共放置的作弊者-这一行放置的作弊者
                                f[i][j][k]+=f[i-1][t][k-bit[j]];
                            }
                        }
                    }
                }
            }
        }
        for(ll i=0; i<(1<<m); i++) {
            ans+=f[n][i][p];
        }
        cout<<ans;
        return 0;
    }
    #endif
    #ifdef method_2
    /*
    
    */
    
    #endif
    #ifdef method_3
    /*
    
    */
    
    #endif
    
    
  • -1

    /*

    /
    #define method_1
    #ifdef method_1
    /

    /
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    #include<string>
    using namespace std;
    typedef long long ll;
    const int maxn=80+1;
    const int maxp=20+1;
    const int INF=0x3f3f3f3f;
    ll getbit(ll x) { //利用计算机补码性质 依次取出x的每一位的1 并且统计1的个数在ans中
    ll ans=0;
    while(x) {
    x-=x&-x;
    ans++;
    }
    return ans;
    }
    /

    若选择f[i][j][k]表示到第i行第j列选k个有多少种方案,
    那么f[i][j][k] 由f[i-1][j][k1] 和 f[i][j-1][k2]得来,
    但是方阵两两之间不相连,行列之间的状态很难表示,所以选择用二进制表示状态。
    设f[i][j][k] 表示 目前到第i行已选k个,第i行状态为j的方案数,
    显然 j 要满足(j & (j>>1)) 为 0,i行自身的约束考虑好了,但是
    第i行还要受到i-1行的约束,于是我们枚举第i-1行的状态,第i-1
    行与第i行不冲突的条件为(t & (t>>1)) == 0和( t & j) == 0
    (t为第i-1行的状态),然后我们可以得出转移方程:
    f[i][j][k] += f[i-1][t][k-bit[j]](bit[k]为k的二进制中1的个数)
    接下来分析k, k的最大值为2^z-1,z为n,m中较小的数,因为n*m<=80,所以z最大为8而已

    /
    ll f[maxn][(1<<12)][maxp],bit[(1<<12)];
    ll c[maxn*maxn][maxp];
    int main() {
    ios::sync_with_stdio(false);
    // freopen("陇西行四首.in","r",stdin);
    ll n,m,p;
    cin>>p>>n>>m;
    if(n<m) swap(n,m);
    for(ll i=0; i<(1<<m); i++) {
    bit[i]=getbit(i);
    }
    memset(f,0,sizeof(f));
    f[0][0][0]=1;
    ll ans=0;
    for(ll i=1; i<=n; i++) { //按行枚举
    for(ll j=0; j<(1<<m); j++) { //枚举这一行的作弊者放置情况
    for(ll k=0; k<=p; k++) { //枚举当前总共放置的作弊者的数目
    if(!(j&(j>>1))&&k>=bit[j]) {
    //枚举这一行的状态
    //无法作弊 且 这一行放置的作弊者(bit[j])小于总共放置的作弊者数目
    for(ll t=0; t<(1<<m); t++) { //枚举上一行的状态
    //if(!(t&(t>>1))&&!(t&j)&&bit[t]<=k-bit[j]){
    if(!(t&j)) {
    //上一行不冲突 且 上下两行不冲突 且
    //上一行放置的作弊者 小于等于 总共放置的作弊者-这一行放置的作弊者
    f[i][j][k]+=f[i-1][t][k-bit[j]];
    }
    }
    }
    }
    }
    }
    for(ll i=0; i<(1<<m); i++) {
    ans+=f[n][i][p];
    }
    cout<<ans;
    return 0;
    }
    #endif
    #ifdef method_2
    /

    */

    #endif
    #ifdef method_3
    /*

    */

    #endif

  • 1

信息

难度
8
分类
(无)
标签
(无)
递交数
67
已通过
10
通过率
15%
被复制
5
上传者