Codeforces Round 935 (Div. 3)（A,B,C,D,E,F）

比赛链接

阳间场，阴间题，最考阅读理解的一场。题目本身的难度不大。

---

A. Setting up Camp

题意：

组委会计划在奥运会结束后带领参赛者进行一次徒步旅行。目前，需要携带的帐篷数量正在计算中。据了解，每个帐篷最多可容纳 $3$ 人。在参与者中，有 $a$ 个内向者、 $b$ 个外向者和 $c$ 个共通者：

• 每个内向的人都想独自住在帐篷里。因此，内向者的帐篷必须只容纳一个人——只有内向者自己。

• 每个外向的人都想和另外两个人住在一个帐篷里。因此，外向者的帐篷必须正好容纳三个人。

• 共通者任何选择(独自生活，与另一个人一起生活，或与另外两个人一起生活)都可以接受。

组委会非常尊重每一位参赛者的意愿，所以他们想全部兑现。

告诉我们需要携带的帐篷的最小数量，以便所有参与者可以根据自己的喜好进行住宿。

如果无法以满足所有愿望的方式容纳参与者，则输出 $-1$ 。

思路：

内向者好说，一人一个帐篷，共通者也好说，哪里不够塞哪里。主要是外向者，因为必须三人一个帐篷的限制，所以我们先给外向者三人分一个帐篷，有可能会剩下不足三人，这时用共通者补上，如果补不上，就无解，否则就有解。

code：

#include <iostream>
#include <cstdio>
using namespace std;

int T,a,b,c;

int main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>c;
		int d=(3-b%3)%3,ans=a+(b+c+2)/3;
		if(d>c)cout<<-1<<endl;
		else cout<<ans<<endl;
	}
	return 0;
} 

---

B. Fireworks

题意：

徒步旅行的其中一天恰逢假期，所以晚上在营地，人们决定安排一场喜庆的烟花表演。为了这个目的，这次远足的组织者购买了两个发射烟花的装置和数量巨大的发射炮弹。两个装置安装后同时打开。

第一个装置打开后每 $a$ 分钟放一次烟花(即启动后 $a,2\cdot a,3\cdot a,\dots$ 分钟放一次烟花)。第二个装置打开后每 $b$ 分钟放一次烟花(即发射后 $b,2\cdot b,3\cdot b,\dots$ 分钟放一次烟花)。

每个烟花在发射后 $m+1$ 分钟内在天空中可见，即，如果在安装开启后 $x$ 分钟后发射烟花，则从 $x$ 到 $x+m$ (含)每分钟都可见。如果一个烟花在另一个烟花发射后 $m$ 分钟发射，则两个烟花都将在第 $x+m$ 这一分钟内同时可见。问，在同一时间，天空中最多可以看到多少烟花？

思路：

看似比较麻烦，我们不妨转化一下思路：在某一个时间 $t$ 上看到的所有烟花是前面第 $t-m\sim t$ 时间段上释放的所有烟花。那么问题就转化成了：找一个时间段，长为 $m+1$，使得这个时间段上释放的烟花最多。

如果我们要让一个烟花在一个时间段上释放的次数最多，根据贪心的思想，显然我们时间区间左端点应该选在这个烟花刚刚释放的时候，假如这个烟花释放间隔是 $a$，那么这个时间段上烟花会释放 $\lfloor \frac{m}{a}\rfloor +1$ 次。

同理，两个烟花也是如此，我们希望区间左端点选在两个烟花同时释放的时候。问题在于这两个烟花存在同时释放的情况的吗？如果两个烟花是倍数关系，那么显然存在，如果不是倍数关系，那么两个数的最小公倍数时刻就是两个烟花同时释放的时刻。因此两个烟花一定存在同时释放的情况。因此两个烟花总的释放次数就是 $\lfloor \frac{m}{a}\rfloor +\lfloor \frac{m}{b}\rfloor +2$。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

int T;
ll a,b,m; 


int main(){
	cin>>T;
	while(T--){
		cin>>a>>b>>m;
		cout<<m/a+m/b+2<<endl;
	}
	return 0;
}

---

C. Left and Right Houses

题意：

在列托沃村，有 $n$ 栋房屋。村民们决定修一条大路，把村子分成左右两边。每个居民都想住在街道的右边或左边，这被描述为序列 $a_1,a_2,\dots ,a_n$ 。其中如果 $a_j=0$ ，表示第 $j$ 栋房屋的住户想住在街道的左侧，否则 $a_j=1$，表示住户想住在街道右侧 。

这条路将从两座房子之间穿过。它左边的房子将被宣布为左边，右边的房子将被宣布为右边。更正式地说，让道路在房屋 $i$ 和 $i+1$ 之间通过。那么位于 $1$ 和 $i$ 之间的房屋将位于街道的左侧。在 $i+1$ 和 $n$ 之间的房屋将位于右侧。在这种情况下，道路也可以在第一栋房子之前和最后一栋房子之后通过。整个村庄分别被宣布为右侧或左侧。

为了使设计公平，人们决定铺设这条路，使得村庄两边至少有一半的居民对这一选择感到满意。也就是说，在一边的 $x$ 个居民中，至少有 $\lceil \frac{x}{2}\rceil$ 个应该想住在那一边，其中 $\lceil x\rceil$ 表示实数 $x$ 向上取整数。

注：在路的左边，将有 $i$ 个房子，在相应的 $a_j$ 中必须至少有 $\lceil \frac{i}{2}\rceil$ 个 $0$。在路的右边，将有 $n-i$ 栋房屋，在相应的 $a_j$ 中，必须至少有 $\lceil \frac{n-i}{2}\rceil$ 个 $1$。

确定在哪个房屋 $i$ 之后应铺设道路，以满足所描述的条件，并尽可能靠近村庄的中心。形式上说，在所有合适的位置 $i$ 中，最小化 $\left|\frac{n}{2}-i\right|$ 。

如果有多个合适的位置，则输出较小的位置。

思路：

前半部分要求 $0$ 的个数不少于总个数的一半，话句话说就是 $0$ 的个数要多于等于 $1$，同理后半部分就是 $1$ 的个数要多于等于 $0$。

想要快速求得一个区间 $1$ 的个数和 $0$ 的个数的差值，朴素的想法可以分别处理 $1$ 和 $0$ 的前缀和，不过不用这么麻烦，我们可以把 $1$ 看成 $1$，把 $0$ 看成 $-1$，这样跑出来的前缀和直接就是 $1$ 的个数减去 $0$ 的个数的差值。

因为查询很快，只有 $O(1)$，我们直接从中间向两边枚举分割线位置，第一个找到的位置就是答案。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=3e5+5;

int T,n;
string str;

int s[maxn];

inline bool check(int x){
	return s[x]-s[0]<=0 && s[n]-s[x]>=0;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>str;
		str=" "+str;
		for(int i=1;i<=n;i++)
			s[i]=s[i-1]+(str[i]=='0'?-1:1);
		
		for(int l=n/2,r=(n+1)/2;l>=0;l--,r++){
			if(check(l)){
				cout<<l<<endl;
				break;
			}
			if(check(r)){
				cout<<r<<endl;
				break;
			}
		}
	}
	return 0;
}

---

D. Seraphim the Owl

题意：

这些人排成 $n$ 人的队列，从第 $i=1$ 人开始，向猫头鹰Serafim询问生命的意义。不幸的是，基里尔正忙着为这个问题写传奇，所以他晚到了一会儿，站在队伍的最后，排在第 $n$ 个人的后面。基里尔对这种情况非常不满，所以他决定先贿赂一些人。对于队列中的第 $i$ 个人，Kirill知道两个值： a i a_i a