TopCoder SRM 571 题解-白红宇

TopCoder SRM 571 题解

阅读量：5230 次

发布时间：2019-06-14

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

DIV1 250 && DIV2 500：

1- N之内的数，按照字典序排序，取前最多50个。

eg; N = 11， ans = 1, 10, 11, 2, 3, 4, ..., 9

这道题只能模拟，从1开始，往下加0，一直加到溢出为止，回退，再加1，直到加到末位是0为止：

View Code

1 long long tmp = val * 10;2     if (tmp <= n) dfs(tmp);3     else4     {5          tmp = val + 1;6          if (tmp <= n && tmp % 10 != 0) dfs(tmp);7          else dfs(val / 10 + 1);8     }

DIV2 1000：

题意：一幅图，N(N <= 50)个节点， M条边(M <= 50 * 51 / 2), 每个节点有一个力量值power[i]，要求选出一些节点，满足下列要求：

1. 这些点的数目恰好是K个(K <= 14 && K <= N)

2. 对于每条边edge[i]两个端点(u, v)，必定至少有一个被选进set中

要求选出满足 condition 1和2的节点power之和的最大值。覆盖cover类型。

上来不敢下手，递归吧，感觉复杂度挺大的，大约是C(50, K)，肯定超时。但是没有从边的角度上思考问题：枚举每一条边，此时有三种可能，

a. u，v都未被覆盖，此时需要把u 和 v之间的一个加进去set中；

b. u， v已经有一个被加到set里了，此时不做任何处理

c. u 和 v 都在set中，同b

关键是对于每条边来说，只满足一个点被覆盖就行。但是存在一种情况，就是满足所有边被覆盖的点的个数，不到K。eg

1-2, 2-3, 3-4 N = 4, K = 3, 选择set(2, 3)或者set(2, 4) 或者 set(3, 1), 都可以覆盖所有边，但是set.size() < K，还可以选一个点，选哪个呢？

此时只要把剩下的没被选的直接排序，选择前(K - set.size()) 大的即可！贪心ORZ

再看复杂度：递归深度最多是K次，综合 a, b, c, 每次递归做多有两次选择(情况a), 所以复杂度是 O(M * 2 ^ K) MAX(50 * 50 / 2 * 2 ^ 14) = 20480000

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;vector
                
                  magicPower;vector
                 
                   magicBond;struct node{ int x, y; node(){} node(int _x, int _y){x = _x; y = _y;}};vector
                  
                   edge;int n, k;int ans = -1;int m = 0;void dfs(int id, long long state, int select){ int i, j; int val = 0; if (select > k) return; if (id == m) { vector
                   
                    v; for (i = 0; i < n; i++) { if ( (state >> (long long)i) & 1) val += magicPower[i]; else v.push_back(magicPower[i]); } cout << select << "\t"; sort(v.begin(), v.end()); reverse(v.begin(), v.end()); for (i = 0; i < k - select && i < v.size(); i++) { val += v[i]; } ans = max(ans, val); cout << ans << endl; return; } int start = edge[id].x; int end = edge[id].y; if ( !((state >> (long long)start) & 1L) && !((state >> (long long)end) & 1L) ) { dfs(id + 1, state | (1LL << start), select + 1); dfs(id + 1, state | (1LL << end), select + 1); } else dfs(id + 1, state, select);}class MagicMoleculeEasy{public: int maxMagicPower(vector
                    
                      _magicPower, vector
                     
                       _magicBond, int _k) { k = _k; magicPower = _magicPower; magicBond = _magicBond; n = magicPower.size(); int i, j; for (i = 0; i < _magicBond.size(); i++) { for (j = i + 1; j < _magicBond[0].size(); j++) { if (_magicBond[i][j] == 'Y') edge.push_back(node(i, j)); } } m = edge.size(); dfs(0, 0, 0); return ans; }};

DIV1 500:

同上，只不过条件1和2变化了：

1. 选出来的点是K个，满足3 * K >= 2 * N, 即 K >= 2 / 3 * N

2. 对于每个在集合中连个节点i, j， i和j有一条边相连

考虑到 K >= 2 / 3 * N，所以如果像上面那样递归，肯定会超时。根据tc的官方题解，此时如果换个角度思考问题：最多拿出 N / 3 (50 / 3 = 17.X)的点，使得剩下的任意的两点满足2.

问题是，要拿出哪些点？考虑到条件2，假如 (i , j) 没有边连接，那么i和j至少要删除一个。

此时问题就可以简化为，在图中至多选取K个点，其中 (K < N / 3), 对于图中每一对(i, j)，其中i和j没有边连接，至少i或j被选取。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;vector
                
                  magicPower;vector
                 
                   magicBond;struct node{ int x, y; node(){} node(int _x, int _y){x = _x; y = _y;}};vector
                  
                   edge;int n;int ans = -1;int m = 0;void dfs(int id, long long state, int select){ int i, j; int val = 0; if (select * 3 > n) return; if (id == m) { vector
                   
                    v; for (i = 0; i < n; i++) { if ( !((state >> (long long)i) & 1) ) val += magicPower[i]; } ans = max(ans, val); cout << ans << endl; return; } int start = edge[id].x; int end = edge[id].y; if ( !((state >> (long long)start) & 1L) && !((state >> (long long)end) & 1L) ) { dfs(id + 1, state | (1LL << start), select + 1); dfs(id + 1, state | (1LL << end), select + 1); } else dfs(id + 1, state, select);}

转载于:https://www.cnblogs.com/kaitian521/archive/2013/05/04/3060268.html

你可能感兴趣的文章