题解 P5102 【[JOI 2016 Final]领地】
sunzh
·
·
题解
路径上经过的所有点可以用按照轮次和位置表示为(x,y,r)表示第r轮走在(x,y)位置
如果我们默认每次的起点都是(0,0)那么(x,y,r)表示的就是(x+r\times tx,y+r\times ty)
我们如果把所有的点的x坐标都限制在0到tx范围内，那么我们就把所有本质一样的点都压在了一个位置，只要轮数一致，那就是完全重合的两个点
对于x不在0到tx之间的点，我们通过调整轮数使它在合法区间内
我们对于每个点可以处理出存在的轮数区间，考虑每个店作为左下角时，其它三个点对应的位置和轮数区间，四个点所对应的轮数同时合法那就计入答案，也就是将区间统一标准后求交集即可
具体细节可以看代码
```cpp
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<cmath>
#include<map>
#define PII pair<int,int>
#define pb push_back
#define ep emplace_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return f==1?x:~x+1;
}
inline void print(int x){
if(x<0) putchar('-'),x=~x+1;
if(x>=10) print(x/10);
putchar((x%10)|48);
}
int n,k;
char str[100010];
map<PII,vector<PII> >Map;
int tx,ty;
void merge(vector<PII>&s,vector<PII>t){
vector<PII>res;
auto it=t.begin();
for(auto i:s){
while(it!=t.end()){
while(it!=t.end()&&it->se<i.fi) ++it;
if(it==t.end()) break ;
if(it->fi>i.se) break ;
res.ep(max(it->fi,i.fi),min(it->se,i.se));
if(it->se>i.se) break ;
++it;
}
}
s=res;
}
int main(){
n=read(),k=read();
scanf("%s",str+1);
for(int i=1;i<=n;++i){
switch(str[i]){
case 'E':++tx;break ;
case 'N':++ty;break ;
case 'W':--tx;break ;
case 'S':--ty;break ;
}
}
if(tx==0&&ty==0) {k=1;tx=1e9;}
else if(tx==0){
swap(tx,ty);
for(int i=1;i<=n;++i){
switch(str[i]){
case 'E':str[i]='N';break;
case 'N':str[i]='E';break;
case 'W':str[i]='S';break;
case 'S':str[i]='W';break;
}
}
}
if(tx<0){
for(int i=1;i<=n;++i){
switch(str[i]){
case 'E':str[i]='W';break;
case 'W':str[i]='E';break;
}
}
tx=-tx;
}
if(ty<0){
for(int i=1;i<=n;++i){
switch(str[i]){
case 'N':str[i]='S';break;
case 'S':str[i]='N';break;
}
}
ty=-ty;
}
Map[mp(0,0)].pb(mp(1,k));
for(int i=1;i<=n;++i){
static int x=0,y=0;
switch(str[i]){
case 'E':++x;break ;
case 'N':++y;break ;
case 'W':--x;break ;
case 'S':--y;break ;
}
// printf("i:%d,x:%d,y:%d\n",i,x,y);
int d=x/tx;
int ax=x-d*tx,ay=y-d*ty;
if(ax<0) --d,ax+=tx,ay+=ty;
// printf("d:%d,ax:%d,ay:%d\n\n\n",d,ax,ay);
Map[mp(ax,ay)].pb(mp(d+1,d+k));
}
for(auto &i:Map){
auto &v=i.se;
sort(v.begin(),v.end());
int l=-1e6,r=-1e6;
vector<PII>nw;
for(auto p:v){
if(l==-1e6){
l=p.fi,r=p.se;
}
else if(p.fi<=r) r=max(r,p.se);
else{
nw.ep(l,r);
l=p.fi,r=p.se;
}
}
nw.ep(l,r);
v=nw;
}
auto mt=[&](PII x){
if(x.fi>=tx) x.fi-=tx,x.se-=ty;
return x;
};
long long ans=0;
for(auto i:Map){
PII nod=i.fi;
PII x2=mp(nod.fi+1,nod.se),x3=mp(nod.fi,nod.se+1),x4=mp(nod.fi+1,nod.se+1);
if(Map.count(mt(x2))&&Map.count(mt(x3))&&Map.count(mt(x4))){
auto gs=[&](PII x){
if(x.fi>=tx){
x.fi-=tx,x.se-=ty;
vector<PII>t=Map[x];
vector<PII>res(t.size());
auto minus=[&](PII a){
return mp(a.fi-1,a.se-1);
};
// printf("Mns:\n");
// for(auto a:t) printf("%d %d\n",a.fi,a.se);
std::transform(t.begin(),t.end(),res.begin(),minus);
// printf("Res:\n");
// for(auto a:res) printf("%d %d\n",a.fi,a.se);
// printf("\n\n");
return res;
}
else return Map[x];
};
vector<PII>v=i.se;
merge(v,gs(x2));merge(v,gs(x3));merge(v,gs(x4));
for(auto x:v) ans+=x.se-x.fi+1;
// printf("%d %d ans:%d\n",nod.fi,nod.se,ans);
}
}
printf("%lld\n",ans);
return 0;
}
```