COCI2011-2012#3 ROBOT 题解

洛谷题面

部分分做法

直接依照题意模拟即可。
可以获得 \(48\) 分的好成绩。

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,m;
struct node{
	long long x;
	long long y;
}point[100005];
long long robotx=0,roboty=0;
long long query(){
	long long sum=0;//计算(point[i].x,point[i].y)和(robotx,roboty)的曼哈顿距离 
	for(int i=1;i<=n;i++){
		sum=sum+abs(point[i].x-robotx)+abs(point[i].y-roboty);
	}
	return sum;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>point[i].x>>point[i].y;
	}
	while(m--){
		char opt;
		opt=getchar();
		if(opt=='S'){
			roboty++;
		}
		if(opt=='J'){
			roboty--;
		}
		if(opt=='I'){
			robotx++;
		}
		if(opt=='Z'){
			robotx--;
		}
		cout<<query()<<endl;
	}
}

代码复杂度为 \(O\left ( n \times m\right )\)，超时但能冲掉不少数据点。

正解

如何优化呢？我的做法是前缀和。我们一开始就把当前的曼哈顿之和先算出来，记录行和列上的控制点的个数，对行和列分别进行前缀和预处理，用 \(x\) 和 \(y\) 记录当前机器人的坐标，\(ans\) 是曼哈顿距离的总和。

我们每次得到一个操作，便根据情况分析一下，用很简单的操作即可得到答案。

设记录操作种类的字符为 \(opt\)，数组 \(lq\) 为列的前缀和，\(hq\) 为行的前缀和，\(l\) 为每列的操作点的个数，\(h\) 为每行操作点的个数，\(n\) 为点的总数。

• \(opt = S\) 时，\(ans=ans+lq_y-(n-lq_y)\)。

• \(opt = J\) 时，\(ans=ans+n-lq_y+l_y-(lq_y-l_y)\)。

• \(opt = I\) 时，\(ans=ans+hq_x-(n-hq_x)\)。

• \(opt = Z\) 时，\(ans=ans+n-hq_x+h_x-(hq_x - h_x)\)

前缀和此题在洛谷 32MB 的空间下会有 MLE 的风险，所以 @wangzihang2012 的二分是好方法，但我不会。

#include<bits/stdc++.h>//都开long long会炸掉
using namespace std;
const long long yi=1e6;
long long hq[2000005],lq[2000005],h[2000005],l[2000005];
long long x,y,n,m,i,j,k,s,nx,ny,ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		h[x+yi]++;
		l[y+yi]++;
		ans=ans+abs(x-0)+abs(y-0);
	}
	for(int i=-1000000+1;i<=1000000;i++){
		lq[yi+i]=lq[i-1+yi]+l[i+yi];
		hq[yi+i]=hq[i-1+yi]+h[i+yi];
	}
	nx=0;
	ny=0;
	for(int i=1;i<=m;i++){
		char ch;
		cin>>ch;
		if(ch=='S'){
			ans=ans+lq[ny+yi];
			ans=ans-(n-lq[ny+yi]);
			ny++;
		}
		if(ch=='J'){
			ans=ans-(lq[ny+yi]-l[ny+yi]);
			ans=ans+(n-lq[ny+yi]+l[ny+yi]);
			ny--;
		}
		if(ch=='I'){
			ans=ans+hq[nx+yi];
			ans=ans-(n-hq[nx+yi]);
			nx++;
		}
		if(ch=='Z'){
			ans=ans-(hq[nx+yi]-h[nx+yi]);
			ans=ans+(n-(hq[nx+yi]-h[nx+yi]));
			nx--;
		}
		cout<<ans<<endl;
	}
}

全 MLE /ll 提交记录

但是前缀和改成 int 其他不变就可以 AC 啦！ AC 记录

#include<bits/stdc++.h>
using namespace std;
const int yi=1e6;
int hq[2000005],lq[2000005];
int h[2000005],l[2000005];
int x,y,n,m,k,s,nx,ny;
long long ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		h[x+yi]++;
		l[y+yi]++;
		ans=ans+abs(x-0)+abs(y-0);
	}
	for(int i=-1000000+1;i<=1000000;i++){
		lq[yi+i]=lq[i-1+yi]+l[i+yi];
		hq[yi+i]=hq[i-1+yi]+h[i+yi];
	}
	nx=0;
	ny=0;
	for(int i=1;i<=m;i++){
		char ch;
		cin>>ch;
		if(ch=='S'){
			ans=ans+lq[ny+yi];
			ans=ans-(n-lq[ny+yi]);
			ny++;
		}
		if(ch=='J'){
			ans=ans-(lq[ny+yi]-l[ny+yi]);
			ans=ans+(n-lq[ny+yi]+l[ny+yi]);
			ny--;
		}
		if(ch=='I'){
			ans=ans+hq[nx+yi];
			ans=ans-(n-hq[nx+yi]);
			nx++;
		}
		if(ch=='Z'){
			ans=ans-(hq[nx+yi]-h[nx+yi]);
			ans=ans+(n-(hq[nx+yi]-h[nx+yi]));
			nx--;
		}
		cout<<ans<<endl;
	}
}

感谢观看。