P6334 [COCI2007-2008#1] SREDNJI 题解

· · 题解

题目大意：

扔给你一个串，再扔给你一个数字，让你从这个串的头或者尾噶掉一些数字，要求噶完后的串中的中位数，是他刚刚扔给你的那个数字。

主要思路：

1.暴力（会TLE）：

首先，把扔给你的串简化，只剩下 3 种类型：比扔给你的数字大的，跟扔给你的数字一样的，比扔给你的数字小的。这样，串的数字就只剩下了 3 种，分别是：1，0，-1。然后，问题就变成了：求串中长度为奇数，且和为 0 的字串，对每个数暴力一遍，就可以得出答案。

暴力代码：（90pts）

#pragma gcc optimize(2)//手动开O2
#include <iostream>
#include <algorithm>
#include <string>
#define maxn 100010
#define inf 2147483647
using namespace std;
int a[maxn],n,b,ans;
bool flag;
inline int read(){//快读
    int x=0,f; char ch=0;
    while(!isdigit(ch)) f=(ch=='-'?-1:1),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
inline void print(int x){//快写
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
}
inline void write(int x){print(x);putchar('\n');}
int main(){
    n=read(),b=read();
    for(int i=1,x;i<=n;i++){
        x=read();
        a[i]=x>b?1:(x<b?-1:0);//简化串
    }
    for(int i=1,sum;i<=n;i++){
        sum=a[i];
        if(a[i]!=0)flag=0;
        else ans++;
        for(int j=i+2;j<=n;j+=2){//对每个点进行暴力
            sum+=a[j]+a[j-1];
            if(a[j]==0||a[j-1]==0)flag=1;//判断字串中是否含有扔给你的那个数
            if(flag&&sum==0)ans++;
        }
        if(a[i]==0)break;
    }
    write(ans);
    return 0;//杀青
}

然而，我们发现，暴力的时间复杂度为 O(n^2)，题目数据为 1\times10^5，时间显然不足以通过本题，所以尝试优化。

2.单线奇偶性处理（AC）：

暴力枚举每个点会超时，那就尝试一次性解决问题。在单一线上，我们会发现存在奇数段和偶数段，那就从奇偶性出发，尝试进行单线处理。我们发现，当路径长度为奇数，叠加奇数路径数，并为偶数路径加一；反之，当路径长度为偶数，叠加偶数路径数，并为奇数路径加一。这样，时间复杂度为 O(n)，可以通过本题。

AC Code：

#pragma gcc optimize(2)
#include <iostream>
#include <algorithm>
#include <string>
#define maxn 100010
#define inf 2147483647
using namespace std;
int x[maxn],y[maxn],n,b,ans,sum;
bool flag;
inline int read(){//快读
    int x=0,f; char ch=0;
    while(!isdigit(ch)) f=(ch=='-'?-1:1),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
inline void print(int x){//快写
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+48);
}
inline void write(int x){print(x);putchar('\n');}
signed main(){
    n=read(),b=read();
    for(int i=1,u;i<=n;i++){//单线处理
        u=read();
        sum+=u>b?1:(u<b?-1:0);
        if(i%2==0)ans+=x[n+sum],y[n+sum]++;//偶数路径
        else ans+=y[n+sum],x[n+sum]++;//奇数路径
    }
    write(ans);
    return 0;//完结撒花~
}