menu ZigZagK的博客

正在努力加载中QAQ

[思维]liu_runda NOIP模拟题【斯诺】题解
apps HHHOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 17 次访问

解题报告

补集转化,则统计有数超过区间一半的区间的个数,由于是超过区间一半所以只会是 $012$ 中的一个。

分开统计 $012$ ,考虑前缀和,其实就是个逆序对问题,由于 $n=5\times10^6$ 树状数组会TLE,所以考虑优化,会发现每次 $sum$ 变化是 $\pm1$ 的,所以直接瞎搞。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=5000000,maxs=maxn<<1;

int n,a[maxn+5],cnt[maxs+5];LL ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
inline char getdig() {char ch=readc();while (!isdigit(ch)) ch=readc();return ch;}
inline LL Count(int c){
    for (int i=0;i<=(n<<1);i++) cnt[i]=0;int now=n;LL ans=0;
    for (int i=1,lst=0;i<=n;i++)
        if (cnt[now]++,a[i]==c) lst+=cnt[now++],ans+=lst;
        else lst-=cnt[--now],ans+=lst;return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) a[i]=getdig()-48;ans=(LL)n*(n+1)/2;
    for (int i=0;i<3;i++) ans-=Count(i);printf("%lld\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up