TC SRM 584 DIV2-白红宇

TC SRM 584 DIV2

阅读量：7145 次

发布时间：2019-06-29

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

250pt:

水题set处理。

500pt：

题意：

给你一个图，每条边关联的两点为朋友，题目要求假设x的金钱为y，则他的左右的朋友当中的钱数z，取值为y - d <= z <= y + d.求使得任意两点的最大金钱差值，若果是inf输出-1.

思路：

求任意两点的最短的的最大值即可，比赛时不知道哪地方写搓了，直接被系统样例给虐了，老师这么悲剧500有思路能写，老师不仔细哎..

floyd求任意两点的最短距离好写一些。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define keyTree (chd[chd[root][1]][0])#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 25000#define N 207using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;int f[N][N];int n;void floyd(){ for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (f[i][k] != inf && f[k][j] != inf && f[i][j] > f[i][k] + f[k][j]) { f[i][j] = f[i][k] + f[k][j]; } } } }}class Egalitarianism{ public: int maxDifference(vector 
                    
                      isF, int d) { n = isF.size(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) f[i][j] = inf; } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (isF[i][j] == 'Y') { f[i + 1][j + 1] = 1; } } } floyd(); int Ma = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i == j) continue; Ma = max(Ma,f[i][j]); } } if (Ma == inf) return -1; else return Ma*d; }};

View Code

100pt：

题意：

有n个城市，给出每个城市的类型kind[i]表示i城市属于kind[i]类，然后给出已经发现的类型found[i]表示发现了found[i]类型，然后给出k求满足有k个城市，并且这k个城市包含了m中已将发现的类型。（k个城市都是从已经发现的类型里面选的）也即：知道m种数的每种数个数，然后将这些数放入K个箱子里面连，每个箱子只能放一个，要求放完后这k个箱子的数的种数为m

思路：

才开始想用组和公式方看看怎么放，可是那样考虑会有很多重复，而且不好去重。

dp其实很简单，可是就是想不到，弱逼的DP啊。 dp[i][j] 表示一共放了j个箱子，并且放了i种则dp[i][j] += dp[i - 1][j - p]*c[found[i]][p];

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define keyTree (chd[chd[root][1]][0])#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 25000#define N 107using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;ll dp[N][N];ll c[55][55];void init(){ for (int i = 0; i <= 50; ++i) { c[i][i] = c[i][0] = 1; } for (int i = 2; i <= 50; ++i) { for (int j = 1; j < i; ++j) { c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; } }}class Excavations2{ public: int num[N]; long long count(vector 
                    
                      kind, vector 
                     
                       found, int K) { init(); int n = kind.size(); int m = found.size(); CL(num,0); for (int i = 0; i < n; ++i) num[kind[i]]++; CL(dp,0); dp[0][0] = 1; for (int i = 0; i < m; ++i) { for (int j = 0; j <= K; ++j) { for (int p = 1; p <= num[found[i]]; ++p) { if (j - p >= 0) dp[i + 1][j] += dp[i][j - p]*c[num[found[i]]][p]; } } } return dp[m][K]; }};

View Code

转载地址：http://rjgrl.baihongyu.com/

你可能感兴趣的文章