本文主要是介绍Codeforces Good Bye 2014 解题报告 (A B C D)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A. New Year Transportation
水题，直接模拟就行。我居然连跪两发。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;int a[30010];int main(){int n,t;cin>>n>>t;for(int i=1;i<n;i++){scanf("%d",&a[i]);}int s=1;bool ok=0;int cnt=0;while(1){if(s==t)ok=1;if(s>=t)break;s+=a[s];cnt++;if(cnt>=n)break;}if(ok){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}return 0;
}B. New Year Permutation
我的写法是求每个连通分量，然后对每个连通分量内排序，填回去就行了。不过感觉应该有更好的做法。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;const int maxn=310;int a[maxn];
int mat[maxn][maxn];bool vis[maxn];
int ans[maxn];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){char c;scanf("%c",&c);for(int j=1;j<=n;j++){scanf("%c",&mat[i][j]);mat[i][j]-='0';}}for(int i=1;i<=n;i++){if(vis[i])continue;queue<int> que; que.push(i);vector<int> vec;vector<int> tmp;while(!que.empty()){int cur=que.front(); que.pop();if(vis[cur])continue;vis[cur]=1;vec.push_back(cur); //下标 tmp.push_back(a[cur]); //答案 for(int j=1;j<=n;j++){if(mat[cur][j]&&!vis[j]){que.push(j);}}}sort(tmp.begin(),tmp.end());sort(vec.begin(),vec.end());int sz=vec.size();for(int j=0;j<sz;j++){ans[vec[j]]=tmp[j];}}for(int i=1;i<=n;i++){cout<<ans[i]<<" ";}return 0;
}
C. New Year Book Reading
贪心。其实我们无须关心书的顺序。对每本要读的书，往前扫到头或者扫到同一本书，看看中间夹着多少本书，把这些书的重量加上就行了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;int a[510];
int b[1010];bool use[510];int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}int ans=0;for(int i=2;i<=m;i++){memset(use,0,sizeof(use));for(int j=i-1;j>=1;j--){if(b[j]==b[i]){break;}use[b[j]]=1;}for(int j=1;j<=n;j++){if(use[j]){ans+=a[j];}}}cout<<ans<<endl;return 0;
}D. New Year Santa Network
dfs一次，对每一条边，求出边的两头有多少个点。然后用组合数学的方法算出随机取三个点时，这条边经过的期望（具体见代码）。最后把每条边期望乘以权，并维护权输出就可以了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;const int maxn=100010;int head[maxn];
int next[maxn*2];
int cnt[maxn];
int pos;
double p[maxn];struct Edge{int v,w;int id;Edge(int v,int w,int id):v(v),w(w),id(id){}Edge(){}
}edges[maxn*2];inline void addedge(int& u,int& v,int& w,int& id){edges[pos]=Edge(v,w,id); next[pos]=head[u]; head[u]=pos; pos++; edges[pos]=Edge(u,w,id); next[pos]=head[v]; head[v]=pos; pos++;
}int dfs(int x,int p){int re=0;for(int i=head[x];i!=-1;i=next[i]){int v=edges[i].v;if(v==p)continue;int tmp=dfs(v,x);re+=(tmp+1);cnt[edges[i].id]=tmp+1;}return re;
}int main(){int n;cin>>n;int u,v,w;pos=0;memset(head,-1,sizeof(head));for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&w);addedge(u,v,w,i);}dfs(1,0);for(int i=1;i<n;i++){int x=cnt[i];int y=n-cnt[i];if(x>y)swap(x,y);if(x==1){p[i]=(1.0-(n-3.0)/n)*2;}if(x==2){if(y==2)p[i]=2.0;else p[i]=(1.0-(y+0.0)/n*(y-1.0)/(n-1)*(y-2.0)/(n-2))*2;}if(x>=3){p[i]=(1.0-(x+0.0)/n*(x-1.0)/(n-1)*(x-2.0)/(n-2)-(y+0.0)/n*(y-1.0)/(n-1)*(y-2.0)/(n-2))*2;}}double ans=0.0;for(int i=1;i<n;i++){ans+=edges[(i-1)*2].w*p[i];}int q;cin>>q;int a,b;for(int i=1;i<=q;i++){scanf("%d%d",&a,&b);int d=edges[(a-1)*2].w-b;edges[(a-1)*2].w=b;ans-=d*p[a];printf("%.8lf\n",ans);}return 0;
}
这篇关于Codeforces Good Bye 2014 解题报告 (A B C D)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
