小白月赛96

小白月赛96

• • a最小胜利数
  • b最小操作次数
  • c最多数组数量

a最小胜利数

最小胜利数

1. 只要有一个超过6次，那么便不可能反败为胜
2. 求出两位选手的题目差+1，即为反败为胜的条件

ac code

#include<iostream>
using namespace std;
int main(){
    string a;cin>>a;int alen=a.length();
    string b;cin>>b;int blen=b.length();
    if(alen==6||blen==6)cout<<"-1";
    else{
        int res;
        res=abs(alen-blen)+1;
        cout<<res;
    }
    return 0;
}

b最小操作次数

最小操作次数

这题分情况讨论吧

1. 如果0，1的数量不一样的话，一次操作即可全部转换
2. 如果全为0或者全为1的话，就不需要任何操作，答案为0
3. 如果0和1的个数相等的话，那么就需要两次，比如010101010101，需要先把任何一段变成1或者0，这样全部序列中0和1的数量就不对等了，便可得到答案，总次数为2次

ac code

#include<iostream>
using namespace std;
int main(){
    int n;cin>>n;
    string a;cin>>a;
    int tmp1=0,tmp2=0;
    for(int i=0;i<a.length();i++){
        if(a[i]=='0')tmp1++;
        else tmp2++;
    }
    if(tmp1==tmp2){
        if(a.length()==2)cout<<"-1";
        else
        cout<<"2";
    }
    else if(tmp1==0||tmp2==0){
        cout<<"0";
    }
    //cout<<tmp1<<" "<<tmp2;
    else cout<<"1";
    return 0;
}

c最多数组数量

最多数组数量

1. 做法是双指针+前缀和，前缀和处理的目的是方便每次求和，双指针用来快速求符合的条件
2. i，j作为指针，从1，2分别开始向后走，当i，j区间内的和大于两边区间的和的时候，就视为一种情况，那么这时候j一直向后延申，条件也一直成立，那么res=n-2-j，2是因为下标为0且不能与数组结尾重合

ac code

#include<iostream>
using namespace std;

const int N=1e6;
int arr[N];
int res;
int main(){
    int n;cin>>n;
    //这里首先处理一下前缀和
    for(int i=0;i<n;i++){
        cin>>arr[i];
        arr[i]+=arr[i-1];
    }
    //接下来是双指针
    for(int i=0,j=1;i<n-1&&j<n-1&&i<j;){
        int tmp1=arr[i];
        int tmp2=arr[j]-arr[i];
        int tmp3=arr[n-1]-arr[j];
        //cout<<i<<" "<<j<<endl;
        //cout<<tmp1<<" "<<tmp2<<" "<<tmp3<<endl;
        if(tmp2>tmp1&&tmp2>tmp3&&i<j){
            res++;
            res+=(n-2-j);
            //cout<<i<<" "<<j<<endl;
            i++;
            //cout<<res<<endl;
        }
        else j++;
    }
    cout<<res;
    return 0;
}