[CF1472F] New Year's Puzzle

[CF1472F] New Year's Puzzle

Description

给你一个 (2 imes n) 的长方形，里面有 (m) 的格子被挡住了，可不可以只用 (1 imes 2) 和 (2 imes 1) 的小长方形盖住原来 (2 imes 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();
}