Copy of a Copy of a Copy

Created by LXC on Tue Apr 9 16:51:07 2024

https://codeforces.com/problemset/problem/1772/F

ranting: 2000

tag: constructive algorithms, dfs and similar, graphs, implementation, sortings

problem

给定一张 $n$ 行 $m$ 列的黑白图片（下标从 $1$ 开始），每一个单元格都被涂上了黑色或白色（$1$ 或者 $0$）。

我们对这张图片进行了若干次（可能为零次）操作，每一次操作都是下列两种之一：

• 选择一个单元格，这个单元格不能在图片的边缘（即，单元格所在行不能是 $1$ 或 $n$ 行，所在列不能是 $1$ 或 $m$ 列），并且这个单元格被四个不同颜色的单元格包围（中间 $0$ 四周 $1$，反之亦然），将这个单元格涂成相反的颜色；
• 复制一份当前图片。

两种操作不一定会交替进行。

给出你初始图片与 $k$ 份复制图片，一共 $k+1$ 份图片，这 $k+1$ 份图片是被随机打乱的。

你的任务是恢复操作的顺序。若有多种可能答案，只输出其中一个即可。

所有数据保证答案一定存在。

输入格式

输入第一行包含三个整数 $n$、$m$ 以及 $k$（$3\le n，m\le 30$；$0\le k\le 100$），分别表示图片的行数、列数和复制图片的数量。

接下来 $k+1$ 行，每行一张图片，包括 $k$ 张复制图片和 $1$ 张初始图片，顺序是打乱的。

每张图片由 $n$ 行 $m$ 列组成，每个单元格都为 $0$ 或 $1$。每张图片之前都有一个空行。

输出格式

输出第一行一个整数，表示初始图片是第几张。图片按其输入顺序分别编号 $1$ 至 $k+1$。

输出第二行一个整数 $q$，表示进行了多少次操作。

接下来 $q$ 行，每行对应一次操作，须按正确顺序输出操作。每个操作有题目描述中提到的两种类型：

• $1\ x\ y$ 表示在坐标 $(x,y)$ 执行第一种操作；
• $2\ i$ 表示复制一份当前图片，编号是 $i$。

solution

可以统计每张图片的可修改次数，一张图片可修改次数只会减少。

我们按照可修改次数降序排序，然后判断相邻图片间需要修改多少次，便用多少次一号操作，然后再用二号操作。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m, k;
    cin >> n >> m >> k;
    vector g(k+1, vector<string>(n));
    for (auto& i:g) {
        for (auto& j:i) {
            cin >> j;
        }
    }
    // cout << g << "\n";
    auto dif = [&](int x, int y)->vector<pair<int,int>> {
        vector<pair<int,int>> rt;
        for (int i=1; i<n-1; i++) {
            for (int j=1; j<m-1; j++) {
                if (g[x][i][j] != g[y][i][j]) {
                    rt.emplace_back(i,j);
                }
            }
        }
        return rt;
    };
    auto getopt = [&](int x) {
        int c = 0;
        for (int i=1; i<n-1; i++) {
            for (int j=1; j<m-1; j++) {
                int ok = 1;
                for (int k=0; k<4; k++) {
                    if (g[x][i][j] == g[x][i+(k-1)%2][j+(k-2)%2])
                        ok = 0;
                }
                c += ok;
            }
        }
        return c;
    };
    vector<int> opt(k+1), idx(k+1);
    for (int i=0; i<=k; i++) opt[i] = getopt(i);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return opt[x] > opt[y];
    });
    vector<pair<int,int>> ans;
    for (int i=1; i<=k; i++) {
        if (opt[idx[i]] < opt[idx[i-1]]) {
            for (auto j:dif(idx[i-1], idx[i])) {
                ans.emplace_back(j);
            }
        }
        ans.emplace_back(-1, idx[i]);
    }
    cout << idx[0]+1 << "\n";
    cout << ans.size() << "\n";
    for (auto& [x, y]:ans) {
        if (x == -1) {
            cout << "2 " << y+1 << "\n";
        } else {
            cout <<  "1 " << x+1 << " " << y+1 << "\n";
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}