P12663 [KOI 2023 Round 2] 湖边的蚁穴题解

首先，读一下题，能够有一个结论：如果有小房间时让蚂蚁进小房间为最好的情况。

证明：

因为题目中提到：“当前蚁穴的每条通道最多只能连接一只住着蚂蚁的位置”，所以进小房间我们就能保证目前的大房间一定没有蚂蚁住，从而使附近的两个房间均可居住。

接下来，可以枚举两种情况：

从一号房间开始居住；
从二号房间开始居住。

循环体内进行以下几个操作：

判断当前房间 $i$ 是否有小房间，如果有，答案加上小房间数；
若前一个或后一个房间有小房间并且前一个房间没有蚂蚁居住，答案加 $1$ ，并标记当前房间有蚂蚁；
若前一个房间没有蚂蚁居住，答案加 $1$ ，并标记当前房间有蚂蚁。

需要注意的是，从一号房间开始住的话需要判断

1

号和

n

号房间是否同时有蚂蚁居住，如果有，答案减

1

。

具体代码如下：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,cnt;
struct node{
	int pd,so,c;//pd表示是否有小房间，so表示小房间数，c表示是否选择过
}e[250010],e1[250010];//e表示情况1，e1表示情况2 
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>e[i].so,e[i].pd=((e[i].so)?1:0),e1[i]=e[i];//预处理，判断是否有小房间 
	for(int i=1;i<=n;i++)//情况1
		if(e[i].pd) cnt+=e[i].so;
		else if((e[i+1].pd||e[i-1].pd)&&!e[i-1].c) cnt++,e[i].c=1;
		else if(!e[i-1].c) cnt++,e[i].c=1;
	if(e[1].c&&e[n].c) cnt--;//特判 
	ans=max(ans,cnt);//记录答案 
	cnt=0;
	for(int i=2;i<=n;i++)//情况2 
		if(e1[i].pd) cnt+=e1[i].so;
		else if((e1[i+1].pd||e1[i-1].pd)&&!e1[i-1].c) cnt++,e1[i].c=1;
		else if(!e1[i-1].c) cnt++,e1[i].c=1;
	ans=max(ans,cnt);
	cout<<ans;//输出答案
	return 0; 
}

P12663 [KOI 2023 Round 2] 湖边的蚁穴题解

文章操作

证明：

相关推荐

评论

P12663 [KOI 2023 Round 2] 湖边的蚁穴题解