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

Codeforces-Round 174(Cows and Sequence)

2024-07-16 10:38:02   222人阅读

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

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;
}


联系
我们