TopCoder SRM 570 题解-白红宇

TopCoder SRM 570 题解

阅读量：4977 次

发布时间：2019-06-12

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

官方题解在

DIV2的前两题比较简单，忽略

DIV2 第三题 1000，题意是：给一个N个节点的树(共有N - 1条边)，要求是从这些点中抽取一些点(可以一个也不选)，保证抽取的点也是一颗树。

一看这个题的结果非常大，枚举所有可能的做法必定超时(O(2**50)), 观察到，可以通过树的递推关系来计算父节点的数目：令dp[i]表示以i为根，并且含有i的个数

含有某一个节点i的子树的数目： dp[i] = multi(dp[children of i] + 1),其中1表示子树可以为空。

最后再计算 sum(dp[i]) for i in range(0, n)，别忘了 + 1

1 #include 
     
       2 #include 
      
        3 #include 
        4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 #include 
                    
                     17 #include 
                     
                      18 #include 
                      
                       19 #include 
                       
                        20 #include 
                        
                         21 using namespace std;22 #define N 6023 int n;24 int tree[N][N];25 bool connect[N][N];26 bool visit[N];27 long long dp[N];28 29 void dfs(int v)30 {31 visit[v] = 1;32 int i = 0, j = 0;33 //cout << v << " : ";34 for (i = 0; i < n; i++)35 {36 if (!connect[v][i] || visit[i]) continue;37 tree[v][j++] = i;38 //cout << i << " ";39 }40 //cout << endl;41 for (i = 0; i < j; i++)42 {43 dfs(tree[v][i]);44 }45 }46 47 long long ans = 0;48 long long f()49 {50 int i, j;51 queue
                         
                          q;52 q.push(0);53 vector
                          
                           v;54 while(!q.empty())55 {56 int tt = q.front();57 v.push_back(tt);58 q.pop();59 for(i = 0; tree[tt][i] != -1; i++) q.push(tree[tt][i]);60 }61 for (i = v.size() - 1; i >= 0; i--)62 {63 int cnt = 0;64 long long X = 1;65 for (j = 0; tree[v[i]][j] != -1; j++)66 {67 cnt ++;68 X *= (dp[tree[v[i]][j]] + 1);69 }70 if (cnt == 0) dp[v[i]] = 1;71 else dp[v[i]] = X;72 }73 for (i = 0; i < n; i++)74 {75 ans += dp[i];76 cout << i << "\t" << (int)dp[i] << endl;77 }78 return ans;79 }80 81 class CentaurCompanyDiv2 {82 public:83 long long count(vector 
                           
                            , vector 
                            
                             );84 };85 86 long long CentaurCompanyDiv2::count(vector 
                             
                               a, vector 
                              
                                b) {87 n = a.size() + 1;88 int i, j, k;89 memset(tree, -1, sizeof(tree));90 for (i = 0; i < a.size(); i++)91 {92 connect[a[i] - 1][b[i] - 1] = 1;93 connect[b[i] - 1][a[i] - 1] = 1;94 }95 dfs(0);96 f();97 return ans + 1;98 }

DIV1 第一题，注意T很大， 10**9，暴力必定超时，只能找规律了，发现angle只能四个方向，找到循环节(1,2,4) 再把没计算的 T - T % rotate 计算一下就好。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;int n;int dir[4][2] = { 1, 0, 0, -1, -1, 0, 0, 1};long long x, y, angle;vector
              
               a;long long myabs(long long T){ if (T < 0) return -T; return T;}void f(){ int i; for (i = 0; i < a.size(); i++) { x += dir[angle][0] * a[i]; y += dir[angle][1] * a[i]; angle = (angle + a[i]) % 4; }}class RobotHerb{public: long long getdist(int T, vector 
               
                 _a) { long long xx, yy; int i, j; a = _a; f(); if (angle == 0) { xx = x * T; yy = y * T; return myabs(x) + myabs(y); } if (angle == 1) { x = 0; y = 0; angle = 0; for (i = 0; i < 4; i++) { for (j = 0; j < a.size(); j++) { x += dir[angle][0] * a[j]; y += dir[angle][1] * a[j]; angle = (angle + a[j]) % 4; } } long long cnt = T / 4; xx = x * cnt; yy = y * cnt; for (i = 0; i < T % 4; i++) { for (j = 0; j < a.size(); j++) { xx += dir[angle][0] * a[j]; yy += dir[angle][1] * a[j]; angle = (angle + a[j]) % 4; } } return myabs(xx) + myabs(yy); } if (angle == 2) { x = 0; y = 0; angle = 0; for (i = 0; i < 2; i++) { for (j = 0; j < a.size(); j++) { x += dir[angle][0] * a[j]; y += dir[angle][1] * a[j]; angle = (angle + a[j]) % 4; } } long long cnt = T / 2; xx = x * cnt; yy = y * cnt; for (i = 0; i < T % 2; i++) { for (j = 0; j < a.size(); j++) { xx += dir[angle][0] * a[j]; yy += dir[angle][1] * a[j]; angle = (angle + a[j]) % 4; } } return myabs(xx) + myabs(yy); } if (angle == 3) { x = 0; y = 0; angle = 0; for (i = 0; i < 4; i++) { for (j = 0; j < a.size(); j++) { x += dir[angle][0] * a[j]; y += dir[angle][1] * a[j]; angle = (angle + a[j]) % 4; } } long long cnt = T / 4; xx = x * cnt; yy = y * cnt; for (i = 0; i < T % 4; i++) { for (j = 0; j < a.size(); j++) { xx += dir[angle][0] * a[j]; yy += dir[angle][1] * a[j]; angle = (angle + a[j]) % 4; } } return myabs(xx) + myabs(yy); } return 0; }};int main(){ return 0;}

转载于:https://www.cnblogs.com/kaitian521/archive/2013/04/30/Topcoder_SRM_570.html

你可能感兴趣的文章