FaceTheRightWay(POJ3276开关问题)xiaodangao

题目链接：Face The Right Way
思路：枚举区间长度，我们选择从左往右处理，利用前缀和的思想，前缀和代表的是当前左指针指向的牛改变过多少次朝向，每一次满足左指针指向的牛，让他朝前方，然后如果当前牛朝后，那么我们就增加一次操作数，记住左指针从1到n，每一次满足左指针牛的要求，将差分数组中右指针指向的-1（这代表从区间[l,r]增加一次操作数量），然后每一次左右指针后移，最后到右指针指向n+1，停止，并检查后面的牛是否全部朝前。复杂度$\Theta (n^2)$
$Code:$

/* -*- encoding: utf-8 -*-
'''
@File    :   255.cpp
@Time    :   2021/05/31 21:05:02
@Author  :   puddle_jumper
@Version :   1.0
@Contact :   1194446133@qq.com
'''

# here put the import lib*/
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#define ch() getchar()
#define pc(x) putchar(x)
#include<stack>
#include<unordered_map>
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define ll long long
#define ull unsigned long long
#define pb emplace_back
#define mp make_pair
#define PI acos(-1)
using namespace std;
template<typename T>void read(T&x){
    static char c;
    static int f;
    for(c=ch(),f=1; c<'0'||c>'9'; c=ch())if(c=='-')f=-f;
    for(x=0; c>='0'&&c<='9'; c=ch())x=x*10+(c&15);
    x*=f;
}
template<typename T>void write(T x){
    static char q[65];
    int cnt=0;
    if(x<0)pc('-'),x=-x;
    q[++cnt]=x%10,x/=10;
    while(x)
        q[++cnt]=x%10,x/=10;
    while(cnt)pc(q[cnt--]+'0');
}


const int N = 5e3+10;
int n;
char op[N][2];
int base[N],x[N];
void solve(){
    read(n);
    rep(i,1,n){scanf("%s",op[i]);if(*op[i] == 'B')base[i] = 1;}
    int sum = 0,id = -1,ans = 99999999;
    rep(i,1,n){
        memset(x,0,sizeof x);
        int cnt = 0;sum = 0;
        rep(idx,1,n){
            int idy = idx + i ;
            sum += x[idx];
            if((sum + base[idx])%2){
                sum++;
                cnt++;
                if(idy<=n)x[idy]--;
            }
            if(idy == n+1)break;
           // printf("%d %d\n",sum,base[idx]);
        }
        bool flag = true;
        rep(j,n-i+2,n){
            sum += x[j];
            if((sum + base[j])%2){flag = false;break; }
        }
        if(!flag)continue;
        if(ans>cnt)ans = cnt,id = i;
    }
    if(id == -1){
        puts("-1");
    }
    else
    printf("%d %d\n",id,ans);
}


signed main(){solve();return 0; }

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章