Codeforces Global Round 17(Codeforces Global Round 17)

Codeforces Global Round 17

A. Anti Light’s Cell Guessing

坑点:\(n=1,m=1\) 时答案为 \(0\) 。

其他情况:当 \(n=1\) 或 \(m=1\) 时,只需要取端点即可。其他情况只需要两个点,也是取两个端点,把离一个点曼哈顿距离为固定值的点连成一条线段,可以发现这两个端点形成的线段只可能有一个交点,即隐藏点。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int _; cin>>_;
	while (_--) {
		ll n,m; cin>>n>>m;
		if(n==1&&m==1)cout<<0<<endl;
		else if(n==1||m==1)cout<<1<<endl;
		else {
			cout<<2<<endl;
		}
	}
    return 0;
}

B. Kalindrome Array

和之前cf出过的一题一模一样,那题是删字母,这题是删数字,不过都一样,因为可能删的值只可能有两个,枚举这两个可能值即可。

时间复杂度 \(O(n)\)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;
int a[N];

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int _; cin>>_;
	while (_--) {
		int n; cin>>n;
		rep(i,0,n)cin>>a[i];
		int lx=-1,ly=-1;
		int l=0,r=n-1;
		while(l<r){
			if(a[l]!=a[r]){
				if(lx==-1){
					lx=a[l]; ly=a[r];
					break;
				}
			}else{
				l++,r--;
			}
		}
		l=0,r=n-1;
		int flag=1;
		while(l<r){
			if(a[l]!=a[r]){
				if(a[l]==lx){
					while(l<r&&a[l]==lx)l++;
				}else if(a[r]==lx){
					while(l<r&&a[r]==lx)r--;
				}else{
					flag=0;
					break;
				}
				if(a[l]!=a[r]){
					flag=0;
					break;
				}
			}else{
				l++,r--;
			}
		}
		if(flag){
			cout<<"yes\n";
			continue;
		}
		l=0,r=n-1;flag=1;
		while(l<r){
			if(a[l]!=a[r]){
				if(a[l]==ly){
					while(l<r&&a[l]==ly)l++;
				}else if(a[r]==ly){
					while(l<r&&a[r]==ly)r--;
				}else{
					flag=0;
					break;
				}
				if(a[l]!=a[r]){
					flag=0;
					break;
				}
			}else{
				l++,r--;
			}
		}
		if(!flag){
			cout<<"no\n";
		}else{
			cout<<"yes\n";
		}
	}
    return 0;
}

C. Keshi Is Throwing a Party

由于答案具有单调性,考虑二分答案。于是问题就转化成了从 \(n\) 个人里选 \(k\) 个人,使他们都开心。

假设选了 \(k\) 个人的下标分别为 \(p_1,p_2,\cdots,p_k\) 。对于 \(i\in[1,k]\) ,都有

根据这个性质,我们就可以贪心地取了。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;
int r[N], p[N], n;

int check(int x) {
	int ans=0,cc=0;
	rep(i,0,n){
		if(cc+1>=x-r[i]&&cc+1<=p[i]+1)cc++;
	}
	return cc>=x;
}

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int _; cin>>_;
	while (_--) {
		cin>>n;
		rep(i,0,n)cin>>r[i]>>p[i];
		int l=1,r=n;
		while(l<r){
			int mid=l+r+1>>1;
			if(check(mid))l=mid;
			else r=mid-1;
		}
		cout<<l<<endl;
	}
    return 0;
}

D. Not Quite Lee

一个数 \(x\) 形成的连续数字的和可以表示为

于是一个数列 \((x_1,x_2,\cdots,x_k)\) 的合法性可以表示为

移项得

以下的幂次都是对于 \(2\) 而言。

当数列中有一个为奇数时,右边的最低幂次为 \(0\) ,最低幂次为 \(0\) 的数可以表示任何数,也就是说,当数列中有一个为奇数,该数列即合法。于是考虑数列中全为偶数的情况,等式右边的最低幂次一定比左边的最低幂次大 \(1\) 。因为 \(x\) 是偶数,\(x+1\) 是奇数,乘起来再除个 \(2\) 必定会丢失一个因子 \(2\) 。低幂次的可以表示高幂次的,高幂次的不能表示低幂次,而左边的最低幂次要比右边小,所以要保证数列中幂次为最低幂次的数有偶数个,才能使他们的最低幂次 \(+1\) ,从而被右边的表示出来。于是思路就显而易见了,枚举最低幂次,若这个幂次不为 \(0\) ,那只能挑偶数个,否则都可以选。

从 \(n\) 个数中挑偶数个数(不能不挑)的方案数为

其实根据二项式定理,二项式系数中的偶数项和奇数项的和其实是一样的,也就是说,上述的式子其实就是

然后就可以写了。一个小技巧,求一个数的幂次可以用内建函数 求得。

__builtin_ctz(x)
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;

ll qpow(ll a, ll b) {
	ll res=1;
	for(;b;b>>=1,a=(a*a)%P)if(b&1)res=res*a%P;
	return res;
}

int cc[35];

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif // !ONLINE_JUDGE
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int n; cin>>n;
	rep(i,0,n){
		int x; cin>>x;
		cc[__builtin_ctz(x)] ++;
	}
	ll ans=0, tot=0;
	for(int i=31;i>=0;i--){
		if(cc[i]){
			if(i) ans=(ans+qpow(2,tot)*(qpow(2,cc[i]-1)-1)%P)%P;
			else ans=(ans+qpow(2,tot)*(qpow(2,cc[i])-1)%P)%P;
			tot += cc[i];
		}
	}
	cout<<ans;
    return 0;
}
————————

Codeforces Global Round 17

A. Anti Light’s Cell Guessing

Pit point: when \ (n = 1, M = 1 \), the answer is \ (0 \).

Other situations: when \ (n = 1 \) or \ (M = 1 \), you only need to take the endpoint. In other cases, only two points are needed, i.e. two endpoints are taken, and the points with a fixed Manhattan distance from a point are connected into a line segment. It can be found that the line segment formed by these two endpoints can only have one intersection, that is, hidden points.

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int _; cin>>_;
	while (_--) {
		ll n,m; cin>>n>>m;
		if(n==1&&m==1)cout<<0<<endl;
		else if(n==1||m==1)cout<<1<<endl;
		else {
			cout<<2<<endl;
		}
	}
    return 0;
}

B. Kalindrome Array

As like as two peas that CF has done before, the problem is to delete the alphabet. This is the number of digits, but it is the same, because there may be only two possible values, and the two possible values are enumerated.

Time complexity \ (O (n) \)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;
int a[N];

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int _; cin>>_;
	while (_--) {
		int n; cin>>n;
		rep(i,0,n)cin>>a[i];
		int lx=-1,ly=-1;
		int l=0,r=n-1;
		while(l<r){
			if(a[l]!=a[r]){
				if(lx==-1){
					lx=a[l]; ly=a[r];
					break;
				}
			}else{
				l++,r--;
			}
		}
		l=0,r=n-1;
		int flag=1;
		while(l<r){
			if(a[l]!=a[r]){
				if(a[l]==lx){
					while(l<r&&a[l]==lx)l++;
				}else if(a[r]==lx){
					while(l<r&&a[r]==lx)r--;
				}else{
					flag=0;
					break;
				}
				if(a[l]!=a[r]){
					flag=0;
					break;
				}
			}else{
				l++,r--;
			}
		}
		if(flag){
			cout<<"yes\n";
			continue;
		}
		l=0,r=n-1;flag=1;
		while(l<r){
			if(a[l]!=a[r]){
				if(a[l]==ly){
					while(l<r&&a[l]==ly)l++;
				}else if(a[r]==ly){
					while(l<r&&a[r]==ly)r--;
				}else{
					flag=0;
					break;
				}
				if(a[l]!=a[r]){
					flag=0;
					break;
				}
			}else{
				l++,r--;
			}
		}
		if(!flag){
			cout<<"no\n";
		}else{
			cout<<"yes\n";
		}
	}
    return 0;
}

C. Keshi Is Throwing a Party

Because the answer is monotonous, consider the dichotomous answer. So the problem becomes to choose \ (K \) individuals from \ (n \) individuals to make them all happy.

Suppose that the subscripts of individuals with \ (K \) selected are \ (p_1, p_2, \ cdots, p_k \). For \ (I \ in [1, k] \), there are

According to this nature, we can take it greedily.

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;
int r[N], p[N], n;

int check(int x) {
	int ans=0,cc=0;
	rep(i,0,n){
		if(cc+1>=x-r[i]&&cc+1<=p[i]+1)cc++;
	}
	return cc>=x;
}

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int _; cin>>_;
	while (_--) {
		cin>>n;
		rep(i,0,n)cin>>r[i]>>p[i];
		int l=1,r=n;
		while(l<r){
			int mid=l+r+1>>1;
			if(check(mid))l=mid;
			else r=mid-1;
		}
		cout<<l<<endl;
	}
    return 0;
}

D. Not Quite Lee

The sum of consecutive numbers formed by a number \ (x \) can be expressed as

Therefore, the legitimacy of a sequence \ ((x_1, x_2, \ cdots, x_k) \) can be expressed as

Transferred item

The following powers are for \ (2 \).

When one of the sequence is odd, the number with the lowest power on the right is \ (0 \), and the number with the lowest power of \ (0 \) can represent any number, that is, when one of the sequence is odd, the sequence is legal. Therefore, considering that all numbers in the sequence are even, the lowest power on the right of the equation must be \ (1 \) greater than the lowest power on the left. Because \ (x \) is an even number and \ (x + 1 \) is an odd number, multiplying by and dividing by \ (2 \) will inevitably lose a factor \ (2 \). The low power can represent the high power, and the high power cannot represent the low power, and the lowest power on the left is less than that on the right. Therefore, it is necessary to ensure that there are even numbers of the lowest power in the sequence, so that their lowest power \ (+ 1 \) can be represented by the right. So the idea is obvious. Enumerate the lowest power. If the power is not \ (0 \), you can only choose an even number, otherwise you can choose all.

The number of schemes that select an even number (not optional) from the number of \ (n \) is

In fact, according to the binomial theorem, the sum of even and odd terms in binomial coefficients is actually the same, that is, the above formula is actually

Then you can write. A small skill to find the power of a number can be obtained with a built-in function.

__builtin_ctz(x)
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;

constexpr int N = 2e5+5, P = 1e9+7;

ll qpow(ll a, ll b) {
	ll res=1;
	for(;b;b>>=1,a=(a*a)%P)if(b&1)res=res*a%P;
	return res;
}

int cc[35];

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif // !ONLINE_JUDGE
    cin.tie(nullptr)->ios::sync_with_stdio(false);
	int n; cin>>n;
	rep(i,0,n){
		int x; cin>>x;
		cc[__builtin_ctz(x)] ++;
	}
	ll ans=0, tot=0;
	for(int i=31;i>=0;i--){
		if(cc[i]){
			if(i) ans=(ans+qpow(2,tot)*(qpow(2,cc[i]-1)-1)%P)%P;
			else ans=(ans+qpow(2,tot)*(qpow(2,cc[i])-1)%P)%P;
			tot += cc[i];
		}
	}
	cout<<ans;
    return 0;
}