首页 > 代码库 > Topcoder SRM 144
Topcoder SRM 144
Div2 1100 PowerOutage
题意：给定一个有根树，求遍历完整棵树的最小路程
题解：DFS一下，求出叶子节点中到根节点的最远距离，然后把树的所有边相加，乘以二，减去最远距离就是答案
#line 2 "PowerOutage.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=50;struct Edge{ int to; int w;};int ans=0;vector <Edge> G[maxn+5];int d[maxn+5];void dfs(int r){ ans=max(ans,d[r]); for (int i=0;i<G[r].size();++i) { Edge &e=G[r][i]; d[e.to]=d[r]+e.w; dfs(e.to); }}class PowerOutage{ public: int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) { int sz=fromJunction.size(); int sum=0; for (int i=0;i<=sz-1;++i) { int u=fromJunction[i]; int v=toJunction[i]; int w=ductLength[i]; sum+=w; G[u].push_back((Edge){v,w}); } dfs(0); return 2*sum-ans; }};#ifdef exint main(){ #ifdef ex1 freopen ("in.txt","r",stdin); #endif}#endif
Div1 550 Lottery
题意：
买彩票，给定一些彩票的描述：choice,blanks,sorted,unique，choice代表彩票的每个数码的最大值，blank代表彩票号码由几个数码组成，sorted代表彩票的数码是否是呈升序的，unique代表彩票的数码是否两两不唯一。
根据这些描述，可以求出合法的彩票号码的数量，也就可以求出中奖概率，将彩票按照中奖概率排序。
题解：
组合数学
未排序，不唯一：choice！ 每个数码都有choice种选择
排序，唯一：C（choice,blanks) 从choice个数中选blanks个
不排序，唯一：C(choice,blanks)*(blanks!) 在上一个的基础上，还可以对这选出的blanks个做全排序
排序，不唯一：C(choice+blanks-1,blanks) 按照官方题解，考虑choice+blanks-1个球，对其中choice-1个染色，对于不染色的球，它的权值等于左边染色球的个数+1，对于这些权值，就构造出了一系列长度为blanks，单调不减的序列。
#line 2 "Lottery.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;struct Node{ string s; LL p; bool operator < (const Node& A) const { if (p!=A.p) return p<A.p; else return s<A.s; }};vector <string> ans;Node L[60];LL C[125];LL fac[15];LL f(LL n,LL m){ if (m>n) return 0; C[0]=1; for (int i=1;i<=m;++i) { C[i]=C[i-1]*(n-i+1)/i; } return C[m];}class Lottery{ public: vector <string> sortByOdds(vector <string> rules) { int sz=rules.size(); if (sz==0) { return ans; } fac[1]=1; for (int i=2;i<=9;++i) fac[i]=fac[i-1]*i; for (int i=0;i<=sz-1;++i) { stringstream ss(rules[i]); LL choice,blanks; char S,U; getline(ss,L[i].s,‘:‘); ss>>choice>>blanks>>S>>U; if (S==‘F‘ && U==‘F‘) { L[i].p=1; for (int j=1;j<=blanks;++j) L[i].p*=choice; } else if (S==‘F‘ && U==‘T‘) { L[i].p=f(choice,blanks)*fac[blanks]; } else if (S==‘T‘ && U==‘F‘) { L[i].p=f(choice+blanks-1,blanks); } else if (S==‘T‘ && U==‘T‘) { L[i].p=f(choice,blanks); } //cout<<choice<<‘ ‘<<blanks<<endl; } sort(L,L+sz); for (int i=0;i<=sz-1;++i) { ans.push_back(L[i].s); //cout<<L[i].p<<endl; } return ans; }};#ifdef exint main(){ #ifdef ex1 freopen ("in.txt","r",stdin); #endif}#endif
Topcoder SRM 144
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。