首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。