【序】
由于昨天大佬讲课，很多人没来，在做完这个训练，我希望用我自己的粗浅理解能够帮到大家，还有训练已经过去几天了，也希望大家抓紧时间去完成这个专题训练，不然这个专题就开得毫无意义了。然后下面的题解我会细致的讲解题目的解法，以及我是如何理解这道题，争取大家都可以很快的看懂。
【正文】 题目传送门：点击打开链接
【A】 题意为给了1个H*W的方格矩阵，然后要我们用1*2小矩形去填满这个大矩形，最后要问填满这个大矩形的方法总数。解题方法：数据范围非常小，我们大概确定这个题可以状压了。我们用2进制的0,1表示一个格子是否放了。我们发现第i行的状态只会和第i-1行有关，所以我枚举 i-1行的每个状态，推出由此状态可以达到的第i行状态，如果i-1行的出发状态某处没有放，必然要在第i行放一个竖的方块，所以这里对上一行的状态按位取反之后的状态机就是放了 竖方块的状态。然后我们DFS扫一道在i行横着的方块的所有可能，并且把这些状态累加上i-1的出发状态的方法数就可以了。下面来个例子：
2 4
1111
1111
状态可以由
1100 0000 0110 0011 1111
0000 0000 0000 0000 0000
这五种i-1的状态达到，故2 4 的答案为5代码如下：
int n, m;
long long dp[12][1<<11], pre; //dp[i][j]第i行状态为j
void dfs(int r, int sta, int pos)//行r,当前状态sta,当前位置pos
{
if(pos >= m){
dp[r][sta] += pre;//i-1行的出发状态的方案数
return ;
}
dfs(r, sta, pos + 1);
if(pos <= m - 2 && !(sta & 1 << pos) && !(sta & 1 << pos+1)){
dfs(r, sta | 1<<pos | 1<<pos + 1, pos + 2);
}
}
int main()
{
while(scanf("%d%d",&n,&m) != EOF)
{
if(n == 0 && m == 0) break;
memset(dp, 0, sizeof(dp));
pre = 1;
dfs(1, 0, 0);
for(int i = 2; i <= n; i++){
for(int j = 0; j < 1<<m; j++){
pre = dp[i-1][j];
dfs(i, ~j&((1<<m) - 1), 0); //先和（1<<(m)-1）相与，保证只有m位二进制
}
}
printf("%lld\n", dp[n][(1<<m)-1]);
}
return 0;
}【B】题意为一个N*M的矩阵，其中N<=150,M<=10，矩阵中有K个坏点，芯片不能放在上面，现在要用一些2*3的芯片来填充这个矩阵，问最多可以使用用多少个这样的芯片？解题方法：由于芯片大小是2*3的，意思就是当前行的状态不仅和上一行有关并且也和上上行相关？那么这个状态用什么来表示比较好呢？2进制？可以，但是想想二进制在这里 的判断感觉要写个几十排，不太好。那么3进制呢？下面我们假设用三进制表示，来试一下状态合法性的判断会不会很简单。
由于芯片长度只有 3， 所以第 x 行芯片的放置只受 x-1行 和 x-2 行放置情况的影响。
同时由于一旦 方格 （x-1, y）被黑色记号或其他芯片 占据，则方格（x-2,y）即便空闲对第 x行芯片的放置也毫无意义。
所以，只需记录的状态只有：
一， a[x] = 0 表示方格（x-1,y）空闲，方格（x-2,y）空闲
二， a[x] = 1 表示方格（x-1,y）空闲，方格（x-2,y）被占据
三， a[x] = 3, 表示方格（x-1,y）被占据
意味着对于 I 层， 其状态 J， 保存着 I，I-1 层 芯片的放置方法，
所以我们通过 dp（I，J）更新 I+1 层时，同样要更新 I+1 的状态信息 K， 其保存着 I+1， I层信息
状态 dp（i,j）表示 前 i 层 状态为 J 的最大芯片数量
情况一， 当前列y 不放，从 y+1 列开始考虑
情况二， 当前两列 ( y, y+1 ) 合法，放 3*2 芯片， 更新 I+1层状态 ， 再去考虑 y+2列
情况三， 当前三列（y,y+1,y+2）合法，放 2*3 芯片， 更新 I+1 层状态，再去考虑 y+3列
然后我们再来计算一下空间复杂度，3^10 * 150 毫无疑问的炸掉了，然后这里当然就考虑用滚动数组来优化空间了。另，处理列的组合问题需要 递归DFS，通过回溯来解决。 另外，对于黑点，我们其实可以合并到 芯片占据的类型中去，而不需要单独处理，这样就能同过 I层的放置序列 P（p1,p2,...,pm），I+1层的放置序列Q（Q1，Q2，。。，Qm），来决策了。
int vis[155][11];
int dp[2][maxn], A[11], P[11], Q[11];
int n, m, K, mask;
int bianma(int f[]){ //编码
int res = 0;
for(int i = 1; i <= m; i++){
res += (f[i] * A[i - 1]);
}
return res;
}
void jiema(int x, int f[]){ //解码
for(int i = 1; i <= m; i++){
f[i] = x % 3;
x /= 3;
}
}
void dfs(int i, int x, int num) //第i行，x列，数量为num
{
if(x > m) return;
int cur = (i + 1) & 1, nxt = i & 1, k = bianma(Q);
dp[nxt][k] = max(dp[nxt][k], dp[cur][bianma(P)]);
if((x <= (m - 1)) && ((P[x] == 0) && (P[x + 1] == 0)) && ((Q[x] == 0) && (Q[x + 1] == 0))){
Q[x] = Q[x + 1] = 2;
int kk = bianma(Q);
dp[nxt][kk] = max(dp[nxt][kk], num + 1);
dfs(i, x + 2, num + 1);
Q[x] = Q[x + 1] = 0;
}
if((x <= (m - 2)) && (P[x] <= 1) && (P[x + 1]) <= 1 && P[x + 2] <= 1 && Q[x] == 0 &&Q[x + 1] == 0 && Q[x + 2] == 0){
Q[x] = Q[x + 1] = Q[x + 2] = 2;
int kk = bianma(Q);
dp[nxt][kk] = max(dp[nxt][kk], num + 1);
dfs(i, x + 3, num + 1);
Q[x] = Q[x + 1] = Q[x + 2] = 0;
}
dfs(i, x + 1, num);
}
int main()
{
A[0] = 1;
for(int i = 1; i <= 10; i++) A[i] = A[i - 1] * 3;
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &m, &K);
memset(vis, 0, sizeof(vis));
for(int i = 0; i < K; i++){
int x, y;
scanf("%d%d", &x, &y);
vis[x][y] = 1;
}
memset(dp, -1, sizeof(dp));
memset(P, 0, sizeof(P));
memset(Q, 0, sizeof(Q));
for(int i = 1; i <= m; i++){
P[i] = vis[1][i] + 1;
}
mask = A[m];
dp[1][bianma(P)] = 0;
for(int i = 2; i <= n; i++){
int cur = (i + 1) & 1, nxt = i & 1;
memset(dp[nxt], -1, sizeof(dp[nxt]));
for(int j = 0; j < mask; j++){
if(dp[cur][j] == -1) continue;
jiema(j, P);
for(int x = 1; x <= m; x++){
if(vis[i][x]) Q[x] = 2;
else{
Q[x] = P[x] - 1;
if(Q[x] < 0) Q[x] = 0;
}
}
dfs(i, 1, dp[cur][j]);
}
}
int ans = 0;
for(int i = 0; i < mask; i++){
ans = max(ans, max(dp[0][i], dp[1][i]));
}
printf("%d\n", ans);
}
return 0;
}
【C】题意为一开始棋盘上布满蜘蛛，可以安排每个蜘蛛想邻近的四个方向走，一秒走一次，问一秒以后空格最多有多少。这道题算是这套题最简单的了，很容易想到用dp[i][j][k]来表示当前行为i,状态为j,下一行状态为k的最大空格数。
还有一个问题是判断冲突，如何判断呢？
bool f(int x, int y, int z)
{
//return (((x|y|z|(y<<1)|(y>>1))&((1<<m)-1)) == ((1<<m)-1));
int s = x|y|z|(y<<1)|(y>>1);
int t = (1<<m) - 1;
if((s & t) == t) return true;
else return false;
}能理解吗？其实就是把当前状态退会到移动之前的状态一的二进制定是m个1对吧，就是这个原理。
状态转移部分如下：
memset(num, 0, sizeof(num));
// memset(dp, 0, sizeof(dp));
int sta = 1<<m;
REPZ(i, n){
REP(j, sta){
REP(k, sta){
dp[i][j][k] = -inf;
}
}
}
REP(i, sta){
dp[0][0][i] = 0;
num[i] = m - __builtin_popcount(i);
}
REP(i, n){//枚举行
REP(j, sta){ //当前行状态
REP(k, sta){//下一行状态
REP(l, sta){//下下行状态
if(f(j, k, l)){
dp[i+1][k][l] = max(dp[i+1][k][l], dp[i][j][k] + num[k]);
}
}
}
}
}
int ans = 0;
REP(i, sta){
ans = max(ans, dp[n][i][0]);
}
printf("%d\n", ans);【D】倒是觉得这题和这个专题没多大关系，仅仅就是个或运算而已。说下题意吧，就是现在有一颗树有两个操作，把节点i的子树染成某一种颜色c,还有一种是查询一个点的子树有多少种颜色？ 就是把区间染色问题搬到了树上而已，我们只需要处理这颗树每个节点的DFS序就可以转化成区间染色问题了，这里颜色有60种，可以LL表示，我依靠自己习惯，随手压了个bitset，不过代码会稍微长一点，不过花点时间就可以了，没有难度。
代码如下：
int n, q, col[maxn];
vector <int> G[maxn];
//处理DFS序
int st[maxn], en[maxn], dfn;
void dfs(int u, int fa)
{
st[u] = ++dfn;
for(int i = 0; i < (int)G[u].size(); i++){
int v = G[u][i];
if(v == fa) continue;
dfs(v, u);
}
en[u] = dfn;
}
//定义线段树节点
struct node{
int l, r, lazy;
bitset <61> c;
node(){}
node(int l, int r):l(l), r(r){c.reset();}
void SetColor(int col){
c.reset();
c[col] = 1;
}
}T[maxn * 4];
//线段树部分
node operator+(node a, node b){
node ret(a.l, b.r);
ret.c = a.c | b.c;
return ret;
}
void pushup(int rt){
T[rt].c = T[rt*2].c | T[rt*2+1].c;
}
void pushdown(int rt){
if(T[rt].lazy){
T[rt*2].SetColor(T[rt].lazy);
T[rt*2+1].SetColor(T[rt].lazy);
T[rt*2].lazy = T[rt*2+1].lazy = T[rt].lazy;
T[rt].lazy = 0;
}
}
void Build(int l, int r, int rt)
{
T[rt].l = l, T[rt].r = r, T[rt].lazy = 0;
if(l == r){ return ;}
int mid = (l + r) / 2;
Build(l, mid, rt*2);
Build(mid+1, r, rt*2+1);
}
void update(int L, int R, int c, int rt)
{
if(L == T[rt].l && R == T[rt].r){
T[rt].lazy = c;
T[rt].SetColor(c);
return ;
}
pushdown(rt);
int mid = (T[rt].l + T[rt].r) / 2;
if(R <= mid) update(L, R, c, rt*2);
else if(L > mid) update(L, R, c, rt*2+1);
else{
update(L, mid, c, rt*2);
update(mid+1, R, c, rt*2+1);
}
pushup(rt);
}
node queryans(int L, int R, int rt)
{
if(L == T[rt].l && R == T[rt].r){
return T[rt];
}
pushdown(rt);
int mid = (T[rt].l + T[rt].r) / 2;
if(R <= mid) return queryans(L, R, rt*2);
else if(L > mid) return queryans(L, R, rt*2+1);
else{
return queryans(L, mid, rt*2) + queryans(mid + 1, R, rt*2+1);
}
}
int main()
{
int n, q;
while(scanf("%d%d", &n, &q) != EOF)
{
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 1; i <= n; i++) scanf("%d", &col[i]);
Build(1, n, 1);
for(int i = 1; i < n; i++){
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfn = 0;
dfs(1, -1);
for(int i = 1; i <= n; i++){
update(st[i], st[i], col[i], 1);
}
while(q--)
{
int op, x, y;
scanf("%d", &op);
if(op == 1)
{
scanf("%d%d", &x, &y);
update(st[x], en[x], y, 1);
}
else
{
scanf("%d", &x);
node ans = queryans(st[x], en[x], 1);
int sum = ans.c.count();
printf("%d\n", sum);
}
}
}
return 0;
}【E】状压+二分好题。大佬昨天讲得很清楚了。把他的方法再复述一次，首先题意是：给你一个长度为N的一个序列，需要我们找到一个最长的序列，保证每个元素(1~8)的个数之前的绝对值差小于等于1，而且对应选出来的序列中，需要保证相同的元素是连续的。解题方法：copy from:点击打开链接 感谢。
1、首先我们很容易想到状压，我们肯定是状压8个数字的状态，其中1表示这个位子上的数已经选完了，0表示没有选完，那么我们在想dp数组的维度的时候，以及初算时间复杂度的时候，发现这个出现的次数一直是一个很难处理的点，那么我们首先对这个出现的次数进行优化：
①我们可以通过枚举来dp，每次枚举一个出现的次数，进行最大值的维护 ，我们不难想到：对应这个出现的次数越多，结果就可能越长，那么其具有单调性。
②对于可以枚举的具有单调性存在的变量，我们可以通过二分查找来进行优化。
2、那么我们每一次二分枚举出的当前值mid，表示本次二分枚举出来每个数将要出现的次数。
①对于当前值mid，每种数字出现的次数要么是mid次，要么是mid-1次。
②考虑dp，我们设定dp【i】【j】表示dp过程进行到第i位，对应j状态下的最多出现mid次的数字的个数。
③那么考虑状态转移方程：
如果我们直接暴力的话肯定时间复杂度是吃不消的，那么我们考虑调用一个vector<int >mp；mp【i】用于存储数字i出现的各个位子，我们按照升序排列存储。
然后状态转移见下面：
④维护好每次二分情况的最大值即可。
代码如下：
int n, ans, a[maxn], cur[10], dp[maxn][1<<8];//状态里面0的个数代表长度为len+1的个数
vector <int> v[maxn];
bool check(int len){
int mask = 1<<8;
for(int i = 1; i <= 8; i++) cur[i] = 0;
memset(dp, -1, sizeof(dp));
dp[1][0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < mask; j++){
if(dp[i][j] < 0) continue;
for(int k = 1; k <= 8; k++){
if(j & 1<<(k-1)) continue;
if(cur[k] + len - 1 > (int)v[k].size()) continue;
dp[v[k][cur[k] + len - 2]][j | (1<<(k-1))] = max(dp[v[k][cur[k] + len - 2]][j | (1<<(k-1))], dp[i][j]);
if(cur[k] + len > (int)v[k].size()) continue;
dp[v[k][cur[k] + len - 1]][j | (1<<(k-1))] = max(dp[v[k][cur[k] + len - 1]][j | (1<<(k-1))], dp[i][j] + 1);
}
}
cur[a[i]]++;
}
int sum = -1;
for(int i = 1; i <= n; i++){
sum = max(sum, dp[i][(1<<8) - 1]);
}
if(sum <= 0) return false;
ans = max(ans, sum * len + (8 - sum) * (len - 1));
return true;
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= 8; i++) v[i].clear();
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
v[a[i]].push_back(i);
}
int l = 2, r = n;
ans = 0;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid) > 0) {
l = mid + 1;
}
else{
r = mid - 1;
}
}
if(ans == 0){
for(int i = 1; i <= 8; i++) if(v[i].size() > 0) ans++;
}
printf("%d\n", ans);
}
return 0;
}【F】经典开关灯问题。题意就是有一个n*m的矩形，里面有n*m颗灯，现在问能否找到一个最佳方案使得所有的灯都被关掉，注意一个灯被关掉，则他上下左右的灯都亮了，如果这个题不会做，只能说你这的POWER OJ真的白刷了，因为上面有一个和这个一样的题目。那么我来考虑一下这个题怎么做吧，这题最重要的是要发现一个规律，就是如果你确定了第一行的状态，接下来m-1行的状态都可以递推出来。然后这个题还要求字典序最小的方案，状态直接从小到大枚举，本身就保证了这个特性，所以这个说和不说也差不多吧。
代码如下：
int n, m, step;
int maze[16][16], b[16][16], ans[16][16];
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
bool check(int x, int y)
{
if(x > -1 && y > - 1) return true;
else return false;
}
void press(int i, int j)
{
++step;
ans[i][j] = 1;
b[i][j] = !b[i][j];
REP(k, 4){
int dx = i + dir[k][0];
int dy = j + dir[k][1];
if(check(dx, dy)){
b[dx][dy] ^= 1;
}
}
}
bool f(int sta){
step = 0;
REP(i, n){
REP(j, m){
b[i][j] = maze[i][j];
}
}
REP(i, m){
if(sta & (1<<i)){
press(0, i);
}
}
REPZ(i, n){
REP(j, m){
if(b[i-1][j]){
press(i, j);
}
}
}
REP(i, m){
if(b[n-1][i]){
return false;
}
}
return true;
}
int main()
{
while(scanf("%d%d", &n,&m) != EOF)
{
REP(i, n){
REP(j, m){
scanf("%d", &maze[i][j]);
}
}
int sum = 0x3f3f3f3f, nexcur = -1;
REP(i, 1<<m){
if(f(i) && step < sum){
sum = step;
nexcur = i;
}
}
memset(ans, 0, sizeof(ans));
if(nexcur == -1){
printf("IMPOSSIBLE\n");
}
else{
f(nexcur);
REP(i, n){
REP(j, m){
if(j == m - 1) printf("%d\n", ans[i][j]);
else printf("%d ", ans[i][j]);
}
}
}
}
return 0;
}【G】已经写过了，就不写了，顺便说一下，这个题也可以用3进制压缩，方法和B的方法完全一样，代码长度可能稍微长一些，贴一个之间的解题链接： 点击打开链接
【后记】写到这里，这个专题就写完了，对于刚学的确有一定难度，不过死活把他啃下去之后，你会发现其实状压也不过如此。然后还有什么问题，和不懂的欢迎交流。我自己还有一套状压的训练计划，有余力的可以留言。
京公网安备 11010502036488号