Codeforces Round #839 (Div. 3) F. Copy of a Copy of a Copy

标签：std 01 int 839 矩阵 second Div Copy

题目链接：https://codeforces.com/problemset/problem/1772/F

 

 题目的大致意思是：

　　给你一个01矩阵，然后你可以进行俩种操作：

　　1：你可以将一个  不在边缘的  并且   四个方向与之不同的  数 变成  与之不同的 数；

　　2：复制一遍这个01矩阵；

你已经进行了不知道多少次操作，然后你得到（k+1）个01矩阵；

现在，给你这（k+1）个01矩阵，问你   最初的矩阵是第几个，并且给出操作顺序使得由最初的01矩阵进行这些操作后和给出的（k+1）个01矩阵对应；

注意：给出的01矩阵的顺序一开始是任意的；

 

解题思路：

                                                                  1            0           1           0

首先，我们来观察，题目的意思是，要将101或者010变成111或者000；

 

                                                                   1            0           1           0

而一旦进行了这种操作，那么，接下来这个01矩阵中满足  中间的数与四个方向的数不同的情况也就会减一；

很容易可以看出，我们是不能通过以上的操作将满足  中间的数与四个方向的数不同的情况  加一的；

那么也就是说，我们只要一开始先对每个01矩阵扫一遍，记录他满足情况的个数是多少，那么结果中个数最多的一个必然是最初的01矩阵；

而个数最少的必然是最后一个；

那么在我们得到每个01矩阵满足情况的个数后，我们将他们排列一下，那么结果就可以出来了；

因为会有（k+1）个01矩阵，那么就会进行k次复制操作，所以我们无需太在意这个，在相邻的矩阵中加一个这个操作即可；

 时间复杂度：O（N*M）（是咩？，不太会算，但是数据挺小的，0ms过了）

 

ac代码如下:

#include<bits/stdc++.h>

bool my_cmp(std::pair<int, int> x, std::pair<int, int> y)
{
    if (x.second == y.second)return x.first < y.first;
    return x.second > y.second;
}

int main()
{
    std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    int N, M, K; std::cin >> N >> M >> K;
    std::vector cnt(N + 1, std::vector<int>(M + 1, 0));
    std::vector G(K + 2, std::vector<std::string>(N + 1));
    for (int i = 1; i <= K + 1; ++i)//输入矩阵
    {
        for (int k = 1; k <= N; ++k)
        {
            std::string s; std::cin >> s; 
            s = "!" + s;G[i][k] = s;
            for (int p = 1; p <= M; ++p)cnt[k][p] += (s[p] - '0');
        }
    }

    std::vector<std::pair<int, int>> FOU;
    for (int i = 1; i <= N; ++i)//此处是记录哪些位置是变动过的
        for (int j = 1; j <= M; ++j)
            if (cnt[i][j] != K + 1 && cnt[i][j] != 0)
                FOU.push_back(std::make_pair(i, j));

    std::vector<int> MP(K + 2, 0);
    for (auto& [x, y] : FOU)//此处是记录一个矩阵满足的情况个数
    {
        //std::cout << x << " " << y << "\n";
        for (int i = 1; i <= K + 1; ++i)
        {
            int cnt = 0;
            if (G[i][x][y] != G[i][x - 1][y])cnt++;
            if (G[i][x][y] != G[i][x][y - 1])cnt++;
            if (G[i][x][y] != G[i][x][y + 1])cnt++;
            if (G[i][x][y] != G[i][x + 1][y])cnt++;
            MP[i] += (cnt == 4);
        }
    }

    std::vector<std::pair<int, int>>OP;
    for (int x = 1; x <= K + 1; ++x)
        OP.push_back(std::make_pair(x, MP[x]));
    std::sort(OP.begin(), OP.end(), my_cmp);//进行排序
    /*for (int i = 0; i <= K; ++i)
        std::cout << OP[i].first << " " << OP[i].second << "\n";*/
    std::vector<std::vector<int>> ANS;
    for (int p = 1; p < K + 1; ++p)
    {
        int pre = OP[p - 1].first, now = OP[p].first;
        for (int j = 1; j <= N; ++j)
            for (int k = 1; k <= M; ++k)
                if (G[now][j][k] != G[pre][j][k])
                    ANS.push_back({ 1,j,k });
        ANS.push_back({ 2,now });
    }
        //输出结果
    std::cout << OP[0].first << "\n";
    std::cout << ANS.size() << "\n";
    for (int i = 0; i < ANS.size(); ++i)
        for (int j = 0; j < ANS[i].size(); ++j)
            std::cout << ANS[i][j] << (j == ANS[i].size() - 1 ? "\n" : " ");

    return 0;
}    

总的来说，这题对于思维的考察能力还是挺弱的（毕竟只是div.3），但是对于模拟能力要求还有有点高的，敲代码的时候还是要多多注意才行（悲

 

标签：std,01,int,839,矩阵,second,Div,Copy
From： https://www.cnblogs.com/ACMER-XiCen/p/17081822.html