首页 > 代码库 > Topcoder 144-150（未完待续）
Topcoder 144-150（未完待续）
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
SRM 145 (略）
SRM 146
Div1 600 Masterbrain
题意：略
题解：主要是卡题意，以及“No digit in either a guess or a secret combination may be involved in giving more than one peg”这个条件的处理
#line 2 "Masterbrain.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;int ans;int A[5];int cnt[15];int ok[5];vector<vector<int> > G;vector<int> v;vector<int> B;vector<int> W;bool check(){ int wa=0; for (int i=0;i<G.size();++i) { memset(ok,0,sizeof(ok)); vector<int>& v=G[i]; int b=0; int w=0; for (int j=0;j<v.size();++j) { if (A[j]==v[j]) { ++b; ok[j]=1; } } for (int j=0;j<v.size();++j) { if (A[j]!=v[j] && cnt[v[j]]!=0) { for (int jj=0;jj<v.size();++jj) { if (A[jj]==v[j] && ok[jj]==0) { ok[jj]=1; ++w; break; } } } } if (b!=B[i] || w!=W[i]) ++wa; } if (wa!=1) return false; else return true;}void dfs(int k){ if (k==4) { if (check()) ++ans; return; } for (int i=1;i<=7;++i) { A[k]=i; ++cnt[i]; dfs(k+1); --cnt[i]; } return ;}class Masterbrain{ public: int possibleSecrets(vector <string> guesses, vector <string> results) { for (int i=0;i<guesses.size();++i) { string& tmp=guesses[i]; v.clear(); for (int j=0;j<tmp.length();++j) { int t=tmp[j]-‘0‘; v.push_back(t); } G.push_back(v); } for (int i=0;i<results.size();++i) { string& tmp=results[i]; B.push_back(tmp[0]-‘0‘); W.push_back(tmp[3]-‘0‘); } ans=0; memset(cnt,0,sizeof(cnt)); dfs(0); return ans; }};#ifdef exint main(){ #ifdef ex1 freopen ("in.txt","r",stdin); #endif}#endif
Div2 1000 BridgeCrossing
题意：略
题解：状压DP
#line 2 "BridgeCrossing.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1<<8;int dp[maxn+5];int sz;vector<int> T;int DP(int x){ if (dp[x]!=-1) return dp[x]; vector<int> v1,v2; for (int i=0;i<=sz-1;++i) { if (x>>i & 1) v1.push_back(i); else v2.push_back(i); } if (v1.size()==0) return dp[x]=0; else if (v1.size()==1) return dp[x]=T[v1[0]]; else if (v1.size()==2) return dp[x]=max(T[v1[0]],T[v1[1]]); int q=0; int val=1e8; for (int i=0;i<v2.size();++i) { int& e=v2[i]; if (T[e]<val) { val=T[e]; q=e; } } dp[x]=1e8; for (int i=0;i<v1.size();++i) { for (int j=i+1;j<v1.size();++j) { int& e1=v1[i]; int& e2=v1[j]; int S=x&~(1<<e1); S=S&~(1<<e2); int t=T[e1]<T[e2]?e1:e2; int p=val<T[t]?q:t; S=S|(1<<p); dp[x]=min(dp[x],DP(S)+max(T[e1],T[e2])+T[p]); //printf("%d %d %d\n",x,S,q); //printf("%d %d %d %d\n",x,v1.size(),i,j); } } return dp[x];}class BridgeCrossing{ public: int minTime(vector <int> times) { sz=times.size(); for (int i=0;i<=sz-1;++i) T.push_back(times[i]); memset(dp,-1,sizeof(dp)); int ans=DP((1<<sz)-1); /* for (int i=0;i<=((1<<sz)-1);++i) { printf("%d %d\n",i,DP(i)); } */ return ans; }};#ifdef exint main(){ #ifdef ex1 freopen ("in.txt","r",stdin); #endif}#endif
SRM 147
Div2 950 GoldenChain
题意：略
题解：二分答案再判断，判断时选择贪心地剪长度短的sections。
#line 2 "GoldenChain.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;LL sum[60];int n;bool check(int num){ int p=upper_bound(sum+1,sum+1+n,num)-sum-1; if (n-p<=num) return true; else return false;}class GoldenChain{ public: int minCuts(vector <int> sections) { n=sections.size(); sort(sections.begin(),sections.end()); sum[0]=0; for (int i=1;i<=n;++i) { sum[i]=sum[i-1]+sections[i-1]; } LL lb=0; LL ub=INT_MAX; while (ub-lb>1) { int mid=(lb+ub)>>1; if (check(mid)) ub=mid; else lb=mid; } return ub; }};#ifdef exint main(){ #ifdef ex1 freopen ("in.txt","r",stdin); #endif}#endif
SRM148
Div1 250 CircleGame
题意：略
题解：循环链表模拟，要求删除操作，注意头指针的维护
#line 2 "CircleGame.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;struct Node{ int pre,next; int val;};Node p[60];int n;int head;void Remove(int x){ p[p[x].pre].next=p[x].next; p[p[x].next].pre=p[x].pre;}void Remove(int x,int y){ p[p[x].pre].next=p[y].next; p[p[y].next].pre=p[x].pre;}class CircleGame{ public: int cardsLeft(string deck) { n=deck.length(); int v; for (int i=0;i<=n-1;++i) { if (isdigit(deck[i])) v=deck[i]-‘0‘; else if (deck[i]==‘A‘) v=1; else if (deck[i]==‘T‘) v=10; else if (deck[i]==‘J‘) v=11; else if (deck[i]==‘Q‘) v=12; else if (deck[i]==‘K‘) v=13; p[i].val=v; p[i].next=(i+1)%n; p[i].pre=(i-1+n)%n; } head=0; bool update=true; while (update && n>0) { update=false; int pointer=head; do { if (p[pointer].val==13) { if (pointer==head) head=p[head].next; --n; Remove(pointer); update=true; break; } int f=p[pointer].pre; if (p[pointer].val+p[f].val==13) { if (pointer==head || f==head) head=p[pointer].next; n=n-2; Remove(f,pointer); update=true; break; } pointer=p[pointer].next; }while (pointer!=head); } return n; }};#ifdef exint main(){ #ifdef ex1 freopen ("in.txt","r",stdin); #endif}#endif
Div1 450 MNS
题意：略
题解：next_permutation
#line 2 "MNS.cpp"#include<bits/stdc++.h>using namespace std;typedef long long LL;int sum[10];class MNS{ public: int combos(vector <int> numbers) { vector <int>& A=numbers; sort(A.begin(),A.end()); int ans=0; do { bool f=true; sum[1]=A[0]+A[1]+A[2]; sum[2]=A[3]+A[4]+A[5]; sum[3]=A[6]+A[7]+A[8]; sum[4]=A[0]+A[3]+A[6]; sum[5]=A[1]+A[4]+A[7]; sum[6]=A[2]+A[5]+A[8]; for (int i=2;i<=6;++i) { if (sum[i]!=sum[i-1]) f=false; } if (f) ++ans; }while (next_permutation(A.begin(),A.end())); return ans; }};#ifdef exint main(){ #ifdef ex1 freopen ("in.txt","r",stdin); #endif}#endif
Topcoder 144-150（未完待续）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。