Codeforces Round #241 (Div. 2) 解题报告-白红宇

Codeforces Round #241 (Div. 2) 解题报告

阅读量：6087 次

发布时间：2019-06-20

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

Problem A

这道题比较容易错注意最小值一定小于-1e9，最大值大于1e9

代码如下:

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-04-13 15:56 5  * Filename     : Codeforce_241_2_E.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 34 int main()35 {36 freopen("in.txt", "r", stdin);37 38 int n, x, l, r;39 string op, c;40 while(cin >> n){41 l = -INF;42 r = INF;43 for(int i=0; i
                      
                       > op >> x >> c;45 if(c == "Y"){46 if(op == "<"){47 r = min(r, x-1);48 }else if(op == "<="){49 r = min(r, x);50 }else if(op == ">"){51 l = max(l, x+1);52 }else{53 l = max(l, x);54 } 55 }else{56 if(op == "<"){57 l = max(l, x);58 }else if(op == "<="){59 l = max(l, x+1);60 }else if(op == ">"){61 r = min(r, x);62 }else{63 r = min(r, x-1); 64 } 65 }66 }67 if(l > r) cout << "Impossible" << endl;68 else cout << (l+r)/2 << endl;69 }70 return 0;71 }

View Code

Problem B

递推一下即可sum[i][j] = max(sum[i-1][j], sum[i][j-1])+a[i][j];

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-04-13 15:56 5  * Filename     : Codeforce_241_2_B.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 int a[50000+10][10], sum[50000+10][10];34 int n, m;35 36 void debug(){37 for(int i=0; i<=n; i++){38 for(int j=0; j<=m; j++){39 cout << sum[i][j] << ' ';40 }cout << endl;41 }cout << endl;42 }43 44 int main()45 {46 // freopen("in.txt", "r", stdin);47 48 while(cin >> n >> m){49 memset(a, 0, sizeof a);50 memset(sum, 0, sizeof sum);51 for(int i=1; i<=n; i++)52 for(int j=1; j<=m; j++)53 cin >> a[i][j];54 for(int i=1; i<=m; i++) sum[1][i] = sum[1][i-1] + a[1][i];55 for(int i=1; i<=n; i++) sum[i][1] = sum[i-1][1] + a[i][1];56 for(int i=2; i<=n; i++){57 for(int j=2; j<=m; j++){58 sum[i][j] = max(sum[i-1][j], sum[i][j-1])+a[i][j];59 }60 }61 for(int i=1; i<=n; i++){62 cout << sum[i][m] << ' ';63 }64 cout << endl;65 }66 return 0;67 }

View Code

Problem C

贪心尽量让小的桌子坐下钱多的人就可以了。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-04-13 15:56 5  * Filename     : Codeforce_241_2_C.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 a, b, num;36 }p[LEN];37 struct D{38 int a, num;39 }d[LEN];40 41 bool cmp(P a, P b){42 if(a.a != b.a)return a.b > b.b;43 else return a.a < b.a;44 }45 46 bool cmp2(D a, D b){47 return a.a < b.a;48 }49 50 int main()51 {52 // freopen("in.txt", "r", stdin);53 54 int n, m;55 while(cin >> n){56 for(int i=0; i
                      
                       > p[i].a >> p[i].b;58 p[i].num = i;59 }60 cin >> m;61 for(int i=0; i
                       
                        > d[i].a;63 d[i].num = i;64 }65 sort(d, d+m,cmp2);66 sort(p, p+n, cmp);67 int ans = 0, cnt = 0, f[LEN];68 memset(f, -1, sizeof f);69 for(int i=0; i
                        
                         = 0) continue;73 if(d[i].a >= p[j].a && (tmp == -1 || p[j].b > p[tmp].b)){74 tmp = j;75 }76 }77 if(tmp == -1) continue;78 cnt ++;79 f[tmp] = d[i].num;80 ans += p[tmp].b;81 }82 cout << cnt << ' ' << ans << endl;83 for(int i=0; i
                         
                          = 0){85 cout << p[i].num+1 << ' ' << f[i]+1 << endl;86 }87 }88 }89 return 0;90 }