神秘做法求 Hack

大概思路是把相邻企鹅之间的距离列成一个数组

d

（默认

0,L+1

处各有一只企鹅），最终只需要使这个距离数组与

B

的距离数组对位相等。

发现一次操作形如将

d_{i+1}\leftarrow d_{i+1}+d_i,d_i\leftarrow 0

或者

d_{i-1}\leftarrow d_{i-1}+d_i,d_i\leftarrow 0

。所以可以从左到右贪心（？）。

令

d'_i

表示

B

的距离数组，

d_i

表示当前

A

的距离数组。如果

d_i=d'_i

，无事发生；如果

d_i>d'_i

，则需要判断

d'_i

是否等于

0

，是则将

d_i

移到

d_{i+1}

上，否则无解（？）；如果

d_i<d'_i

，则需要将一段从

i

开始的一段区间的

d

全移动到

d_i

上，使之恰好等于

d'_i

，如果不能恰好等于则无解（？）。感觉这么做步数是最少的吧（？）。

用线段树维护上述过程。

然而我这么写并没有通过此题，使用数组代替线段树仍有答案错误的点，有无大佬orz指出算法/代码错误。

代码如下：

CPP

#include <bits/stdc++.h>
#define fin(str) freopen(str,"r",stdin)
#define fout(str) freopen(str,"w",stdout)
#define ll long long
using namespace std;

bool MEM_beg;

const int maxn=2e5+5;

int n,L,a[maxn],b[maxn],a0[maxn],b0[maxn];
ll ans;

namespace SGT{
	#define lc(p) ((p)<<1)
	#define rc(p) ((p)<<1|1)
	struct segment{
		int cov,sum;
	}c[maxn<<2];
	inline void pushdown(int rt,int l,int r){
		if (c[rt].cov==-1) return ;
		c[lc(rt)].cov=c[rt].cov;
		c[rc(rt)].cov=c[rt].cov;
		int mid=(l+r)>>1;
		c[lc(rt)].sum=(mid-l+1)*c[rt].cov;
		c[rc(rt)].sum=(r-(mid+1)+1)*c[rt].cov;
		
		c[rt].cov=-1; 
	}
	inline void pushup(int rt){
		c[rt].sum=c[lc(rt)].sum+c[rc(rt)].sum;
	}
	inline void build(int rt,int l,int r){
		c[rt].cov=-1,c[rt].sum=0;
		if (l==r){
			c[rt].sum=a[l];
			return ;
		}
		int mid=(l+r)>>1;
		build(lc(rt),l,mid);
		build(rc(rt),mid+1,r);
		pushup(rt);
	}
	inline void cover(int rt,int l,int r,int ql,int qr,int k){
		if (l>=ql && r<=qr){
			c[rt].cov=k;
			c[rt].sum=(r-l+1)*k;
			return ;
		}
		pushdown(rt,l,r);
		int mid=(l+r)>>1;
		if (ql<=mid) cover(lc(rt),l,mid,ql,qr,k);
		if (qr>mid) cover(rc(rt),mid+1,r,ql,qr,k);
		pushup(rt);
	}
	inline int query(int rt,int l,int r,int ql,int qr){
		if (l>=ql && r<=qr) return c[rt].sum;
		int mid=(l+r)>>1;
		pushdown(rt,l,r);
		int res=0;
		if (ql<=mid) res+=query(lc(rt),l,mid,ql,qr);
		if (qr>mid) res+=query(rc(rt),mid+1,r,ql,qr);
		return res;
	}
	inline int search(int rt,int l,int r,int k){		
		if (l==r) return l;
		pushdown(rt,l,r);
		int mid=(l+r)>>1;
		if (c[lc(rt)].sum>=k) return search(lc(rt),l,mid,k);
		else return search(rc(rt),mid+1,r,k-c[lc(rt)].sum);
	}
}using namespace SGT;

bool MEM_end;
int main(){
//	fin("data.in");
//	fout("data.out"); 
	scanf("%d%d",&n,&L);
	for (int i=1;i<=n;i++) scanf("%d",&a0[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b0[i]);
	
	n++;
	a0[n]=b0[n]=L+1;
	for (int i=1;i<=n;i++){
		a[i]=a0[i]-a0[i-1]-1;
		b[i]=b0[i]-b0[i-1]-1;
	}
	
	build(1,1,n);
	
	int res=query(1,1,n,1,n);
//	for (int i=1;i<=n;i++) printf("%d ",b[i]);
//	printf("\n-----------------\n");
//	for (int i=1;i<=n;i++) printf("%d ",a[i]);
//	putchar('\n');
	for (int i=1;i<=n;i++){
		int cur=query(1,1,n,i,i);
		if (cur>b[i]){
			if (b[i]==0){
				int pre=query(1,1,n,i+1,i+1);
				cover(1,1,n,i,i,0);
				cover(1,1,n,i+1,i+1,pre+cur);
				ans++;
			}else{
				printf("-1\n");
				return 0;
			}
		}else if (cur<b[i]){
			int pres=0;
			if (i>1) pres=query(1,1,n,1,i-1);
			int p=search(1,1,n,pres+b[i]);
			assert(p>=i && p<=n);
			if (query(1,1,n,1,p)-pres!=b[i]){
				printf("-1\n");
				return 0;
			}else{
				cover(1,1,n,i,p,0);
				cover(1,1,n,i,i,b[i]);
				ans+=p-i;
			}
		}
		
//		for (int j=1;j<=n;j++) printf("%d ",query(1,1,n,j,j));
//		putchar('\n');

		assert(res==query(1,1,n,1,n));
	}
	
	printf("%lld\n",ans);
	
	cerr<<"\nMemory : "<<1.0*abs(&MEM_end-&MEM_beg)/1048576<<" MB\n";
	return 0;
}

讨论操作

回复

相关推荐

神秘做法求 Hack