牛客练习赛80

比赛地址：https://ac.nowcoder.com/acm/contest/11170#question

A：
分以下 3 种情况：
1、如果存在长度为 1 的极长全 1 子串，那么将这个子串反转，变为 0 ，答案减少 1 ，例如 100110011
2、如果存在一个 0 ，在两个全 1 子串中间，则把这个 0 反转变成 1 ，答案减少 1 ，例如 11101100
3、以上情况都没有，用O（n）复杂度算出权重，即答案

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int ans=0,f=0;
    for(int i=0;i<s.size();)
    {
        int j,chang=0;
        for(j=i;j<s.size();j++)
        {
            if(s[j]=='0')    break;
            chang++;
        }
        if(chang==1)
        {
            f=1;
        }
        if(chang!=0)    ans++;
        i=j+1;
    }
    for(int i=1;i<s.size()-1;i++)
    {
        if(s[i]=='0'&&s[i-1]=='1'&&s[i+1]=='1')    f=1;
    }
    if(f==1)    cout<<ans-1<<endl;
    else    cout<<ans<<endl; 
    return 0;
}

B：
为了方便，以下题解及程序的数组下标从1开始（题目从0开始），用j表示a[j]，k表示b[k]，ansa表示a数组所有元素之和，ansb表示b数组所有元素之和。
我们分以下4种情况来分类讨论：
i = 1：j 和 k 必须 ≥ 2，则
          

          

          

          

#include<bits/stdc++.h>
using namespace std;
const long long modd=998244353;
const int maxn=1e5+10;
long long a[maxn],b[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    long long ansa=0,ansb=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        ansa+=a[i];
        ansa%=modd;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&b[i]);
        ansb+=b[i];
        ansb%=modd;
    }
    long long ans1,ans2;

    ans1=ansa-a[1],ans2=ansb-b[1];
    if(ans1<0)    ans1+=modd;
    if(ans2<0)    ans2+=modd;
    cout<<(ans1*ans2)%modd<<" ";

    ans1=ansa-a[2],ans2=ansb-b[2];
    if(ans1<0)    ans1+=modd;
    if(ans2<0)    ans2+=modd;
    ans1-=a[1],ans2-=b[1];
    if(ans1<0)    ans1+=modd;
    if(ans2<0)    ans2+=modd;
    cout<<(((ans1*b[1])%modd+(ans2*a[1])%modd)%modd+(a[1]*b[1])%modd)%modd<<" ";

    cout<<((a[1]*b[2])%modd+(b[1]*a[2])%modd)%modd<<" ";

    for(int i=4;i<=n;i++)
    {
        printf("0 ");
    }
    printf("\n");
    return 0;
}