首页 > 代码库 > CSU-ACM2014年校队选拔赛指导赛解题报告
CSU-ACM2014年校队选拔赛指导赛解题报告
•Problem A CSU 1065 贪心
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 1000010; 6 struct Node{ 7 int a,b; 8 bool operator < (const Node& rhs) const{ 9 return b < rhs.b;10 }11 }node[maxn];12 13 int main(){14 int n,r = -1,ans = 0;15 scanf("%d",&n);16 for(int i = 0;i < n;i++){17 scanf("%d%d",&node[i].a,&node[i].b);18 }19 sort(node,node+n);20 for(int i = 0;i < n;i++){21 if(node[i].a > r){22 ans++;23 r = node[i].b;24 }25 }26 printf("%d\n",ans);27 return 0;28 }
•Problem B CSU 1060 DP
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 110; 6 char s1[maxn],s2[maxn],s3[maxn]; 7 int dp[maxn][maxn][maxn]; 8 9 int main(){10 while(scanf("%s",s1+1) != EOF){11 scanf("%s",s2+1);12 scanf("%s",s3+1);13 int len1 = strlen(s1+1);14 int len2 = strlen(s2+1);15 int len3 = strlen(s3+1);16 memset(dp,0,sizeof(dp));17 18 for(int i = 1;i <= len1;i++){19 for(int j = 1;j <= len2;j++){20 for(int k = 1;k <= len3;k++){21 if(s1[i] == s2[j] && s2[j] == s3[k]){22 dp[i][j][k] = dp[i-1][j-1][k-1]+1;23 }else{24 int tmp1 = dp[i-1][j][k];25 int tmp2 = dp[i][j-1][k];26 int tmp3 = dp[i][j][k-1];27 tmp1 = max(tmp1,tmp2);28 tmp1 = max(tmp1,tmp3);29 dp[i][j][k] = tmp1;30 }31 }32 }33 }34 35 printf("%d\n",dp[len1][len2][len3]);36 }37 return 0;38 }
•Problem C CSU 1307 最短路
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 using namespace std; 6 typedef pair<int,int> pii; 7 const int maxn = 2010; 8 const int maxm = 100010; 9 int v[maxm],next[maxm],w[maxm];10 int d[maxm],first[maxn],e;11 void init(){12 e = 0;13 memset(first,-1,sizeof(first));14 }15 16 void add_edge(int a,int b,int c){17 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++;18 }19 20 int dijkstra(int src,int dist,int mid){21 priority_queue <pii,vector<pii>,greater<pii> > q;22 memset(d,-1,sizeof(d));23 d[src] = 0;24 q.push(make_pair(0,src));25 while(!q.empty()){26 while(!q.empty() && q.top().first > d[q.top().second]) q.pop();27 if(q.empty()) break;28 int u = q.top().second;29 q.pop();30 for(int i = first[u];i != -1;i = next[i])if(w[i] <= mid){31 if(d[v[i]] > d[u] + w[i] || d[v[i]] == -1){32 d[v[i]] = d[u]+w[i];33 q.push(make_pair(d[v[i]],v[i]));34 }35 }36 }37 return d[dist];38 }39 40 int main(){41 int n,m,src,dist;42 while(scanf("%d%d%d%d",&n,&m,&src,&dist) != EOF){43 init();44 int l = 1<<30,r = -1,ans = 1<<30;45 for(int i = 0;i < m;i++){46 int a,b,c;47 scanf("%d%d%d",&a,&b,&c);48 add_edge(a,b,c);49 add_edge(b,a,c);50 l = min(l,c);51 r = max(r,c);52 }53 while(l <= r){54 int mid = (l+r)>>1;55 int tmp = dijkstra(src,dist,mid);56 if(tmp == -1) l = mid+1;57 else r = mid-1,ans = tmp;58 }59 60 printf("%d\n",ans);61 }62 return 0;63 }
•Problem D CSU 1290 DP
1 #include <cstdio> 2 double dp[1005]; 3 int main() 4 { 5 int n,t; 6 double k; 7 scanf("%d", &t); 8 while (t--) { 9 scanf("%lf %d", &k, &n);10 dp[1] = 1.0;11 for (int i = 2; i <= n; ++i)12 dp[i] = dp[i-1] + (k - dp[i-1])/k;13 printf("%.5f\n", dp[n]);14 }15 return 0;16 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。