Codeforces Round #645 (Div.2)

比赛链接 / 官方题解链接

A. Park Lighting

Solution

每两个格子用一盏灯点亮，如果总数为奇数就再增加一盏灯。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, n, m;

int main(){
	for(read(T); T; T--){
		read(n, m);
		printf("%d\n", n * m / 2 + (n * m % 2 == 1));
	}
	return 0;
}

---

B. Maria Breaks the Self-isolation

Solution

从小到大排序，然后依次枚举，但凡能邀请就邀请进来。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n, a[N];

int main(){
	for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i]), a[i]++;
		sort(a+1, a+n+1);
		int now = 1;
		for(int i = 1; i <= n; i++){
			int j = i;
			while(j <= n && now + j - i + 1 < a[j])
				j++;
			if(j == n + 1)	break;
			now += j - i + 1;
			i = j;
		}
		printf("%d\n", now);
	}
	return 0;
}

---

C. Celex Update

Solution

在由 $(x_1,y_1)$ 和 $(x_2,y_2)$ 确定的矩形中，和最小的路径是往右走到底再往下走，和最大的路径是往下走到底再往右走，凡落在这个最大值和最小值之间的数字都可以通过走某条路径得到（因为和数加一就是将一个“右-下”改成“下-右”），所以答案就是这个最大值减去这个最小值加一。

设 $m$ 是矩形小的边长，$n$ 是矩形大的边长，那么最大值减去最小值就是 $1+2+\cdots+(m-1)+(m-1)+\cdots+(m-1)+\cdots+2+1$，一共 $n+m-3$ 项，所以 $上式=(m-1)(m-2)+(n+m-3-2(m-2))(m-1)=(m-1)(n-1)$.

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, X1, Y1, X2, Y2;

int main(){
	for(read(T); T; T--){
		read(X1, Y1, X2, Y2);
		int mn = min(X2 - X1 + 1, Y2 - Y1 + 1);
		int mx = max(X2 - X1 + 1, Y2 - Y1 + 1);
		printf("%lld\n", 1ll * (mn - 1) * (mx - 1) + 1);
	}
	return 0;
}

---

D. The Best Vacation

Solution

解决循环只需要把原数组扩倍。

首先发现性质：答案的端点一定是某区间的端点。所以双指针扫一遍即可。

复杂度：$O(n)$

P.S. 其实上面的性质弱了，官方题解里面证明了答案的右端点一定是某区间的右端点，这样代码可以写得简单些。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 400005;

LL n, x, d[N], sum[N];

inline LL get(LL l, LL r){
	return (l + r) * (r - l + 1) / 2;
}

int main(){
	read(n, x);
	for(int i = 1; i <= n; i++)
		read(d[i]), d[i+n] = d[i];
	for(int i = 1; i <= 2 * n; i++)
		sum[i] = sum[i-1] + d[i];
	LL ans = 0;
	LL l = 1, ll = 1, r = 1, rr = 1;
	while(sum[r] - sum[l-1] < x){
		ans += d[r] * (d[r] + 1) / 2;
		r++;
	}
	rr = x - sum[r-1];
	ans += (x - sum[r-1]) * (x - sum[r-1] + 1) / 2;
	LL res = ans;
	while(r <= 2 * n){
		LL step = min(d[l] - ll, d[r] - rr);
		if(step > 0){
			res -= get(ll, ll + step - 1);
			res += get(rr + 1, rr + step);
			ll += step, rr += step;
			ans = max(ans, res);
		}

		ll++;
		if(ll > d[l]){
			res -= d[l];
			l++;
			ll = 1;
		}
		else{
			res -= ll - 1;
		}
		rr++;
		if(rr > d[r]){
			res += 1;
			r++;
			rr = 1;
		}
		else{
			res += rr;
		}
		ans = max(ans, res);
	}
	printf("%lld\n", ans);
	return 0;
}

---

E. Are You Fired?

Solution

首先有性质：存在 $k>\left\lfloor\frac{n}{2}\right\rfloor$ 满足要求，这是因为如果我们找到了某个 $k\leq\left\lfloor\frac{n}{2}\right\rfloor$ 满足要求，那么 $2k$ 一定也满足要求。

如果 $x\geq0$，我们只需要看所有数的和是否大于 $0$。因为如果所有数的和小于 $0$，我们一定可以把 $1\sim \left\lceil\frac{n}{2}\right\rceil$ 分成两段，前一段和为正，后一段和为负，但凡包含了和为负的这一段的区间总和一定为负，所以无解。

如果 $x<0$，设一个初始区间为 $[1,n]$（$k=n$），如果这一段区间和非正，那么我们缩减 $k$，也就是新区间左端点是前一个区间左端点加一，然后前面所有区间的右端点减一，由于这些右端点一定在后 $\left\lfloor\frac{n}{2}\right\rfloor$ 这一段里，所以这些区间总和均减 $x$。查看现在是否有某区间的和非正（记录一个区间和最小值即可），如果有，继续缩减 $k$，否则输出答案。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 500005;

int n;
LL a[N], x, s[N];

int main(){
	read(n);
	for(int i = 1; i <= (n + 1) / 2; i++)
		read(a[i]);
	read(x);
	for(int i = (n + 1) / 2 + 1; i <= n; i++)
		a[i] = x;
	for(int i = 1; i <= n; i++)
		s[i] = a[i] + s[i-1];
	if(x < 0){
		LL mn = s[n];
		if(mn > 0){ printf("%d\n", n); return 0; }
		for(int i = 2; i <= (n + 1) / 2; i++){
			mn -= x;
			mn = min(mn, s[n] - s[i-1]);
			if(mn > 0){ printf("%d\n", n-i+1); return 0;}
		}
		puts("-1");
		return 0;
	}
	else{
		if(s[n] > 0)	printf("%d\n", n);
		else	puts("-1");
		return 0;
	}
}