题解：CF2255C Even If the World Turns

· · 题解

思路

step 1 观察/简化题目

观察每个操作——

step 2 设计信息存储方式

观察题目，发现似乎可以把所有黑色的点的横竖坐标分别作为表示信息的方式。

接下来设计信息存储方式。

由于x,y轴没什么本质区别，因此以下只讨论x轴。

令 x_1, x_2, x_3 \dots x_w 表示黑色点横坐标从小到大排序后的序列，x_i 为 0,1,2 \dots n-1 （即把原坐标减一）。

考虑加减乘除，发现乘除减都不太行。那就只剩下加了。

以下所有数均在 \bmod \space n 意义下。

让 S=x_1+x_2+x_3 \dots x_w 作为目标格子？

发现稍微有点问题：

对于平移操作，设平移了 k 个格子 S \to S+wk 。但是实际的 x \to x+k 。

如何解决？可以让 S 变为 wS，再让实际的 x = S \times w^{-1} 。这样 x+k=wS+wK=S \times w^{-1} + k 。

对于旋转/翻转操作：S \to nw-S (x 是从 0 开始的)，x \to n-x ，n-s \times w^{-1} = n-x 。

所以最终就是这样的表示方式。

step 3 具体如何操作/实现

我们要交换 (x1, y1) 与 (x2,y2) 使得 x_1+x_2+x_3 \dots x_w \mod n = w^{-1}S ，y轴同理。

当前目标格子为 (x, y) 。

找到一个横坐标为 p 的黑格，以及一个横坐标为 p+wx-S_0 \mod n 的白格即可。

值得注意的是，这样的黑格是一定存在的。

::::info[证明]

把每个格点想象成一个图上的节点，边为 p \to p+wx-S_0 \mod n 。

如果没有这样的黑格，那么这个图一定是由很多相同长度环组成的，设每个环的长度为 l 。

显然有 l \mid n ，l \mid w ，因此 \gcd(w, n) \ge l ，与题目条件矛盾。

::::

对于第二次运行，我们就扫一遍网格，找到满足 wx=S 的就行了。

代码

#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
template <class TT>
using vc=vector<TT>;

void solve1(){
    int n;
    cin >> n;
    vc<vc<char>> a(n, vc<char>(n));
    int w=0;
    for(int i=0;i < n;i++){
        for(int j=0;j < n;j++){
            cin >> a[i][j];
            if(a[i][j] == '#') w++;
        }
    }
    if(w*2 > n*n){ //处理反转操作
        for(int i=0;i < n;i++){
            for(int j=0;j < n;j++){
                if(a[i][j] == '#') a[i][j]='.';
                else a[i][j]='#';
            }
        }
        w=n*n-w;
    }
    int rx, ry;
    cin >> rx >> ry;
    rx--;
    ry--;
    int sx0=0, sy0=0;
    for(int i=0;i < n;i++){
        for(int j=0;j < n;j++){
            if(a[i][j] == '#'){
                sx0+=i;
                sy0+=j;
            }
        }
    }
    for(int i=0;i < n;i++){
        for(int j=0;j < n;j++){
            if(a[i][j] == '#'){
                int xx=((i+w*rx-sx0)%n+n)%n, yy=((j+w*ry-sy0)%n+n)%n;
                if((xx == i && yy == j) || a[xx][yy] == '.'){
                    cout << i+1 << " " << j+1 << " " << xx+1 << " " << yy+1 << "\n";
                    return;
                }
            }
        }
    }
}
void solve2(){
    int n;
    cin >> n;
    vc<vc<char>> a(n, vc<char>(n));
    int w=0;
    for(int i=0;i < n;i++){
        for(int j=0;j < n;j++){
            cin >> a[i][j];
            if(a[i][j] == '#') w++;
        }
    }
    if(w*2 > n*n){ //处理反转操作
        for(int i=0;i < n;i++){
            for(int j=0;j < n;j++){
                if(a[i][j] == '#') a[i][j]='.';
                else a[i][j]='#';
            }
        }
        w=n*n-w;
    }
    int sx0=0, sy0=0;
    for(int i=0;i < n;i++){
        for(int j=0;j < n;j++){
            if(a[i][j] == '#'){
                sx0+=i;
                sy0+=j;
            }
        }
    }
    for(int i=0;i < n;i++){
        for(int j=0;j < n;j++){
            if(w*i%n == sx0%n && w*j%n == sy0%n){
                cout << i+1 << " " << j+1 << "\n";
                return;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    string RUN;
    cin >> RUN;
    if(RUN == "first"){
        int T;
        cin >> T;
        while(T--){
            solve1();
        }
    }
    else if(RUN == "second"){
        int T;
        cin >> T;
        while(T--){
            solve2();
        }
    }
}