自动搬运

查看原文

来自洛谷，原作者为

	一念之间、、 Have already AFOed.

搬运于2025-08-24 22:12:11，当前版本为作者最后更新于2022-10-17 11:05:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

说：给定长度为 $n$ 的序列 $a$，长度为 $m$ 的序列 $b\in\{1,-1\}$ 维护两个指针 $i,j$ ，每次 $a_i$ += $b_j$ 然后两个指针同时 +1，指针是循环的，问：至少多少时刻使得存在一个 $a_i$ 变为 $0$。

题解

就说，考虑对于 $a_i$ 会取哪些 $b$ 显然是一个环的形式，且除了第一步，相邻两步之间间隔的时间恰为 $n$，我们求出来这些环，对于每个环进行讨论。

对于一个 $a_i$ 我们求得其在所在环上走路，最早变成 $0$ 的时刻，形如走 $k$ 圈，然后再向后走一段路径。

求出一圈的 $dlt$ 然后再求出 $k$ 剩下问题形如：从 $s$ 位置开始走，每次取对应位置的 $b$，保证在一圈以内能存在一个变成 $0$ 的点，问：最早的点在哪里。

这个东西呢，我比较逊，写的树状数组上二分，实际上可以直接开一个桶。

第一个复杂度是带 $\log$ 第二个不带，但是都可以过。

然后是实现细节。

首先是记得判断 $-1$。

如果你大量使用 vector 就像我一样，那么你会被卡空间，我也就被卡了 $13$ 发提交。

代码

#include<bits/stdc++.h>
namespace ifzw{
#define ll long long 
#define dd double
#define LL __int128
#define ld long double
#define ull unsigned ll 
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return *s++;}
#define getchar gc
ll read()
{
	char c;
	ll w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	ll ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
void pc(char c,int op)
{
	static char buf[1<<16],*s=buf,*t=(buf+(1<<16));
	(op||((*s++=c)&&(s==t)))&&(fwrite(buf,1,s-buf,stdout),s=buf);
}
void wt(int x)
{
	if(x>9)wt(x/10);
	pc('0'+x%10,0);
}
void wts(int x,char op)
{
	if(x<0)pc('-',0),x=-x;
	wt(x),pc(op,0);
}
char ST;
const int xx=1000005;
int n,m,a[xx];
char b[xx],vis[xx];
struct info
{
	vector<int>A;
};
vector<int>v[xx];
vector<info>cir;
vector<int>B;
namespace s1
{
	int lim;
	vector<int>sum;
	int lb(int x){return (x&(-x));}
	void add(int x,int y){++x;for(;x<=lim;x+=lb(x))sum[x]=min(sum[x],y);}
	int ask(int x){++x;int ans=1e9;for(;x;x-=lb(x))ans=min(ans,sum[x]);return ans;}
	int bin(int y)//第一个小于等于 y 的 
	{
		int x=0;
		for(int i=__lg(lim);i>=0;i--)
			if(x+(1<<i)<=lim&&sum[x+(1<<i)]>y)x+=(1<<i);
		return x+1 -1;
	}
	void Set(int x){vector<int>(x+1,1e9).swap(sum),lim=x;}
}
namespace s2
{
	int lim;
	vector<int>sum;
	int lb(int x){return (x&(-x));}
	void add(int x,int y){++x;for(;x<=lim;x+=lb(x))sum[x]=min(sum[x],y);}
	int ask(int x){++x;int ans=1e9;for(;x;x-=lb(x))ans=min(ans,sum[x]);return ans;}
	int bin(int y)//第一个小于等于 y 的 
	{
		int x=0;
		for(int i=__lg(lim);i>=0;i--)
			if(x+(1<<i)<=lim&&sum[x+(1<<i)]>y)x+=(1<<i);
		return x+1 -1;
	}
	void Set(int x){vector<int>(x+1,1e9).swap(sum),lim=x;}
}


char ED;
int main(){
//	freopen("a.in","r",stdin);
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
//	n=1e6;
//	for(int i=1;i<=n;i++)a[i]=1e6;
	m=read();
//	m=1e6-1;
	for(int i=1;i<=m;i++)
	{
		char c;
		while((c=getchar())!='P'&&c!='W');
		if(c=='W')b[i]=1;
		else b[i]=-1;
	}
//	for(int i=1;i<=m;i++)
//	{
//		b[i]=i%100==0?1:-1;
////		char c;
////		while((c=getchar())!='P'&&c!='W');
////		if(c=='W')b[i]=1;
////		else b[i]=-1;
//	}
	int te=0;
	for(int i=1;i<=m;i++)
	{
		if(vis[i])continue;
		int j=i;
		while(!vis[j])vis[j]=1,j+=n,j=(j-1)%m+1;
		++te;
	}
	for(int i=1;i<=m;i++)vis[i]=0;
	cir.resize(te),te=0;
	for(int i=1;i<=m;i++)
	{
		if(vis[i])continue;
		int j=i;
		vector<int>v;
		while(!vis[j])
		{
			vis[j]=1;
			v.push_back(j);
			j+=n,j=(j-1)%m+1;
		}
		v.shrink_to_fit();
		cir[te++]={v};
	}
// 105 MB 。 
//	cir.shrink_to_fit();
//	return 0;
	for(int i=1;i<=n;i++)
		v[(i-1)%m+1].push_back(i);
//	for(int i=1;i<=m;i++)v[i].shrink_to_fit();
	ll mn=1e18;
	for(auto &it:cir)
	{
		int sz=it.A.size();
		
		B.resize(it.A.size());
		for(int i=0;i<sz;i++)B[i]=b[it.A[i]]+(i!=0?B[i-1]:0);
		s1::Set(sz+1),s2::Set(sz+1);
		for(int i=0;i<sz;i++)s1::add(i,B[i]);
		for(int i=sz-1;i>=0;i--)
		{
			s2::add(i,B[i]);
			for(auto itv:v[it.A[i]])
			{
				int sm=B[sz-1];
				int msuf=min(s2::ask(sz)-(i==0?0:B[i-1]),s1::ask(i)+B[sz-1]-(i==0?0:B[i-1]));
				int lun=1e9;
				if(a[itv]+msuf<=0)lun=0;
				else if(sm<0)lun=(a[itv]+msuf+(-sm)-1)/((-sm));
				if(lun==1e9)continue;
				a[itv]+=lun*sm;
				int pos=0;
				if(a[itv]+s2::ask(sz)-(i==0?0:B[i-1])<=0)
					pos=s2::bin(-(a[itv]-(i==0?0:B[i-1])))-i+1;
				else if(a[itv]+s1::ask(i)+B[sz-1]-(i==0?0:B[i-1])<=0)
					pos=s1::bin(-(a[itv]+B[sz-1]-(i==0?0:B[i-1])))+sz-i+1;//注意 
				else assert(0);
//				for(auto It:it.A)cerr<<It<<" ";
//				cerr<<"\n";
//				cerr<<"\n";
//				cerr<<lun<<" "<<sm<<" "<<itv<<" "<<lun<<" "<<pos<<" "<<(1ll*lun*sz+pos-1)*n+itv<<" "<<msuf<<" "<<s2::ask(sz)-(i==0?0:B[i-1])<<" "<<i<<"@\n";
				mn=min(mn,(1ll*lun*sz+pos-1)*n+itv);
			}
		}
	}
	if(mn>=1e18)puts("-1");
	else cout<<mn<<"\n";
	
	pc('1',1);
	return 0;
}

}signed main(){return ifzw::main();}