首页 > 代码库 > 多校比赛第九场

多校比赛第九场

  hdu 4950 Monster

         

题意好简单,队友说要用线段树做,要不然会TLE,连树状数组也会T。我说让我试试树状数组,结果搞了一个


时左右用树状数组给搞出来了,嘿嘿。用了树状数组区间更新。

       

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100010
using namespace std;
__int64 a[maxn],c[maxn],d[maxn],b[maxn];
__int64 n;
__int64 lowbit(__int64 x)
{
    return x&-x;
}
void update(__int64 i ,__int64 x)
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}
__int64 sum(__int64 i)
{
    __int64 s=0;
    while(i>0)
    {
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}
void update2(__int64 i,__int64 x)
{
    while(i<=n)
    {
        b[i]+=x;
        i+=lowbit(i);
    }
}
__int64 sum2(__int64 i)
{
    __int64 s=0;
    while(i>0)
    {
        s+=b[i];
        i-=lowbit(i);
    }
    return s;
}
int main()
{
    while(scanf("%I64d",&n)&&n)
    {
        memset(c,0,sizeof(c));
        memset(b,0,sizeof(b));
        __int64 m;
        scanf("%I64d",&m);
        while(m--)
        {
            __int64 u,v,w;
            scanf("%I64d%I64d%I64d",&u,&v,&w);
            update(u,w);
            update(v+1,-w);
        }
        for(__int64 i=1;i<=n;i++)
            update2(i,sum(n-i+1));
        __int64 x;
        __int64 num=0;
         scanf("%I64d",&x);
        while(x--)
        {
            __int64 u,v;
            scanf("%I64d%I64d",&u,&v);
            if(u>sum2(n-v+1)) num++;
        }
        printf("%I64d\n",num);
    }
    return 0;
}
hdu  4968

      绩点问题,已知科目数以及平均分,求出它的最大,最小绩点数; 

     最小绩点数  :让前n-1科的分数为69分,最后一科分数为总分减去前几科的分数,然后在最后一门课大于100分的

情况下减减,先给第一门课加,直到满100分,然后给第二门课加,一次类推;

   

    最大绩点数;让前n-1科的分数为85分,最后一科分数为总分减去前几课的分数,然后在最后一门课小于60分的情

下,给最后一门课加加,第一门课减减,直到减到60分,然后第二门减减,一次类推。

    不要问我怎么想的。

    

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int main()
{
    int t;
    int a[20];
    int score,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&score,&n);
        double maa=0, mii=0;
        if(n==1)
            {
                a[1]=score;
            if(a[1]<=69) maa+=2.0;
            else if(a[1]<=74) maa+=2.5;
            else if(a[1]<=79) maa+=3.0;
            else if(a[1]<=84) maa+=3.5;
            else maa+=4.0;
            mii=maa;
            }
        else
        {
        for(int i=1;i<n;i++) a[i]=85;
        a[n]=score*n-85*(n-1);
        bool flag=0;
        int ii=1;
        while(ii<n&&a[n]<60)
        {
                  while(a[ii]>60&&a[n]<60)
                        {
                            a[ii]--;
                            a[n]++;
                        }
                ii++;
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]<=69) maa+=2.0;
            else if(a[i]<=74) maa+=2.5;
            else if(a[i]<=79) maa+=3.0;
            else if(a[i]<=84) maa+=3.5;
            else maa+=4.0;
        }
        maa/=n;
        for(int i=1;i<n;i++) a[i]=69;
         a[n]=score*n-69*(n-1);
         flag=0;
         int ij=1;
        while(ij<n&&a[n]>70)
        {
             if(a[n]<=69) break;
                   while(a[ij]<100&&a[n]>100)
                        {
                            a[ij]++;
                            a[n]--;
                        }
                ij++;
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]<=69) mii+=2.0;
            else if(a[i]<=74) mii+=2.5;
            else if(a[i]<=79) mii+=3.0;
            else if(a[i]<=84) mii+=3.5;
            else mii+=4.0;
        }
        mii/=n;
        }
     printf("%.4lf %.4lf\n",mii,maa);
    }
    return 0;
}

多校比赛第九场