题解：P12549 [UOI 2025] Gift for Anton

Forget_Everything · 2025-05-19 21:12:23 · 题解

P12549 [UOI 2025] Gift for Anton

好玩诈骗构造，抢个首发题解。

虽然但是，是蓝我吃。

Problem

构造一个 n \times m 的矩阵，使得矩阵中 0 旁边没有 1，1 旁边有 1 个 1，2 旁边有 2 个 2，3 旁边有 3 个 3，4 旁边有 4 个 4。

Solution

诈骗题。

我在纸上画了好久得出一个结论：不存在一个局部图形可以使得 3 旁边有 3 个 3，4 旁边有 4 个 4。

这个也比较好想，因为这个你画着画着就会发现它一直会多出来一块不符合条件的。

所以题意转化为：构造一个 n \times m 的矩阵，使得矩阵中 0 旁边没有 1，1 旁边有 1 个 1，2 旁边有 2 个 2。

这个就比较好做了，先考虑构造一个可以拼起来且符合条件的，不难想到下面这种。

原谅一下我不太会使用公式表示这个矩阵，直接用图片了。

画出这个东西之后，把它自己拼到它的上下左右都是合法的，所以 n,m 均为 3 的倍数的时候就做完了，我们称拼到现在为止的东西为标准矩阵。

考虑推广正解，我直接考虑大力分讨 n,m 除以 3 的余数，为方便讲解，接下来令 a 表示 n 除以 3 的余数，b 表示 m 除以 3 的余数。

• 当 a=1,b=0 时，在标准矩阵下面横着放若干个 1 1 0 即可。

• 当 a=2,b=0 时，在标准矩阵上面横着放若干个两行的 2 2 1 即可。

• 当 a=0,b=1 时，在标准矩阵左面竖着放若干个 0 1 1 即可。

• 当 a=0,b=2 时，在标准矩阵右面竖着放若干个两列的 1 2 2 即可。

还有几种情况，但是你会发现就是把上面四种中的两种揉到一起就行了。

然后这题就做完了，代码巨大但是很好写，都是差不多的东西，而且很好调。

#include <bits/stdc++.h>
int n, m;
constexpr int maxn = 210;
std::deque<int> ans[maxn];
int main(){
    std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false);
    std::cin >> n >> m;
    for(int i = 3; i <= 2 + (n / 3) * 3; i++){
        if(i % 3 == 0){
            for(int j = 1; j <= (m / 3); j++){
                ans[i].push_back(1);
                ans[i].push_back(1);
                ans[i].push_back(0);    
            }
        }
        if(i % 3 == 1){
            for(int j = 1; j <= (m / 3); j++){
                ans[i].push_back(2);
                ans[i].push_back(2);
                ans[i].push_back(1);    
            }
        }
        if(i % 3 == 2){
            for(int j = 1; j <= (m / 3); j++){
                ans[i].push_back(2);
                ans[i].push_back(2);
                ans[i].push_back(1);    
            }
        }
    }
    if(n % 3 == 1 && m % 3 == 0){
        for(int i = 1; i <= (m / 3); i++){
            ans[n + 3].push_back(1);
            ans[n + 3].push_back(1);
            ans[n + 3].push_back(0);
        }
    }
    if(n % 3 == 2 && m % 3 == 0){
        for(int i = 1; i <= (m / 3); i++){
            ans[1].push_back(2);
            ans[1].push_back(2);
            ans[1].push_back(1);
            ans[2].push_back(2);
            ans[2].push_back(2);
            ans[2].push_back(1);
        }
    }
    if(n % 3 == 0 && m % 3 == 1){
        for(int i = 3; i <= n + 2; i++){
            if(i % 3 == 0){
                ans[i].push_front(0);
            }
            if(i % 3 == 1 || i % 3 == 2){
                ans[i].push_front(1);
            }
        }
    } 
    if(n % 3 == 1 && m % 3 == 1){
        for(int i = 3; i <= n + 2; i++){
            if(i % 3 == 0){
                ans[i].push_front(0);
            }
            if(i % 3 == 1 || i % 3 == 2){
                ans[i].push_front(1);
            }
        }
        for(int i = 1; i <= (m / 3); i++){
            ans[n + 2].push_back(1);
            ans[n + 2].push_back(1);
            ans[n + 2].push_back(0);
        }
    }
    if(n % 3 == 2 && m % 3 == 1){
        for(int i = 1; i <= (m / 3); i++){
            ans[1].push_back(2);
            ans[1].push_back(2);
            ans[1].push_back(1);
            ans[2].push_back(2);
            ans[2].push_back(2);
            ans[2].push_back(1);
        }
        for(int i = 1; i <= n; i++){
            if(i % 3 == 0){
                ans[i].push_front(0);
            }
            if(i % 3 == 1 || i % 3 == 2){
                ans[i].push_front(1);
            }
        }
    }
    if(n % 3 == 0 && m % 3 == 2){
        for(int i = 3; i <= n + 2; i++){
            if(i % 3 == 0){
                ans[i].push_back(1);
                ans[i].push_back(1);
            }
            if(i % 3 == 1 || i % 3 == 2){
                ans[i].push_back(2);
                ans[i].push_back(2);
            }
        }
    }
    if(n % 3 == 1 && m % 3 == 2){
        for(int i = 1; i <= (m / 3); i++){
            ans[n + 2].push_back(1);
            ans[n + 2].push_back(1);
            ans[n + 2].push_back(0);
        }
        for(int i = 3; i <= n + 2; i++){
            if(i % 3 == 0){
                ans[i].push_back(1);
                ans[i].push_back(1);
            }
            if(i % 3 == 1 || i % 3 == 2){
                ans[i].push_back(2);
                ans[i].push_back(2);
            }
        }
    }
    if(n % 3 == 2 && m % 3 == 2){
        for(int i = 1; i <= (m / 3); i++){
            ans[1].push_back(2);
            ans[1].push_back(2);
            ans[1].push_back(1);
            ans[2].push_back(2);
            ans[2].push_back(2);
            ans[2].push_back(1);
        }
        for(int i = 1; i <= n; i++){
            if(i % 3 == 0){
                ans[i].push_back(1);
                ans[i].push_back(1);
            }
            if(i % 3 == 1 || i % 3 == 2){
                ans[i].push_back(2);
                ans[i].push_back(2);
            }
        }
    }
    for(int i = 1; i <= n + 3; i++){
        if(ans[i].size()){
            for(int x : ans[i]){
                std::cout << x << ' ';
            }
            std::cout << '\n';
        }
    } 

    return 0; 
}