首页 > 代码库 > Codeforces-Round 174(Cows and Sequence)

Codeforces-Round 174(Cows and Sequence)

这道题是树状数组的题,但是用普通数组也能整出来,没学树状数组,就用的普通数组,算是高效算法吧,下面是我的修改思路:

1.一上来我写了如下代码:把每个新加进去的数压入vector,但是我在当t=1时,我的想法是将v[i]一个一个加上去,这样肯定会超时,而且我这个方法的sum是最后一起求的,这样多了个循环,又耗费时间。

#include<stdio.h>
#include<time.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(0);
    int n;cin>>n;
    while(n--)
    {
        int t;cin>>t;
        if(t == 1)
        {
            int a,x;cin>>a>>x;
            for(int i = 0;i < a;i++)
                v[i] += x;
        }
        if(t == 2)
        {
            int k;cin>>k;
            v.push_back(k);
        }
        if(t == 3)
            v.pop_back();
        int sum = 0;
        for(int i = 0;i < v.size();i++)
            sum += v[i];
        printf("%.6lf\n",(double)sum*1.0/v.size());
    }
    return 0;
}
2.想了一下,做出以下修改:虽然我意识到了sum用成全局的,随输随加,但其余的真是纯属脑残,因为我没考虑到连续把最后一个数删除的情况,看来输进去的数还是要用vector保存

#include<stdio.h>
#include<time.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n,last = 0,shu = 1,a,k,x,sum = 0;cin>>n;
    while(n--)
    {
        int t;cin>>t;
        if(t == 1) {cin>>a>>x;sum += a*x;}
        if(t == 2) {cin>>k;sum += k;last = k;shu++;}
        if(t == 3) {sum -= k;shu--;}
        printf("%.6lf\n",sum*1.0/shu);
    }
    return 0;
}


3.又修改:这样去除了sum的循环,但是当t=1时循环还在,还TLE

#include<stdio.h>
#include<time.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(0);
    int n,last = 0,shu = 1,a,k,x,sum = 0;cin>>n;
    while(n--)
    {
        int t;cin>>t;
        if(t == 1)
            {
                cin>>a>>x;sum += a*x;
                for(int i = 0;i < a;i++)
                    v[i] += x;
            }
        if(t == 2)
            {cin>>k;sum += k;v.push_back(k);}
        if(t == 3)
            {sum -= v[v.size() - 1];v.pop_back();}
        printf("%.6lf\n",(double)sum*1.0/v.size());
    }
    return 0;
}

4.无奈之下开始打表,把每个数的位置对应的加的数都打到表里,无奈有挂了,还是WA
#include<stdio.h>
#include<time.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(0);
    int n,last = 0,shu = 1,k,a,x,sum = 0,biao[200005];cin>>n;
    memset(biao,0,sizeof(biao));
    while(n--)
    {
        int t;cin>>t;
        if(t == 1)
        {
            cin>>a>>x;
            for(int i = 0;i < a;i++)
                biao[i] += x;
            sum += a*x;
        }
        if(t == 2)
            {cin>>k;sum += k;v.push_back(k);}
        if(t == 3)
            {
                sum -= v[v.size() - 1];
                sum -= biao[v.size() - 1];
                biao[v.size() - 1] = 0;
                v.pop_back();
            }
        printf("%.6lf\n",(double)sum*1.0/v.size());
    }
    return 0;
}
5.经过参考网上的题解,我发现这题竟然用long long!就修改成long long

#include<stdio.h>
#include<time.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(0);
    int n,last = 0,shu = 1,k,a,x,biao[200005];cin>>n;
    long long sum = 0;
    memset(biao,0,sizeof(biao));
    while(n--)
    {
        int t;cin>>t;
        if(t == 1)
        {
            cin>>a>>x;
            for(int i = 0;i < a;i++)
                biao[i] += x;
            sum += a*x;
        }
        if(t == 2)
            {cin>>k;sum += k;v.push_back(k);}
        if(t == 3)
            {
                sum -= v[v.size() - 1];
                sum -= biao[v.size() - 1];
                biao[v.size() - 1] = 0;
                v.pop_back();
            }
        printf("%.6lf\n",(double)sum*1.0/v.size());
    }
    return 0;
}

6.修改后又挂了,TLE,发现这里有点小技巧,t=1时根本不用将biao数组的所有前a个值都加x,将a加上x即可,然后从t=3里面调节,太巧妙了,终于AC

#include<stdio.h>
#include<time.h>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> v;
    v.push_back(0);
    int n,last = 0,shu = 1,k,a,x,biao[200005];cin>>n;
    long long sum = 0;
    while(n--)
    {
        int t;cin>>t;
        if(t == 1)
        {
            cin>>a>>x;
            biao[a - 1] += x;
            sum += a*x;
        }
        if(t == 2)
            {cin>>k;sum += k;v.push_back(k);}
        if(t == 3)
            {
                sum -= v[v.size() - 1];
                sum -= biao[v.size() - 1];
                biao[v.size() - 2] += biao[v.size() - 1];
                biao[v.size() - 1] = 0;
                v.pop_back();
            }
        printf("%.6lf\n",(double)sum*1.0/v.size());
    }
    return 0;
}