Codeforces Round #321 (Div. 2)-白红宇

Codeforces Round #321 (Div. 2)

阅读量：6714 次

发布时间：2019-06-25

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

水

/************************************************* Author        :Running_Time* Created Time  :2015/9/23 星期三 00:19:33* File Name     :A.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;int a[N];int main(void) { int n; scanf ("%d", &n); for (int i=1; i<=n; ++i) { scanf ("%d", &a[i]); } int l = 1; int ans = 1; int pre = a[1]; for (int i=2; i<=n; ++i) { if (a[i] >= pre) { pre = a[i]; ans = max (ans, i - l + 1); } else { pre = a[i]; l = i; } } printf ("%d\n", ans); return 0;}

尺取法

题意：每个朋友有他的金钱和友好程度，从朋友中选取一些人，问在贫富差距小于d的最大友好程度和为多少

分析：先按照m金钱从小到大排序，枚举每个起点看以这个人为最穷的人能得到的最大友好程度多少，然后是第二穷的人。。。。。复杂度O (nlogn)，尺取法也叫two points ？

/************************************************* Author        :Running_Time* Created Time  :2015/9/23 星期三 00:19:38* File Name     :B.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;struct Friend { int m, s; bool operator < (const Friend &r) const { return m < r.m; }}f[N];int main(void) { int n, d, mn = INF, mx = -1; ll sum = 0; scanf ("%d%d", &n, &d); for (int i=1; i<=n; ++i) { scanf ("%d%d", &f[i].m, &f[i].s); if (f[i].m > mx) mx = f[i].m; if (f[i].m < mn) mn = f[i].m; sum += f[i].s; } if (mx - mn < d) { printf ("%I64d\n", sum); return 0; } sort (f+1, f+1+n); int l = 1, r = 2; ll ans = f[1].s; sum = f[1].s; while (true) { while (r <= n && f[r].m - f[l].m < d) { sum += f[r++].s; } ans = max (ans, sum); if (r > n) break; sum -= f[l++].s; } printf ("%I64d\n", ans); return 0;}

DFS

题意：从根节点1出发，到底部的点的路径没有超过连续m个点有cat的个数为多少

分析：简单的深搜，记录走到当前点最大连续cat数，注意一些剪枝

/************************************************* Author        :Running_Time* Created Time  :2015/9/23 星期三 00:19:41* File Name     :C.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;vector
                      
                        G[N];int cat[N];bool vis[N];int n, m, ans;void DFS(int u, int fa, int num) { for (int i=0; i

状态压缩DP

题意：n道菜选择m道，每道菜有一个愉悦度，如果某些菜按照先后顺序吃还能得到额外的愉悦度，问最大愉悦度为多少

分析：其实就是一个DAG问题，数据范围18应该想到状压，我不熟悉以为数据范围太大，做不了。dp[mask][i] 表示当在mask集合状态下，最后是第i道菜的最大愉悦度为多少，状态转移方程：dp[(i|(1<<l))][l] = max (dp[i][j] + a[l] + g[j][l]) 复杂度O(2n * n2).

/************************************************* Author        :Running_Time* Created Time  :2015/9/23 星期三 01:49:58* File Name     :D.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 18;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;int n, m, k;ll dp[(1<
                      
                       << n); for (int i=0; i

转载于:https://www.cnblogs.com/Running-Time/p/4832592.html

你可能感兴趣的文章