P7186 [CRCI2008-2009] TABLICA 题解

题目传送门

首先，乍一眼的思路：

二维数组直接模拟！！！

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

这时，聪明的你会想到：

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

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

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

大致思路：

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

CPP

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;
	}

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

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

CPP

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为负数的情况。（正数不影响）

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

CPP

        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;
			}
		}

P7186 [CRCI2008-2009] TABLICA 题解

文章操作

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

完结撒花！！！

相关推荐

评论

P7186 [CRCI2008-2009] TABLICA 题解