# Codeforces Global Round 17(Codeforces Global Round 17)-其他

## Codeforces Global Round 17(Codeforces Global Round 17)

### A. Anti Light’s Cell Guessing

#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

#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

#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

__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;
}

————————

### 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;
}