【题解】洛谷 P7170 [COCI2020-2021#3] Sateliti

wsyhb · 2021-04-05 12:22:31 · 题解

题解

可以进行行循环移位和列循环移位，因此只需确定左上角的格子是原来的哪个格子，即可确定对应图形。很自然想到将原矩阵复制成左上、右上、左下、右下四份，以方便求解答案。

二维 Hash 可以判断两个子矩阵相不相等，外层套个二分确定第一个不相同的位置，就可以比较字典序大小，总时间复杂度 O(nm(\log{n}+\log{m}))。

代码

PS：二维 Hash 可以将 (i,j) 的权值赋为 p^{(i-1)*m+(j-1)}（从左到右、从上到下对格子进行编号），也可以将其赋为 p^{i}q^{j}（行列分别编号），其中 p,q 为互不相同的质数。笔者使用的是前者，官方题解使用的是后者，故都贴一下代码。

笔者代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int inv2=5e8+4;
inline int get_sum(int a,int b)
{
    return a+b-(a+b>=mod?mod:0);
}
inline int get_power(int a,int n)
{
    int res=1;
    while(n>0)
    {
        res=n&1?1ll*res*a%mod:res;
        a=1ll*a*a%mod;
        n>>=1;
    }
    return res;
}
int n,m;
inline int id(int x,int y)
{
    return (x-1)*(m<<1)+(y-1);
}
const int max_n=1e3+5;
const int max_m=1e3+5;
char str[max_m];
int Map[max_n<<1][max_m<<1];
const int max_tot=4e6+5;
int pow2[max_tot],pow_inv2[max_tot],Hash[max_n<<1][max_m<<1];
inline int get_Hash(int a,int b,int c,int d) // calculate the hash value of the matrix that the upper left corner is (a,b) and the lower right corner is (c,d)
{
    return (1ll*Hash[c][d]-Hash[a-1][d]-Hash[c][b-1]+Hash[a-1][b-1]+2*mod)*pow_inv2[id(a,b)]%mod;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",str+1);
        for(int j=1;j<=m;++j)
            Map[i][j]=Map[i+n][j]=Map[i][j+m]=Map[i+n][j+m]=(str[j]=='.');
    }
    pow2[0]=1;
    for(int i=1;i<=(n*m<<2);++i)
        pow2[i]=get_sum(pow2[i-1],pow2[i-1]);
    pow_inv2[n*m<<2]=get_power(pow2[n*m<<2],mod-2);
    for(int i=(n*m<<2)-1;i>=0;--i)
        pow_inv2[i]=get_sum(pow_inv2[i+1],pow_inv2[i+1]); 
    for(int i=1;i<=(n<<1);++i)  
        for(int j=1;j<=(m<<1);++j)
            Hash[i][j]=(1ll*Map[i][j]*pow2[id(i,j)]+Hash[i-1][j]+Hash[i][j-1]-Hash[i-1][j-1]+mod)%mod;
    int ans_x=1,ans_y=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            int L=1,R=n,res_x=n+1,res_y=m+1;
            while(L<=R)
            {
                int mid=(L+R)>>1;
                if(get_Hash(i,j,i+mid-1,j+m-1)!=get_Hash(ans_x,ans_y,ans_x+mid-1,ans_y+m-1))
                    res_x=mid,R=mid-1;
                else
                    L=mid+1;
            }
            if(res_x==n+1)
                continue;
            L=1,R=m;
            while(L<=R)
            {
                int mid=(L+R)>>1;
                if(get_Hash(i+res_x-1,j,i+res_x-1,j+mid-1)!=get_Hash(ans_x+res_x-1,ans_y,ans_x+res_x-1,ans_y+mid-1))
                    res_y=mid,R=mid-1;
                else
                    L=mid+1;
            }
            if(!Map[i+res_x-1][j+res_y-1])
                ans_x=i,ans_y=j;
        }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            putchar(Map[ans_x+i-1][ans_y+j-1]?'.':'*');
        putchar('\n');
    }
    return 0;
}

官方 std

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 1010, MOD = 1e9 + 7, P = 2, Q = 3;

int pq_pow[2 * MAXN][2 * MAXN];
int h[2 * MAXN][2 * MAXN];

int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}
int sub(int a, int b) { return add(a, MOD - b); }
int mul(int a, int b) { return (ll)a * b % MOD; }

void precalc(const vector<string>& a) {
    for (int i = 0; i < 2 * MAXN; i++) {
        for (int j = 0; j < 2 * MAXN; j++) {
            if (i == 0 && j == 0) pq_pow[i][j] = 1;
            else if (i == 0) pq_pow[i][j] = mul(pq_pow[i][j - 1], Q);
            else pq_pow[i][j] = mul(pq_pow[i - 1][j], P);
        }
    }

    int n = a.size(), m = a[0].size();
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * m; j++) {
            int val = mul(a[i % n][j % m] == '.', pq_pow[i][j]);
            h[i + 1][j + 1] = sub(add(val,
                        add(h[i + 1][j], h[i][j + 1])),
                    h[i][j]);
        }
    }
}

int get_h(int x, int y, int dx, int dy) {
    return sub(add(h[x + dx][y + dy], h[x][y]),
            add(h[x][y + dy], h[x + dx][y]));
}

bool is_equal(int x1, int y1, int x2, int y2, int dx, int dy) {
    int val1 = mul(get_h(x1, y1, dx, dy), pq_pow[x2][y2]);
    int val2 = mul(get_h(x2, y2, dx, dy), pq_pow[x1][y1]);
    return val1 == val2;
}

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

    int n, m;
    cin >> n >> m;

    vector<string> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    precalc(a);

    int sol_x = 0, sol_y = 0;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            int lo_dx = 0, hi_dx = n;
            while (lo_dx + 1 < hi_dx) {
                int dx = (lo_dx + hi_dx) / 2;
                if (is_equal(sol_x, sol_y, x, y, dx, m)) lo_dx = dx;
                else hi_dx = dx;
            }
            int dx = lo_dx;

            int lo_dy = 0, hi_dy = m;
            while (lo_dy + 1 < hi_dy) {
                int dy = (lo_dy + hi_dy) / 2;
                if (is_equal(sol_x + dx, sol_y, x + dx, y, 1, dy)) lo_dy = dy;
                else hi_dy = dy;
            }
            int dy = lo_dy;

            if (a[(x + dx) % n][(y + dy) % m] <
                a[(sol_x + dx) % n][(sol_y + dy) % m]) {
                sol_x = x;
                sol_y = y;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << a[(sol_x + i) % n][(sol_y + j) % m];
        cout << '\n';
    }

    return 0;
}