设为首页 加入收藏

TOP

Codeforces Round #303 (Div. 2)(一)
2015-11-21 01:01:26 来源: 作者: 【大 中 小】 浏览:3次
Tags：Codeforces Round #303 Div.

A.简单题

/*************************************************************************
    > File Name: A.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年05月20日 星期三 09时51分15秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; int mat[110][110]; bool ok[110]; int main() { int n; while (cin >> n) { for (int i = 1; i <= n; ++i) { ok[i] = 1; for (int j = 1; j <= n; ++j) { cin >> mat[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (mat[i][j] == -1 || mat[i][j] == 0) { continue; } if (mat[i][j] == 1) { ok[i] = 0; } else if (mat[i][j] == 2) { ok[j] = 0; } else { ok[i] = ok[j] = 0; } } } vector 
                  
                    ans; ans.clear(); for (int i = 1; i <= n; ++i) { if (ok[i]) { ans.push_back(i); } } int size = ans.size(); printf("%d\n", size); if (size == 0) { continue; } printf("%d", ans[0]); for (int i = 1; i < size; ++i) { printf(" %d", ans[i]); } printf("\n"); } return 0; }

B.简单题

/*************************************************************************
    > File Name: B.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年05月20日 星期三 09时57分00秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; string s, t; int main() { while (cin >> s >> t) { int len = s.length(); int cnt = 0; for (int i = 0; i < len; ++i) { if (s[i] != t[i]) { ++cnt; } } if (cnt & 1) { printf("impossible\n"); } else { bool flag = 0; for (int i = 0; i < len; ++i) { if (s[i] == t[i]) { printf("%c", s[i]); } else { if (!flag) { printf("%c", s[i]); } else { printf("%c", t[i]); } flag ^= 1; } } printf("\n"); } } return 0; }

C.简单dp, dp[i][0/1/2] 表示不砍第i棵树;砍,往左边倒;砍,往右倒

/*************************************************************************
    > File Name: C.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年05月20日 星期三 10时03分06秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; PLL sta[100100]; int dp[100100][3]; int main() { int n; while (~scanf("%d", &n)) { memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; ++i) { scanf("%d%d", &sta[i].first, &sta[i].second); } dp[1][1] = 1; if (sta[1].first + sta[1].second < sta[2].first) { dp[1][2] = 1; } for (int i = 2; i <= n; ++i) { dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]); dp[i][0] = max(dp[i - 1][0], dp[i][0]); if (sta[i].first - sta[i].second > sta[i - 1].first) { dp[i][1] = max(dp[i][1], max(dp[i - 1][1], dp[i - 1][0]) + 1); } if (sta[i].first - sta[i].second > sta[i - 1].first + sta[i - 1].second) { dp[i][1] = max(dp[i][1], dp[i - 1][2] + 1); } if (i < n && sta[i].first + sta[i].second < sta[i + 1].first || i == n) { dp[i][2] = max(dp[i][2], max(dp[i - 1][1], dp[i - 1][0]) + 1); if (sta[i - 1].first + sta[i - 1].second < sta[i].first) { dp[i][2] = max(dp[i][2], dp[i - 1][2] + 1); } } } printf("%d\n", max(dp[n][0], max(dp[n][1], dp[n][2]))); } return 0; }

D.排序贪心就行

/*************************************************************************
    > File Name: D.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年05月20日 星期三 10时16分38秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; int arr[100010]; int main() { int n; while (~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) { scanf("%d", &arr[i]); } sort(arr + 1, arr + n + 1); int sum = 0; int ans = 0; for (int i = 1; i <= n; ++i) { if (sum <= arr[i]) { ++ans; sum += arr[i]; } } printf("%d\n", ans); } return 0; }

E.dijkstra算法的实现过程就是最小路径树的寻找过程
每次加入一个点放到当前求出最短路的集合里
考虑给每个点求一个最短的可以达到它的边,最短路相同时去边权小的边, 求的时候注意用long long ,一个地方没改wa了好多次也是哔了狗了

/*************************************************************************
    > File Name: E.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年05月20日 星期三 10时54分
首页 上一页 1 2 下一页 尾页 1/2/2
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：C++读取和存储一幅BMP图像 下一篇：hdu 1558 Segment set

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: