Codeforces Global Round 17

A. Anti Light's Cell Guessing

坑點(diǎn)：\(n=1,m=1\) 時(shí)答案為 \(0\) 。

其他情況：當(dāng) \(n=1\) 或 \(m=1\) 時(shí)，只需要取端點(diǎn)即可。其他情況只需要兩個(gè)點(diǎn)，也是取兩個(gè)端點(diǎn)，把離一個(gè)點(diǎn)曼哈頓距離為固定值的點(diǎn)連成一條線段，可以發(fā)現(xiàn)這兩個(gè)端點(diǎn)形成的線段只可能有一個(gè)交點(diǎn)，即隱藏點(diǎ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 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出過(guò)的一題一模一樣，那題是刪字母，這題是刪數(shù)字，不過(guò)都一樣，因?yàn)榭赡軇h的值只可能有兩個(gè)，枚舉這兩個(gè)可能值即可。

#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

由于答案具有單調(diào)性，考慮二分答案。于是問(wèn)題就轉(zhuǎn)化成了從 \(n\) 個(gè)人里選 \(k\) 個(gè)人，使他們都開(kāi)心。

假設(shè)選了 \(k\) 個(gè)人的下標(biāo)分別為 \(p_1,p_2,\cdots,p_k\) 。對(duì)于 \(i\in[1,k]\) ，都有

根據(jù)這個(gè)性質(zhì)，我們就可以貪心地取了。

#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

一個(gè)數(shù) \(x\) 形成的連續(xù)數(shù)字的和可以表示為

于是一個(gè)數(shù)列 \((x_1,x_2,\cdots,x_k)\) 的合法性可以表示為

移項(xiàng)得

為表示簡(jiǎn)略，以下的冪次都是指 \(2\) 的冪次。

當(dāng)數(shù)列中有一個(gè)為奇數(shù)時(shí)，右邊的最低冪次為 \(0\) ，最低冪次為 \(0\) 的數(shù)可以表示任何數(shù)，也就是說(shuō)，當(dāng)數(shù)列中有一個(gè)為奇數(shù)，該數(shù)列即合法。于是考慮數(shù)列中全為偶數(shù)的情況，等式右邊的最低冪次一定比左邊的最低冪次大 \(1\) 。因?yàn)?\(x\) 是偶數(shù)，\(x+1\) 是奇數(shù)，乘起來(lái)再除個(gè) \(2\) 必定會(huì)丟失一個(gè)因子 \(2\) 。低冪次的可以表示高冪次的，高冪次的不能表示低冪次，而左邊的最低冪次要比右邊小，所以要保證數(shù)列中冪次為最低冪次的數(shù)有偶數(shù)個(gè)，才能使他們的最低冪次 \(+1\) ，從而被右邊的表示出來(lái)。于是思路就顯而易見(jiàn)了，枚舉最低冪次，若這個(gè)冪次不為 \(0\) ，那只能挑偶數(shù)個(gè)，否則都可以選。

從 \(n\) 個(gè)數(shù)中挑偶數(shù)個(gè)數(shù)（不能不挑）的方案數(shù)為

其實(shí)根據(jù)二項(xiàng)式定理，二項(xiàng)式系數(shù)中的偶數(shù)項(xiàng)和奇數(shù)項(xiàng)的和其實(shí)是一樣的，也就是說(shuō)，上述的式子其實(shí)就是

然后就可以寫(xiě)了。一個(gè)小技巧，求一個(gè)數(shù)的冪次可以用內(nèi)建函數(shù) __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;
}