题解：P5102 [JOI 2016 Final] 领地 / Territory

分析

首先

k=1

我们是会的，模拟即可。

然后将一次走的

n

步构成的图看作一个整体，注意到每次这个整体会有一个偏移量，这是可求的，将 x 坐标上的偏移量记作

dx

，将 y 坐标上的偏移量记作

dy

。先暂时不考虑

dx=0

或

dy=0

的情况，也暂时不管

dx < 0

的情况，因为这些都是可以通过简单处理转化为

dx>0

的情况的。

注意到每次偏移的是固定量，自然地想到取模。一开始每个点的位置可以用二元组

(x,y)

表示，但我们会发现单靠这两个信息无法很好地维护，因为一个整体中可能会存在一个点与另外一个点偏移若干次后的点重合，这种情况是很棘手的，尝试去容斥，但要满足的信息太多，没有前途。故考虑将这些会重合的点通过取模规划在一起，具体地：用一个三元组

(x,y,t)

表示一个位于坐标

(x+t \times dx,y+t \times dy)

的点，并规定

x \in [0,dx-1]

。用这种三元组表示后，我们会发现：所有重合的点，三元组中前两元是一样的，换句话说，经过偏移后的两个点重合的充要条件是三元组前两元相等（简单分析可证）。然后这样还有什么好处呢，有关键性质：对于在初始整体中的点

(x,y)

来说，它会偏移出

(x,y,0)

，

(x,y,1) \dots (x,y,k-1)

这些点，它们的前两元都相等，且第三元的值是一段连续的区间。

有了这些后，我们尝试一步步地做这题。

首先，对于第一个整体中每一个点

(x,y)

都可以通过取模与偏移，处理出三元组

(x_0,y_0,t_0)

，然后就相当于在

(x_0,y_0)

这个键值对的集合中加入的一个

(t_0,t_0+k-1)

的区间，然后我们又可以通过 set 动态加入区间，与已有区间求并。

下一步我们考虑计算答案。我们会发现共有

O(n)

级别个键值对

(x_0,y_0)

，考虑枚举

1 \times 1

正方形的左下角的键值对，从而也能求出其余三个正方形中的格子的键值对，然后想要算的贡献就等于这四个键值对所对应的集合中的区间的交。

有点乱，具体细节看代码。

有几个重要操作提一下：

①：区间取并的核心思想是：通过 set 二分出左右两端与新加入区间相交的地方。插入一个区间时间为

\log2

级别。

②：两个集合中的区间取交可以先转化为 vector 类型，然后在一个集合中固定区间，通过双指针在另一个集合中寻找与固定的区间有交的区间。

分析一下时间复杂度，动态区间取并是

O(n \times \log_2n)

的，求交时枚举的左下角是

O(n)

级别的，集合中取交的确是

O(n \times \log_2n)

级别的（set 中取区间是

\log2

级别的），但是均摊后总体也是

O(n \times \log_2n)

级别的，加上前面的取并，总时间复杂度

O(n \times \log_2n)

。

还有一点没解决，就是

dx=0

与

dx<0

的情况。其中

dx=0

就将

dx

与

dy

交换，并将

n

步中的上下与左右交换。极端地，如果

dy=dx=0

，那么可以将

k

视为

0

，然后

dx

设为一个正整数即可。以及如果

dx<0

，同样的，将“左”和“右”交换即可。

贴个代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int N=1e5,INF=1e15;
int T,n,k;
int dx,dy;
char a[N+5];
map<pii,set<pii>> mp;
void addv(int &x,int &y,char ch){
	if(ch=='E')
		++x;
	if(ch=='W')
		--x;
	if(ch=='N')
		++y;
	if(ch=='S')
		--y;
}
void insert(pii x,pii y){
	auto &s=mp[x];
	auto L=s.lower_bound(make_pair(y.first,-INF));
	auto R=s.upper_bound(make_pair(y.second+1,INF));
	if(L!=s.begin()&&prev(L)->second>=y.first-1)
		--L;
	if(L==R)
		s.insert(y);
	else{
		int tl=min(L->first,y.first),tr=max(prev(R)->second,y.second);
		s.erase(L,R);
		s.insert(make_pair(tl,tr));
	}
}
void add_range(int x,int y){
	int tmp=x/dx;
	x-=dx*tmp,y-=dy*tmp;
	if(x<0)
		--tmp,x+=dx,y+=dy;
	insert(make_pair(x,y),make_pair(tmp,tmp+k-1)); 
}
void prepare(){
	mp.clear();
	mp[{0,0}].insert(make_pair(0,k-1));
	int nowx=0,nowy=0;
	for(int i=1;i<=n;++i){
		addv(nowx,nowy,a[i]);
		add_range(nowx,nowy); 
	}
}
vector<pii> change(int x,int y){
	int flag=0;
	if(x==dx)
		x-=dx,y-=dy,flag=1;
	vector<pii> res;
	if(!mp.count(make_pair(x,y)))
		return res;
	for(auto i:mp[make_pair(x,y)])
		res.emplace_back(make_pair(i.first-flag,i.second-flag));
	return res;
}
vector<pii> merge(vector<pii> x,vector<pii> y){
	vector<pii> res;
	auto it=y.begin();
	for(auto [l,r]:x){
		while(it!=y.end()){
			while(it!=y.end()&&it->second<l)
				++it;
			if(it==y.end()||it->first>r)
				break;
			res.emplace_back(make_pair(max(it->first,l),min(it->second,r)));
			if(it->second>=r)
				break;
			++it;
		}
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	T=1;
	while(T--){
		cin>>n>>k>>(a+1);
		dx=dy=0;
		for(int i=1;i<=n;++i)
			addv(dx,dy,a[i]);
		if(!dx){
			swap(dx,dy);
			for(int i=1;i<=n;++i){
				if(a[i]=='E')
					a[i]='N';
				else if(a[i]=='N')
					a[i]='E';
				if(a[i]=='W')
					a[i]='S';
				else if(a[i]=='S')
					a[i]='W'; 
			}
			if(!dx)
				dx=1,k=1;
		}
		if(dx<0){
			dx=-dx;
			for(int i=1;i<=n;++i){
				if(a[i]=='E')
					a[i]='W';
				else if(a[i]=='W') 
					a[i]='E';
			}
		}
		prepare();
		int ans=0;
		for(map<pii,set<pii>>::iterator it=mp.begin();it!=mp.end();++it){
			int x=it->first.first,y=it->first.second;
			for(auto i:merge(merge(change(x,y),change(x+1,y)),merge(change(x,y+1),change(x+1,y+1))))
				ans+=i.second-i.first+1;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

题解：P5102 [JOI 2016 Final] 领地 / Territory

文章操作

分析

贴个代码

相关推荐

评论

题解：P5102 [JOI 2016 Final] 领地 / Territory