2 条题解
-
0yejun LV 10 MOD @ 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
-
-12021-03-13 13:56:12@
/*
/
#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
- 上传者