P7186 [CRCI2008-2009] TABLICA 题解

Dr1fty · 2023-10-01 17:52:38 · 题解

• 一看到这题，第一反应肯定是暴力枚举。把每一个点都记录在数组里，一个一个模拟。移动时间复杂度为O(kn)，找到下一个点的时间复杂度 O(1)，完美过掉。

如果你是这么想的，恭喜你 MLE 了 (bushi

本题的空间复杂度为 \color{red}O(n^2) ，又注意到空间仅有 32MB ，显然是过不了的。

那我们再进一步思考：

• 只记录行和列，然后通过计算来完成变换，移动时间复杂度为O(kn)

但是！！！！

它找到下一个点时间复杂度是 O(kn^2)……（悲

那，怎么办？

仔细想一想，在之前的过程中，我们都将思维局限于在线算法，我们不妨尝试一下离线算法。

• 不知道读者有没有发现，在优化的过程中我们记录的东西是越来越少的，我们可以直接尝试只记录要修改的点的位置。这是你就会发现其他的点根本用不着，只需要处理要修改的点之间的影响即可

时间复杂度 O(k^2)，空间复杂度 O(k)，非常优雅的过掉了这道题

• 这题想通了其实非常简单，但是在代码细节上需要多多注意

最后奉上 AC 代码

#include<bits/stdc++.h>
using namespace std;
pair<int,int>a[1005];
int n,k,x,r[1005],c[1005];
int main()
{
    return 0;//防止抄题解
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL); //输入优化
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>x>>r[i]>>c[i];
        if(x%n)a[i]={x/n+1,x%n};
        else a[i]={x/n,n};
    }
    #define x first
    #define y second //打起来方便
    for(int i=1;i<=k;i++)
    {
        int m=((c[i]<a[i].y)?(n-a[i].y+c[i]):(c[i]-a[i].y));
        for(int j=i+1;j<=k;j++)
            if(a[i].x==a[j].x)
            {
                a[j].y=a[j].y+m;
                a[j].y-=(a[j].y>n)*n;
            }
        int s=((r[i]<a[i].x)?(n-a[i].x+r[i]):(r[i]-a[i].x));
        for(int j=i+1;j<=k;j++)
            if(c[i]==a[j].y)
            {
                a[j].x=a[j].x+s;
                a[j].x-=(a[j].x>n)*n;
            }
        cout<<m+s<<'\n';
    }
    return 0;
}

蒟蒻第一篇题解，求过 qwq