<算法进阶指南>题解补全计划—进阶指北
此篇属于
算法进阶指南题解补全计划—进阶指北收录题解
:传送门
进阶指北(1+3) ( 1总体 + 3 函数)
void init_col_valid()
- 这个函数主要判断每一个列状态是否合法
- 即判断每一列的连续0的连续区间,每一个区间0的个数是不是都是偶数
void init_transfer_state()
- 按位
&
== 0 保证了 每一位最多只有一位1 - 按位
|
应该可以换成加法,无妨,他代表了填充状态,并且可以通过查表init_col_valid()
来判断是否合法
按位&
实验
#include<iostream>
#include<deque>
using namespace std;
deque<int> temp;
void pr(int n)
{
temp.clear();
while(n)
{
temp.push_front(n&1);
n >>= 1;
}
for(auto k : temp) cout << k;
cout << endl;
}
int main()
{
int x,y;
cin >> x >> y;
pr(x);pr(y);pr(x&y);
cout << (x&y) << endl;
}
按位|
实验
#include<iostream>
#include<deque>
using namespace std;
deque<int> temp;
void pr(int n)
{
temp.clear();
while(n)
{
temp.push_front(n&1);
n >>= 1;
}
for(auto k : temp) cout << k;
cout << endl;
}
int main()
{
int x,y;
cin >> x >> y;
pr(x);pr(y);pr(x|y);
cout << (x|y) << endl;
}
void solve()
- 状态转移,在前面详细讲了,看一眼就能看懂。
code
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 12,M = 1 << N;
int n,m;
LL f[N][M];
vector<int> state[M];
bool st[M];
void init_col_valid()
{
for(int i = 0;i < 1 << n;i ++)
{
int cnt = 0;
bool is_valid = true;
for(int j = 0;j < n;j ++)
if(i >> j & 1)
{
if(cnt & 1)
{
is_valid = false;
break;
}
cnt = 0;
}
else cnt ++ ;
if(cnt & 1) is_valid = false;
st[i] = is_valid;
}
}
void init_transfer_state()
{
for(int i = 0;i < 1 << n;i ++)
{
state[i].clear();
for(int j = 0;j < 1 << n;j ++)
if((i & j) == 0 && st[i|j])
state[i].push_back(j);
}
}
void solve()
{
memset(f,0,sizeof f);
f[0][0] = 1;
for(int i = 1;i <= m;i ++)
for(int j = 0;j < 1 << n;j ++)
for(auto k : state[j])
f[i][j] += f[i-1][k];
}
int main()
{
while(cin >> n >> m, n || m)
{
init_col_valid();
init_transfer_state();
solve();
cout << f[m][0] << endl;
}
return 0;
}