100114D

这道题用暴力水过了，蒟蒻是这么想的：枚举两个端点，找最小值，因为shift只能用一次，但是这样10^9*2.5要t，所以减掉只有一个黑点的情况，然后复杂度变为10^9*0.6

#include<iostream>

#include<vector>

#include<cstdio>

using namespace std;

int n,ll=-(<<),rr=-(<<),ans;

vector<int>left1;

vector<int>right1;

char c;

char s[];

int sum[];

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    cin>>n;

    int pos=;

    cin.ignore();

    for(int i=;i<=n;i++)

    {

        c=getchar();

        s[i]=c;

        sum[i]=sum[i-]+(c=='*');

    }

    s[]='.';

    s[++n]='.';

    for(int i=;i<=n;i++)

    {

        int l,r;

        if(s[i]=='*'&&s[i-]=='.'){l=i;left1.push_back(i);}

        if(s[i]=='*'&&s[i+]=='.')

        {

            r=i;

            if(r-l+<)

            {

                left1.pop_back();

                continue;

            }

            right1.push_back(i);

        }

    }

    int l=,r=;

    int MAX=-(<<);

    for(int i=;i<left1.size();i++)

    {

        for(int j=i;j<right1.size();j++)

        {

            int a=right1[j]-left1[i]+;

//            cout<<"left:"<<left1[i]<<endl;

//            cout<<"right:"<<right1[j]<<endl;

            int b=sum[right1[j]]-sum[left1[i]-];//操作数a-b+2和b比较

//            cout<<"MAX="<<MAX<<" "<<a<<" "<<b<<endl;

            if(a-b+<b&&MAX<*b-a-)

            {

                MAX=*b-a-;

                ll=left1[i];rr=right1[j];

            }

        }

    }

//    cout<<"ll="<<ll<<" "<<"rr="<<rr<<endl;

    if(MAX!=-(<<))

    {

        ans+=(+rr-ll-*(sum[rr]-sum[ll-]));

    }

    ans+=sum[n-];

//    cout<<sum[n]<<endl;

    cout<<ans<<endl;

    if(MAX!=-(<<))

    {

        cout<<ll<<endl;

        cout<<"Shift+"<<rr<<endl;

        for(int i=ll;i<=rr;i++)

            if(s[i]=='.')

            {

                cout<<"Ctrl+"<<i<<endl;

            }

    }

    if(ll==-(<<)&&rr==-(<<))

    {

        ll=;rr=;

    }

    for(int i=;i<ll;i++)

        if(s[i]=='*')cout<<"Ctrl+"<<i<<endl;

    for(int i=rr+;i<=n;i++)

        if(s[i]=='*')cout<<"Ctrl+"<<i<<endl;

    fclose(stdin);

    fclose(stdout);

    return ;

}