Codeforces Global Round 17 A B C

A. Anti Light’s Cell Guessing

题意大概就是你最少查询几个点，使得任意隐藏的位置一定能通过回馈的哈密顿距离确定。有三种情况$1：只有一行一列时，那么不用查询，那么答案也就是0$$2：行或列中有一个是1，那么我们也可以通过查询临界点来确定任意的隐藏位置，答案是1$ $3：行或列都大于1，那么答案是2，我们可以通过查询同一侧的两个底角来确定任意隐藏点$

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        if(a==1&&b==1){
            cout<<0<<endl;
        }
        else if(a==1||b==1){
            cout<<1<<endl;
        }
        else cout<<2<<endl;
    }

    return 0;
}

B. Kalindrome Array

很容易想到的是双指针，之前CF有一场出现过字符暴力双指针。但是这题不能直接裸暴力，复杂度会高达$1e10$的级别，然后加上一点思维，容易发现我们通过双指针的移动，直至左指针与右指针指向的数不同，当然如果$i>=j$我们可以直接返回，因为已经满足回文，否则记录左指针指的数和右指针指的数然后分别操作一遍，然后判断最终能不能构造成回文。

• 参考代码

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        int st=1,end=n;
        while(a[st]==a[end]){
            st++,end--;
        }
        if(st>=end){
            cout<<"YES"<<endl;
            continue;
        }
        int x1=a[st],x2=a[end];
        int st1=st,end1=end;//复制一下当前的st和end,因为我们还要进行第二次操作。
        bool success=false;
        while(st1<end1){
            if(a[st1]==a[end1])st1++,end1--;
            else if(a[st1]==x1)st1++;
            else if(a[end1]==x1)end1--;
            else break;
            if(st1>=end1)success=true;
        }
        st1=st,end1=end;
        while(st1<end1){
            if(a[st1]==a[end1])st1++,end1--;
            else if(a[st1]==x2)st1++;
            else if(a[end1]==x2)end1--;
            else break;
            if(st1>=end1)success=true;
        }
        if(success)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

C. Keshi Is Throwing a Party

这道题是一个二分检验的题目，没学过的同学推荐看一下acwing中有的最佳牛围栏这一道题，加上检验中有贪心的思想。

• 参考代码

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int n;
struct{
    int a,b,c;
}nodes[N];
bool check(int x){
    int num=0;
    int l=0,r=x-1;//l表示左边有多少poorer,r表示右边有多少richer,一开始初始化第一个人那么左边为0,右边为x-1。
    for(int i=1;i<=n;i++){
        int b=nodes[i].b,c=nodes[i].c;
        if(l<=b&&r<=c){num++;l++,r--;}//如果当前人可取我们才进行num++,以及l和r的更新。
    }
    if(num>=x)return true;//如果num>=x说明我能够取到不低于x的人数。
    return false;
}
signed main(){
    snow;
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            nodes[i].a=i;
            cin>>nodes[i].c>>nodes[i].b;//b放poorer,c放richer。
        }
        int l=1,r=n;//人数在1~n中检验
        while(l<r){
            int mid=l+r+1>>1;
            if(check(mid))l=mid;//如果当前人数满足,那么我们将区间延后。
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}