[状压dp] [小清新] P7732 题解

· · 题解

题意

给定一棵树，每个点有 0/1 两状态。每个时刻可以选择一点翻转颜色，并在下个时刻把“翻转”传递到父亲，两个“翻转”同时在一起会抵消。

给定初始状态，求最少第几时刻可以抵达目标状态？

思路

写的比较详细，希望能讲明白。

看到数据范围，优先考虑状压 \rm dp。但是朴素写法需记录 每个点的颜色 和 还在传递的点，显然不对。

先把初始状态和目标状态异或一下得到操作序列 C，那么题意可以转化为 初始全为 0 需抵达 C 状态。这是为了方便下文讨论。

直观地想，答案应该不会太大。事实正是如此：考虑把 C 放在树上，那么一定可以将其划分为 \le \frac n2 个连续全 1 链，并且互不相交。对于每一段，只需在起点和终点的父亲上操作即可。所以答案必定 \le n。

然后考虑加上 时间 这一维。发现固定结束时间后便容易得到：每个点在某个时刻进行操作，最终所改变颜色的点集。

换句话说，可以考虑将每个点被操作后的影响直接加入状态中。

于是定义 f_{i,S} 表示到第 i 秒，点的颜色状压为 S，是否可行？

于是成功省掉了 还在传递的点 这一维。可是又发现，直接枚举被操作的点、操作的时间，还是会超时，不太可做的亚子。

然鹅有个神仙想法：转移时，直接让 1 到 i 的所有操作延迟一秒进行，不难发现对 S 没有影响。然后枚举点，并使其在 1 时刻进行操作。可以发现这样恰好能遍历完所有的可能情况。

然后需要开一个辅助数组 s_{i,j} 表示第 i 点在 1 时刻操作、结束时间为 j 时，被改变颜色的点集，可以预处理出来。

转移方程为：

  1. 啥也不干：f_{i,S}\to f_{i+1,S}
  2. 进行操作：f_{i,S}\to f_{i+1,S\bigoplus s_{j,i+1}}

复杂度 O(qn^2 2^n)，实际上跑不满，可以通过此题。我的辣鸡程序跑的最慢的点约为 1.5s。

代码

好像没啥好说的。

#include<bits/stdc++.h>
using namespace std; 

int q, n, u, v, fa[22], s[22][22], beg, lst;
char c[22];
bool f[22][1 << 20];

int main(){

    cin >> q;
    while(q--){
        scanf("%d %s", &n, c + 1);

        beg = lst = 0;
        for(int i = 0; i <= n;++i){ //最好别用memset 
            fa[i] = 0;
            for(int S = 0; S < 1 << n;++S) f[i][S] = false;
        }

        for(int i = 1; i <= n;++i) beg |= (c[i] == 'R') * (1 << i - 1);
        for(int i = 1; i < n;++i) scanf("%d %d", &u, &v), fa[v] = u;
        scanf("%s", c + 1);
        for(int i = 1; i <= n;++i) lst |= (c[i] == 'R') * (1 << i - 1);

        for(int i = 1; i <= n;++i)
            for(int j = 1, u = i; j <= n;++j, u = fa[u]) 
                if(u) s[i][j] = s[i][j - 1] | (1 << u - 1);
                else s[i][j] = s[i][j - 1];  

        f[0][beg] = true;
        for(int i = 0; i <= n;++i)
            if(f[i][lst]) {printf("%d\n", i); break;}
            else{
                for(int S = 0; S < 1 << n;++S)
                    if(f[i][S]){
                        f[i + 1][S] = true;
                        for(int j = 1; j <= n;++j)
                            f[i + 1][S ^ s[j][i + 1]] = true;
                    }
            }
    } 
    return 0;
}