P7186 [CRCI2008-2009] TABLICA 题解

· · 题解

题目传送门

首先，乍一眼的思路：

二维数组直接模拟！！！

但是评测机会告诉你：休想！
（空间限制32MB，但是这种方法O(kn^2)）

这时，聪明的你会想到：

难道我们真的需要一个完整的二维数组吗？其实有些点用不着，直接考虑被目标点直接造成影响的点即可。

重点：一维角度、实时更新。

恭喜你，你这题完成了一半了。

大致思路：

1.输入数字+目标行列值，求出数字初始的位置：

for(int i=1;i<=k;i++)
    {
        int no;
        cin>>no>>ex[i]>>ey[i];
        s[i].x=(no-1)/n+1;//向上取整，求行
        if(no%n!=0) s[i].y=no%n;
        else s[i].y=n;//求列
        //cout<<s[i].x<<" "<<s[i].y<<endl;
    }

接着，我们就需要依据目标点的变动去更新相关点了。

首先我们可以先搞出移动后的目标点状态+输出：

int dx=(ex[i]-s[i].x+n)%n;
int dy=(ey[i]-s[i].y+n)%n;
cout<<dx+dy<<endl;

注意：这里的+n%n是为了防止ex[i]-s[i].x为负数的情况。（正数不影响）

然后我们就可以更新其他点了： 核心： 变行其实是变了列的下标，变列其实是变了行的下标（要反一反）

        s[i].y=ey[i];//这里还在更新目标点哈
        for(int j=i+1;j<=k;j++)
        {
            if(s[j].x==s[i].x)//判断是否和目标点处在同一行
            {
                s[j].y=(s[j].y+dy-1)%n+1;//变的是列！！！
            }
        }

        s[i].x=ex[i];
        for(int j=i+1;j<=k;j++)
        {
            if(s[j].y==s[i].y)
            {
                s[j].x=(s[j].x+dx-1)%n+1;
            }
        }

完结撒花！！！