破坏正方形问题

解题思路

我们需要求出至少还要去掉几根火柴，使得图中不存在任何正方形。

本题可以看作一个重复覆盖问题来做，而做一个重复覆盖问题只需要套 $Dancing~Links$ 的模板就能做，因此我们现在需要将原问题转化成一个重复覆盖问题。

首先考虑行，也就是选法，显然这里可以选择将哪根火柴去掉，因此行对应的是火柴。

然后考虑列，也就是限制，而当某个火柴被去掉时，他会破坏掉很多正方形，因此列就对应到正方形。此时每列至少有一个 $1$ 就表示每个正方形至少去掉一根火柴。

而行和列怎么去对应呢，我们可以看一下当某个火柴被去掉时，他会破坏哪些正方形，那么我们就在这个火柴所在的行中，将它会破坏的正方形所在的列记上一个 $1$。到此原问题就被我们转化成了一个重复覆盖问题。

这题的转化比较直观，原问题的任意一个方案和重复覆盖问题的任意一个方案也是一一对应的，然后只需要将十字链表建出来，然后跑一遍重复覆盖问题的 $dfs$ 模板即可。

这里另一个难点就是建图比较麻烦，要想建图就需要给所有正方形编号，这里可以依次枚举边长为 $i$ 的正方形来进行编号。而对于每个正方形，我们还需要找出构成它的所有火柴的编号，这就非常恶心。这里需要对于每个边长为 $i$ 的正方形去寻找规律，总结公式来快速找出所有边。

C++ 代码

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 3600;

int n, m;
//l[i] 表示节点 i 的左节点
//r[i] 表示节点 i 的右节点
//u[i] 表示节点 i 的上节点
//d[i] 表示节点 i 的下节点
//s[i] 表示第 i 列中 1 的个数
//row[i] 表示节点 i 所在的行的编号
//col[i] 表示节点 i 所在的列的编号
int l[N], r[N], u[N], d[N], s[N], row[N], col[N], idx;
bool st[60]; //判重数组
vector<int> square[60]; //存储每个正方形包含的所有边的编号

void init() //初始化十字链表
{
    for(int i = 0; i <= m; i++)
    {
        l[i] = i - 1, r[i] = i + 1;
        col[i] = u[i] = d[i] = i;
        s[i] = 0;
    }
    l[0] = m, r[m] = 0;
    idx = m + 1;
}

void add(int &hh, int &tt, int x, int y) //将 (x, y) 加入 hh 和 tt 之间
{
    row[idx] = x, col[idx] = y, s[y]++;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = idx, l[tt] = idx, r[idx] = tt, l[idx] = hh;
    tt = idx++;
}

int h() //估价函数
{
    int cnt = 0;
    memset(st, 0, sizeof st);
    for(int i = r[0]; i; i = r[i])
    {
        if(st[i]) continue;
        st[i] = true;
        cnt++;
        for(int j = d[i]; j != i; j = d[j])
            for(int k = r[j]; k != j; k = r[k])
                st[col[k]] = true;
    }
    return cnt;
}

void remove(int p)
{
    for(int i = d[p]; i != p; i = d[i])
    {
        r[l[i]] = r[i];
        l[r[i]] = l[i];
    }
}

void resume(int p)
{
    for(int i = u[p]; i != p; i = u[i])
    {
        r[l[i]] = i;
        l[r[i]] = i;
    }
}

bool dfs(int k, int depth) //迭代加深
{
    if(k + h() > depth) return false;
    if(!r[0]) return true;

    int p = r[0];
    for(int i = r[0]; i; i = r[i])
        if(s[i] < s[p])
            p = i;

    for(int i = d[p]; i != p; i = d[i])
    {
        remove(i);
        for(int j = r[i]; j != i; j = r[j]) remove(j);
        if(dfs(k + 1, depth)) return true;
        for(int j = l[i]; j != i; j = l[j]) resume(j);
        resume(i);
    }
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);

        memset(st, 0, sizeof st);

        int cnt;
        scanf("%d", &cnt);
        while(cnt--)
        {
            int x;
            scanf("%d", &x);
            st[x] = true; //标记所有缺失的火柴
        }

        m = 0; //记录正方形的数量（行数）
        for(int len = 1; len <= n; len++) //枚举边长
            for(int a = 1; a + len - 1 <= n; a++) //枚举行偏移量
                for(int b = 1; b + len - 1 <= n; b++) //枚举列偏移量
                {
                    auto &sq = square[++m];
                    sq.clear();
                    int d = 2 * n + 1;
                    //找出当前正方形的所有边
                    for(int i = 0; i < len; i++)
                    {
                        sq.push_back((a - 1) * d + b + i); //上边
                        sq.push_back((a - 1) * d + b + i + d * len); //下边
                        sq.push_back((a - 1) * d + b + n + d * i); //左边
                        sq.push_back((a - 1) * d + b + n + d * i + len); //右边
                    }

                    //判断当前正方形的所有边是否存在
                    for(int i = 0; i < sq.size(); i++)
                        if(st[sq[i]]) //如果当前正方形某条边缺失，则正方形数量 - 1
                        {
                            m--;
                            break;
                        }
                }

        init(); //初始化十字链表

        //建出每一行
        for(int i = 1; i <= n * (n + 1) * 2; i++)
            if(!st[i]) //如果当前边存在，则建出一行
            {
                int hh = idx, tt = idx;
                for(int j = 1; j <= m; j++) //枚举所有正方形
                {
                    auto sq = square[j];
                    if(find(sq.begin(), sq.end(), i) != sq.end()) //如果当前正方形包含当前边，则加入节点
                        add(hh, tt, i, j);
                }
            }

        //迭代加深
        int depth = 0;
        while(!dfs(0, depth)) depth++;
        printf("%d\n", depth);
    }
    return 0;
}