题解：AT_arc186_a [ARC186A] Underclued

· · 题解

Sol

矩阵上对于行列信息的维护，有一个比较典的转化，即为将矩阵转化为一个二分图，左侧点表示各行，右侧点表示各列，一个节点 (x,y) 在图上可以表示为链接 x,y 的一条连边。

考虑这道题，一个比较巧妙的转化是为 1 点从左侧连向右侧，为 0 点从右侧连向左侧，然后在环中的边，原矩阵上对应点就是不固定的。因为题中的限制在图上可以表示为点的入度不变，那么环换个方向显然可以满足这个限制，且不在环上的边对应点必然是固定的。

不在环上的边不太好做，考虑对在环上的边 DP，每次就枚举这个环左侧点的数量 l 和右侧点的数量 r 即可，且这个新的连通块内新增的 lr 条边必然全在某个环中。然后我们就可以 O(n^6) 暴力 DP 了。

Code

const int N=35;

int n,q,k;
int f[N][N][N*N];

inline void Main(){
    cin>>n>>q;
    rep(i,0,n)rep(j,0,n)f[i][j][0]=1;
    rep(i,2,n)rep(j,2,n)if(i|j)rep(k,2*2,i*j)rep(l,2,i)rep(r,2,j){
        if(l*r>k)break;
        f[i][j][k]|=f[i-l][j-r][k-l*r];
    }
    rep(i,1,q)cin>>k,put(f[n][n][n*n-k]?"Yes":"No");
}