第十一周组队赛一130918

A题

===============================================================================

B题：给你一组数，数的值k符合:要么在它前面有k个数，要么在它后面有k个数，问给出的序列是否满足要求

分析：给出n=4  下标 ：  1       2      3      4
                             要么： 0      1      2      3

                                         3       2     1      0

所以每个位置i 要么取 i-1 要么取n-i-1  比如可以出现  0  1  2  3     3  2  1  0       0   2  1  0,s[i]为i的个数

可以发现s[0]+s[3]==2   s[1]+s[2]==2

代码：

#include <stdio.h>//B
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int M=110000;
int s[M];
int main()
{
    int t,n,x,g=1;
    scanf("%d",&t);
    while(t--)
    {
        memset(s,0,sizeof(s));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            s[x]++;
        }
        int ff=0;
        for(int i=0;i<=n/2;i++)
        {
            if(s[i]+s[n-i-1]!=2)
            {
                ff=1;break;
            }
        }
        printf("Case %d: ",g++);
        if(ff)printf("no\n");
        else
        printf("yes\n");
    }
    return 0;
}

================================================================================

G题：

水题呀，刚开始看了I题，没多少思路，就去看了G题，发现特别水，不过敲代码的速度。。。抢不到1血呀

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<queue>
using namespace std;
char a[305];
int main()
{
    int t,g=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",&a);
        int l=strlen(a);
        int s1=0,s2=0;
        int num=0;
        for(int i=0; i<l; i++)
        {
            if(a[i]=='S')
            {
                num=1;
                for(int j=i+1; j<l; j++)
                {
                    if(a[j]!='S')
                    {
                        s2++;
                        break;
                    }
                    else
                    {
                        num++;
                        i=j;
                    }
                }
                s1+=num-1;
                num=0;
            }
        }
        printf("Case %d: %d / %d\n",g++,s1,s2);
    }
    return 0;
}

I题：树状数组

题意：给出一个区间，求区间内不重复的数的平均值

思路：关键是去重问题，我们采用离线处理，对区间按右端点排序，一次询问，用到两次树状数组，一个记录区间值的和，一个记录区间不重复个数的和

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
long long a[11000];
long long c[11000];
long long c2[11000];
double ans[110000];

map<long long ,int >mp;
int n;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,long long v)
{
    for(int i=x; i<=n; i+=lowbit(i))
        c[i]+=v;
}
long long sum(int x)
{
    long long ans=0;
    for(int i=x; i>0; i-=lowbit(i))
        ans+=c[i];
    return ans;
}
void add2(int x,long long v)
{
    for(int i=x; i<=n; i+=lowbit(i))
        c2[i]+=v;
}
long long sum2(int x)
{
    long long ans=0;
    for(int i=x; i>0; i-=lowbit(i))
        ans+=c2[i];
    return ans;
}
struct node
{
    int id;
    int l;
    int r;
} inv[1100000];
bool cmp(node a,node b)
{
    return a.r<b.r;
}
int main()
{
    int T;
    scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        mp.clear();
        cas++;
        memset(c,0,sizeof(c));
        memset(ans,0,sizeof(ans));
        memset(c2,0,sizeof(c2));
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
        }
        int m;
        scanf("%d",&m);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&inv[i].l,&inv[i].r);
            inv[i].id=i;
        }
        sort(inv,inv+m,cmp);
        int j=0;
        for(int i=1; i<=n; i++)
        {
            add(i,a[i]);
            add2(i,1);
            if(mp[a[i]])
            {
                add(mp[a[i]],-a[i]);
                add2(mp[a[i]],-1);
            }
            mp[a[i]]=i;
            while(inv[j].r==i && j<m)
            {
                ans[inv[j].id]=1.0*(sum(inv[j].r)-sum(inv[j].l-1))/(sum2(inv[j].r)-sum2(inv[j].l-1));
                j++;
            }
        }
        printf("Case %d:\n",cas);
        for(int i=0; i<m; i++)
        {
            printf("%.6lf\n",ans[i]);
        }
    }
    return 0;
}