【2020五校联考NOIP #8】狗

题面传送门

原题题号：Codeforces 883D

题意：

有 \(n\) 个位置，每个位置上要么有一条狗，要么有一根骨头，要么啥都没有。

现在你要给每个狗指定一个方向（朝左或朝右）。

朝左的狗可以到达它左边的所有位置，朝右的狗可以到达它右边的所有位置。它们的速度均为 \(1\) 格\(/s\)

如果一个格子上有骨头，那么最先到达这个格子上的狗可以吃掉这个骨头。

求最多能吃掉多少个骨头，以及最少需要多长时间才能达到这个局面。

\(n \in [1,10^5]\)

显然，如果只有 \(1\) 只狗，那么就暴力枚举它朝左还是朝右，然后取个 \(\max\) 即可。

如果有 \(2\) 只狗及以上，那么所有骨头都能被吃掉。

难点在于第二问。考虑二分答案 \(x\)，需检查在 \(x\) 秒内这些狗能否吃掉所有骨头。

假设第 \(i\) 只狗的位置为 \(p_i\)，那么这只狗要么吃掉 \([p_i-x,p_i]\) 之间的骨头，要么吃掉 \([p_i,p_i+x]\) 之间的骨头。

考虑 \(dp\)。\(dp_i=j\) 表示按位置从小到大排序，第 \(1\) 到第 \(i\) 只狗最多能吃掉前 \(j\) 个位置上的所有骨头。

你再预处理 \(s_i\)，\(s_i\) 表示位置 \(1\) 到 \(i\) 总共多少个骨头。

分三种情况：

第 \(i\) 只狗向左走，也就是 \([p_i-x,p_i]\) 中有骨头没有被吃掉。这种情况满足的条件是前 \(i-1\) 只狗能够吃完 \([1,p_i-x-1)\) 中的所有骨头，也就是 \(dp_{i-1} \geq p_i-x\) 或 \(s_{p_i-x-1}=s_{dp_{i-1}}\)，i.e. \((dp_{i-1},p_i-x-1)\) 中没有骨头，并更新 \(dp_i=\max(dp_i,p_i)\)。
第 \(i\) 只狗向右走。这种情况的满足条件是 \([1,p_i)\) 中所有骨头都被前 \(i-1\) 条狗吃掉。也就是 \(dp_{i-1} \geq p_i\) 或 \(s_{p_i-1}=s_{dp_{i-1}}\)，并更新 \(dp_i=\max(dp_i,p_i+x)\)。
第 \(i\) 只狗向左走，第 \(i-1\) 只狗向右走。这种情况的满足条件是 \([p_{i-1},p_{i-1}+x]\cup[p_i-x,p_i]\) 可以包含 \([p_{i-1},p_i]\) 中所有骨头，并且 \(dp_{i-2} \geq p_{i-1}\) 或 \(s_{p_{i-1}-1}=s_{dp_{i-2}}\)，并更新 \(dp_i=\max(dp_i,\max(p_i,p_{i-1}+x))\)

为什么这三种情况能涵盖所有情况呢？

考虑一只向右走的狗。显然它前面所有骨头都被吃掉了，要么是被它左边的狗吃掉了（情况 2），要么是被它右边的狗吃掉了（情况 3）。

再考虑一只向左走的狗，根据上面的推论 \([1,p_i-x)\) 所有骨头都被吃掉了。而这些骨头只能被它左边的狗吃掉，所以只有 1 种情况，也就是情况 1。

/*

Contest: -

Problem: NFLSOJ 712

Author: tzc_wk

Time: 2020.10.20

*/

#include <bits/stdc++.h>

using namespace std;

#define fi			first

#define se			second

#define pb			push_back

#define fz(i,a,b)	for(int i=a;i<=b;i++)

#define fd(i,a,b)	for(int i=a;i>=b;i--)

#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define all(a)		a.begin(),a.end()

#define fill0(a)	memset(a,0,sizeof(a))

#define fill1(a)	memset(a,-1,sizeof(a))

#define fillbig(a)	memset(a,0x3f,sizeof(a))

#define y1			y1010101010101

#define y0			y0101010101010

typedef pair<int,int> pii;

typedef long long ll;

int n;char s[1000005];

int posd[1000005],cntd=0;

int posb[1000005],cntb=0;

int dp[1000005];

int hav[1000005];

inline bool check(int mid){

	memset(dp,0,sizeof(dp));

	for(int i=1;i<=cntd;i++){

		if(dp[i-1]>=posd[i]||hav[posd[i]-1]==hav[dp[i-1]]) dp[i]=max(dp[i],posd[i]+mid);

		if(dp[i-1]>=posd[i]-mid||hav[posd[i]-mid-1]==hav[dp[i-1]]) dp[i]=max(dp[i],posd[i]);

		else return 0;

		if(i>=2&&(posd[i-1]+mid>=posd[i]-mid||hav[posd[i-1]+mid]==hav[posd[i]-mid-1])&&(dp[i-2]>=min(posd[i-1],posd[i]-mid)||hav[dp[i-2]]==hav[min(posd[i-1],posd[i]-mid)-1]))

			dp[i]=max(dp[i],max(posd[i],posd[i-1]+mid));

		dp[i]=min(dp[i],n);

//		printf("%d %d\n",i,dp[i]);

	}

	if(hav[dp[cntd]]==hav[n]) return 1;

	return 0;

}

int main(){

	scanf("%d%s",&n,s+1);

	for(int i=1;i<=n;i++) if(s[i]=='D') posd[++cntd]=i;

	for(int i=1;i<=n;i++) if(s[i]=='B') posb[++cntb]=i;

	posb[cntb+1]=n+1;

	for(int i=0;i<=cntb;i++){

		for(int j=posb[i];j<posb[i+1];j++) hav[j]=i;

	}

	if(cntd==1){

		int cntl=0,cntr=0,mxl=0,mxr=0;

		for(int i=1;i<=posd[1];i++) if(s[i]=='B') cntl++,mxl=max(mxl,posd[1]-i);

		for(int i=posd[1];i<=n;i++) if(s[i]=='B') cntr++,mxr=max(mxr,i-posd[1]);

		if(cntl>cntr) printf("%d %d\n",cntl,mxl);

		else if(cntr>cntl) printf("%d %d\n",cntr,mxr);

		else printf("%d %d\n",cntl,min(mxl,mxr));

		return 0;

	}

//	check(4);

	int l=1,r=n,ans=-23987;

	while(l<=r){

		int mid=(l+r)>>1;

		if(check(mid)) ans=mid,r=mid-1;

		else l=mid+1;

	}

	printf("%d %d\n",cntb,ans);

	return 0;

}

巴特西

【2020五校联考NOIP #8】狗

最新文章

热门文章