首页 > 代码库 > 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 }
View Code

 

•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 }
View Code

 

•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 }
View Code

 

•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 }
View Code