[CF1472F] New Year's Puzzle

Description

给你一个 \(2\times n\) 的长方形，里面有 \(m\) 的格子被挡住了，可不可以只用 \(1\times 2\) 和 \(2\times 1\) 的小长方形盖住原来 \(2\times n\) 的长方形没被挡住的部分。

Solution

首先，连续的空行可以保持奇偶性不变压缩，这样做出一个等效的，\(n \le 2m\) 矩形，转置一下方便处理

设 \(f[i][0]\) 表示前 i 行处理妥善，是否可能

设 \(f[i][1]\) 表示前 i 行处理，剩下 \(a[i][1]\) 没有填充

设 \(f[i][2]\) 表示前 i 行处理，剩下 \(a[i][2]\) 没有填充

如果 \(a[i][1]=0, a[i][2]=0\)，那么 \(0-0,1-2,2-1\)

如果 \(a[i][1]=1, a[i][2]=0\)，那么 \(0-2,2-0\)

如果 \(a[i][1]=0, a[i][2]=1\)，那么 \(0-1,1-0\)

如果 \(a[i][1]=1, a[i][2]=1\)，那么 \(0-0\)

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

#define int long long

#define tr(x, y) f[i][x] |= f[i - 1][y]

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> block;
    map<int, int> mp;
    block.push_back({0, 0});
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        block.push_back({x, y});
        mp[y]++;
    }
    int last = 0;
    int ind = 0;
    for (auto &[x, y] : mp)
    {
        if ((x - last) & 1)
            y = ++ind;
        else
            ++ind, y = ++ind;
        last = x;
    }
    if (last < n)
        ++ind;

    // now: ind * 2
    vector<vector<int>> a(ind + 2, vector<int>(4));
    for (int i = 1; i <= m; i++)
    {
        auto [x, y] = block[i];
        y = mp[y];
        a[y][x] = 1;
    }

    // dp
    vector<vector<int>> f(ind + 2, vector<int>(4));
    f[0][0] = 1;
    for (int i = 1; i <= ind; i++)
    {
        if (a[i][1] == 0 && a[i][2] == 0)
        {
            tr(0, 0);
            tr(1, 2);
            tr(2, 1);
        }
        else if (a[i][1] == 0 && a[i][2] == 1)
        {
            tr(0, 1);
            tr(1, 0);
        }
        else if (a[i][1] == 1 && a[i][2] == 0)
        {
            tr(0, 2);
            tr(2, 0);
        }
        else
        {
            tr(0, 0);
        }
    }

    for (int i = 1; i <= ind; i++)
    {
        // cout << a[i][1] << " " << a[i][2] << endl;
    }

    // cout << endl;

    for (int i = 1; i <= ind; i++)
    {
        // cout << f[i][0] << " " << f[i][1] << " " << f[i][2] << endl;
    }

    // out
    cout << (f[ind][0] ? "YES" : "NO") << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}