【2017年浙江中医药大学大学生程序设计竞赛】F 开心的cc 【线段树+思维】

admin管理员组

文章数量:1612394

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
CC is a smart girl and she is curious about everything. One day she starts to analyze her lifestyle and finds out that she either feels happy or unhappy in any day, then she collects her mood data and makes numerical representation. She writes down 1 if she is happy, otherwise she writes down 0.
For example, if CC is happy, happy, unhappy, happy, happy, unhappy in the next 6 days, a numerical sequence which stands for it is 1,1,0,1,1,0

Meanwhile, smart CC finds her mood sequence is always periodic. She also finds the repeated segment like 1,1,0 in the aforementioned example and calls it “feeling repetend”. As a curious girl, CC wants to make another deep analysis. After she gets the length of “feeling repetend” n, she defines a rule: she tries to find a day whose index is d and considers the next d+n-1 days. For each day d’ in [d, d+n-1], CC guarantee that the number of happy days is more than unhappy days in [1, d’] days.

Now, CC wonder that how many days which satisfy the rule in n “feeling repetend” days.

输入描述:
Input contains multiple test cases.
The first line contains an integer T (1<=T<=20), which is the number of test cases.
Then the first line of each test case contains an integer n (1<=n<=100000), which is the length of “feeling repetend”.
The second line of each test case contains n integers, each integer is either 0 or 1, standing for unhappy or happy.
输出描述:
output a integer represents the answer.
示例1
输入

2
5
1 0 1 1 0
5
1 1 1 1 1
输出

1
5
说明

For the sample,the days from the third day as a starting point are as follows:
Day1: 1 day happy : 0 days unhappy
Day2: 2 days happy : 0 days unhappy
Day3: 2 days happy : 1 day unhappy
Day4: 3 days happy : 1 day unhappy
Day5: 3 days happy : 2 days unhappy

分析： 定义u[i]代表为从第一天到第i天有多少个开心，uh[i]代表从第一天到第i天有多少个不开心。
我们假设一个起始天st。
则：
( h[i] - h[st-1] ) - ( uh[i] - uh[st-1] ) > 0
对所有的i (属于 [ st , st+n-1 ] ) 都是同时满足的，当时脑残居然想把这些都加起来然后就算满足了，现在想想肯定是不对的啊。
那怎么样才可以保证所有的同时满足呢？
转化一下格式 : ( h[i] - uh[i] ) > ( h[st-1] - uh[st-1] ) .
针对所有的 i ( 属于 [ st , st+n-1 ] )同时满足，右边是一个固定值，左边是一个区间，我们可以找到区间中的 min( h[i] - uh[i] ) ,如果它大于( h[st] , uh[st] ) 那不就是说明所有的都符合。对于区间的求最小值，我们可以用线段树维护。
ps 代码中令 sum[i] = h[i] - uh[i] .
代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e5*3;

struct Tree{
    int le,ri,val;
}tree[MAXN<<2];
int sum[MAXN];
void Up(int o){
    tree[o].val=min(tree[o<<1].val,tree[o<<1|1].val);
}
void Build(int o,int le,int ri){
    tree[o]={le,ri,0};
    if(le==ri){
        tree[o].val+=sum[le];
        return ;
    }
    int mid=(le+ri)>>1;
    Build(o<<1,le,mid);
    Build(o<<1|1,mid+1,ri);
    Up(o);
}
int Query(int o,int le,int ri){
    if(tree[o].le>=le&&ri<=tree[o].ri) return tree[o].val;
    int mid=(tree[o].le+tree[o].ri)>>1;
    if(le>mid) return Query(o<<1|1,le,ri);
    else if(ri<=mid) return Query(o<<1,le,ri);
    else return min(Query(o<<1,le,mid),Query(o<<1|1,mid+1,ri));
}
int arr[MAXN];
int main(){
    int  T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)  {
            scanf("%d",&arr[i]);
            if(!arr[i]) arr[i]=-1;
            arr[i+n]=arr[i];
        }
        for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+arr[i];
       // for(int i=1;i<=2*n;i++) printf("%d ",sum[i]);puts("");
        Build(1,1,2*n);
        int ans=0;
        for(int i=1;i<=n;i++){
          // printf("%d %d\n",sum[i],Query(1,i+1,i+n-1));
            if(Query(1,i,i+n-1)>sum[i-1]) ans++;
        }
        printf("%d\n",ans);
    }

return 0;
}

本文标签： 线段浙江程序设计中医药大学思维