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出过的一题一模一样，那题是删字母，这题是删数字，不过都一样，因为可能删的值只可能有两个，枚举这两个可能值即可。

#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]\) ，都有

\[b_{p_i}\ge i-1\\
a_{p_i}\ge k-i
\]

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

#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\) 形成的连续数字的和可以表示为

\[\frac{x(x+1)}{2}+kx(k\in \text{Z})
\]

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

\[\sum_{i=1}^k(\frac{x_i(x_i+1)}{2}+k_ix_i)=0 \ (k_i\in \text{Z})
\]

移项得

\[\sum_{i=1}^k\frac{x_i(x_i+1)}{2}=\sum_{i=1}^kk_ix_i \ (k_i\in \text{Z})
\]

为表示简略，以下的幂次都是指 \(2\) 的幂次。

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

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

\[\binom{2}{n}+\binom{4}{n}+\cdots+\binom{\lfloor\frac{n}{2}\rfloor \times2}{n}
\]

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

\[2^{n-1}-\binom{0}{n}=2^{n-1}-1
\]

然后就可以写了。一个小技巧，求一个数的幂次可以用内建函数 __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

Codeforces Global Round 17

A. Anti Light's Cell Guessing

B. Kalindrome Array

C. Keshi Is Throwing a Party

D. Not Quite Lee

最新文章

热门文章