Codeforces Rockethon 2014 解题报告-白红宇

Codeforces Rockethon 2014 解题报告

阅读量：6329 次

发布时间：2019-06-22

本文共 5153 字，大约阅读时间需要 17 分钟。

这次题目好难读各种专业词汇。。。把做出来的题贴一下把。

Problem A

思路：遍历一遍然后求出长度为奇数个的一样字母长度，即为答案。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-02-17 01:53 5  * Filename     : Rockethon_2014_A_1.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 110;34 char str[LEN];35 36 int main()37 {38 // freopen("in.txt", "r", stdin);39 40 while(cin >> str){41 int len = strlen(str), ans = 0, lc = 0;42 char c = str[0];43 for(int i=0; i

View Code

Problem B

题意：题目中告诉你了折叠的方法，然后问你折出来一列上都为同一个字母最高的高度为多少。注意当中不能有空档

思路：我们可以发现只要两个相同的字母相隔为奇数就能折上去，即得到比原来长度+1的一列，这样问题就转化为lis。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-02-17 01:53 5  * Filename     : Rockethon_2014_B_1.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1010;34 char str[LEN];35 int dp[LEN];36 37 int main()38 {39 //freopen("in.txt", "r", stdin);40 41 while(cin >> str){42 int len = strlen(str);43 for(int i=0; i

View Code

Problem C （C1，C2）

题意：一个人打竞标赛，一共有n个对手期望排名在k前面。每个对手初始有一个值p，和打赢他的预计花费e。这个人必须和每个对手打仅一场，有两种情况：1.花费e打赢他自己p+1 2.花费0输掉，对手p+1。问你达到期望的最小花费。

思路：我们可以发现在枚举打赢的人的个数时，即可使用贪心算法。当对手p<i-1（i为枚举值从0-n）时对手排名必定在后面，p>i时对手排名必定在前面。所以对于p=i和i-1的按照花费排序，挑最小的打。大概思路就是这样，细节看代码（复杂度n^2）

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-02-17 01:54 5  * Filename     : Rockethon_2014_C_2.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 102;34 int n, k;35 struct O{36 int p, e;37 };38 O op[LEN];39 int top[LEN], flag[LEN];40 41 bool cmp1(O a, O b){ return a.e < b.e;}42 43 int main()44 {45 // freopen("in.txt", "r", stdin);46 47 while(scanf("%d%d", &n, &k)!=EOF){48 for(int i=0; i

View Code

Problem D （D1）

题意：若干横向量和竖向量，两个向量横竖当相交时找出向量交点到四个顶点中的最小值再找出这个最小值在所有向量对中的最大值。

思路：小数据直接暴力枚举。比较水

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-02-17 01:55 5  * Filename     : Rockethon_2014_D_1.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 1010;34 struct P{35 int x, y, v;36 };37 P row[LEN], col[LEN];38 int n, m;39 40 int main()41 {42 //freopen("in.txt", "r", stdin);43 44 while(scanf("%d%d", &n, &m)!=EOF){45 for(int i=0; i
                      
                        row[j].x+row[j].v || zh.y < col[i].y || zh.y > col[i].y+col[i].v) continue;54 int a = min(abs(zh.y-col[i].y), abs(zh.y-(col[i].y+col[i].v)));55 int b = min(abs(zh.x-row[j].x), abs(zh.x-(row[j].x+row[j].v)));56 int temp = min(a, b);57 ans = max(temp, ans);58 }59 }60 printf("%d\n", ans);61 }62 return 0;63 }

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3552070.html

你可能感兴趣的文章