P3134 [USACO16JAN]Lights Out G 题解

2023-10-02 18:58:22

P3134 [USACO16JAN]Lights Out G题解

题目大意

真不好概括，可以去看看讨论（逃

分析

首先，我们可以发现，在黑暗中，要使 \(Bessie\) 意识到自己在哪个顶点，当且仅当她走过的边的结构在地图中是独一无二且最短的。

要实现这个目的，我们需要一种数据结构来维护地图的结构以及 \(Bessie\) 走过的路径，并且这种数据结构要满足如下几个特点：

可以查找路径在地图中的出现次数
支持在末尾新添状态
复杂度小
每种地图结构只有一种表达方式，反之亦然

这里给出一种很好实现的方法：字符串哈希

接下来说明如何实现。

实现

对于一个地图结构，我们可以模拟 \(Bessie\) 的路线：从起点出发，走一段长度到另一个顶点，然后左转或右转，直到到达出口

那我们也可以这样记录地图结构：

左转：在字符串中加入一个字符 \(L\)
右转：在字符串中加入一个字符 \(R\)
直走：在字符串中加入当前边的长度

可以得到如下函数：

inline void add(register string &mode,const int x){
	if(a[x].lr) mode+='R';else mode+='L';//左右转
	register string s;register int tmp=a[x].len;//路径长度
	while(tmp) s+=char((tmp%10)|48),tmp/=10;
	reverse(s.begin(),s.end());mode+=s;//加进字符串中
}

而要实现查找路径在地图中的出现次数，可以用到 \(STL\) 中的 \(string\) 函数 \(find()\)

循环使用 \(find()\) 即可：

inline int count(const string &a,const string &b){
	register size_t pos=0;register int ans=0;
	while((pos=a.find(b,pos))!=string::npos) ++ans,++pos;
	return ans;
}

\(But!!\) 仔细思考一下即可发现几个问题：

若路径串为 \(R10\)，地图串中有一个子串为 \(R1065\)，那么此时这个 \(count()\) 函数仍然会匹配到。

所以我们对 \(add()\) 函数进行一些修改：每次加入完一条边后再加一个空格

inline void add(register string &mode,const int x){
    if(a[x].lr) mode+='R';else mode+='L';//左右转
    register string s;register int tmp=a[x].len;//路径长度
    while(tmp) s+=char((tmp%10)|48),tmp/=10;
    reverse(s.begin(),s.end());mode+=s;mode+=' ';//新加一个空格（或其他字符也行）
}

重新审题，可以发现 \(Bessie\) 每到一个顶点，她是可以判断下一条边的转向方向的（左 \(or\) 右）。

所以我们对 \(count()\) 函数进行一些修改：每次匹配路径时，临时在路径串末尾加入下一次转向的符号
```
inline int count(const string &a,register string b,const char c){
    b+=c;//临时加入下一次转向的方向符号
    register size_t pos=0;register int cnt=0;
    while((pos=a.find(b,pos))!=string::npos) ++cnt,++pos;
    return cnt;
}
```

有了 \(add()\) 和 \(count()\) 函数，我们即可写出 \(solve()\) 函数统计答案

inline void solve(const int now){
	register string path;
	register int sum=0;
	for(register int i=now;i<=n;++i){
		if(count(mode,path,a[i].lr?'R':'L')) return void(ans=max(ans,abs(dis[now]-(sum+dis[i]))));
		add(path,i),sum+=a[i].len;
	}
}

for(register int i=2;i<=n;i++) solve(i);

~~接下来就是最恶心的数据读入了~~

代码中注释很详细，可以自行理解

/*a[i].lr: 0->左转，1->右转*/
/*a[i].dir: 1->东，2->南,3->西,4->北*/
n=read();
for(register int i=1;i<=n;++i) mp[i].first=read(),mp[i].second=read();
mp[n+1]=mp[1];
for(register int i=2;i<=n+1;++i){
    if(mp[i].first==mp[i-1].first){//竖着走
        tot+=(a[i-1].len=abs(mp[i].second-mp[i-1].second));
        if(mp[i].second>mp[i-1].second){//向上走
            a[i-1].dir=4;if(!a[i-2].dir) continue;
            if(a[i-2].dir==1) a[i-1].lr=0;//前一个是向东走，那么就是左转
            else a[i-1].lr=1;//前一个是向西走，那么就是右转
        }
        else{//向下走
            a[i-1].dir=2;if(!a[i-2].dir) continue;
            if(a[i-2].dir==1) a[i-1].lr=1;//前一个是向东走，那么就是右转
            else a[i-1].lr=0;//前一个是向西走，那么就是左转
        }
    }
    else{//横着走
        tot+=(a[i-1].len=abs(mp[i].first-mp[i-1].first));
        if(mp[i].first>mp[i-1].first){//向右走
            a[i-1].dir=1;if(!a[i-2].dir) continue;
            if(a[i-2].dir==2) a[i-1].lr=0;//前一个是向南走，那么就是左转
            else a[i-1].lr=1;//前一个是向北走，那么就是右转
        }
        else{//向左走
            a[i-1].dir=3;if(!a[i-2].dir) continue;
            if(a[i-2].dir==2) a[i-1].lr=1;//前一个是向南走，那么就是右转
            else a[i-1].lr=0;//前一个是向北走，那么就是左转
        }
    }
}

完整代码

#include<bits/stdc++.h>
#define N 205
#define inf 0x3f3f3f3f
#define endl '\n'
#define debug cerr<<__LINE__<<endl
using namespace std;
int n,tot,ans=-inf;
int dis[N];
int shun[N],ni[N];
pair<int,int>mp[N];
struct node{int len,dir;bool lr;}a[N];
string mode;
inline char gc(){
	static const int L=1<<22|1;static char c[L],*a,*b;
	return (a==b)&&(b=(a=c)+fread(c,1,L,stdin),a==b)?-1:*a++;
}
inline int read(){
	register int f=1,k=0;
	register char c=gc();
	while(c!='-'&&(c<'0'||c>'9')) c=gc();
	if(c=='-') f=-1,c=gc();
	while(c>='0'&&c<='9') k=(k<<3)+(k<<1)+(c^48),c=gc();
	return f*k;
}
inline void write(register int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar((x%10)|48);
}
inline void add(register string &mode,const int x){
	if(x==1) mode+='T';else if(a[x].lr) mode+='R';else mode+='L';
	register string s;register int tmp=a[x].len;
	while(tmp) s+=char((tmp%10)|48),tmp/=10;
	reverse(s.begin(),s.end());mode+=s;mode+=' ';
}
inline void init(){
	for(register int i=1;i<=n;i++) add(mode,i);
	for(register int sum=0,i=1;i<=n;i++) dis[i]=min(tot-sum,sum),sum+=a[i].len;
}
inline int count(const string &a,register string b,const char c){
	b+=c;
	register size_t pos=0;register int cnt=0;
	while((pos=a.find(b,pos))!=string::npos) ++cnt,++pos;
	return cnt;
}
inline void solve(const int now){
	register string path;
	register int sum=0;
	for(register int i=now;i<=n;i++){
		if(count(mode,path,a[i].lr?'R':'L')==1) return void(ans=max(ans,abs(dis[now]-(sum+dis[i]))));
		add(path,i),sum+=a[i].len;
	}
}
main(void){
	n=read();
	for(register int i=1;i<=n;i++) mp[i].first=read(),mp[i].second=read();
	mp[n+1]=mp[1];
	for(register int i=2;i<=n+1;i++){
		if(mp[i].first==mp[i-1].first){
			tot+=(a[i-1].len=abs(mp[i].second-mp[i-1].second));
			if(mp[i].second>mp[i-1].second){
				a[i-1].dir=4;if(!a[i-2].dir) continue;
				if(a[i-2].dir==1) a[i-1].lr=0;
				else a[i-1].lr=1;
			}
			else{
				a[i-1].dir=2;if(!a[i-2].dir) continue;
				if(a[i-2].dir==1) a[i-1].lr=1;
				else a[i-1].lr=0;
			}
		}
		else{
			tot+=(a[i-1].len=abs(mp[i].first-mp[i-1].first));
			if(mp[i].first>mp[i-1].first){
				a[i-1].dir=1;if(!a[i-2].dir) continue;
				if(a[i-2].dir==2) a[i-1].lr=0;
				else a[i-1].lr=1;
			}
			else{
				a[i-1].dir=3;if(!a[i-2].dir) continue;
				if(a[i-2].dir==2) a[i-1].lr=1;
				else a[i-1].lr=0;
			}
		}
	}
	init();for(register int i=2;i<=n;i++) solve(i);
	write(ans),putchar('\n');
	return 0;
}

码风较奇葩（~~压行强迫症+卡常小能手~~）

欢迎觉得做法很麻烦或有错误的巨佬来喷

码农公寓

P3134 [USACO16JAN]Lights Out G题解

题目大意

分析

实现

完整代码

相关文章