HDU4670 Cube number on a tree 树分治-白红宇

HDU4670 Cube number on a tree 树分治

阅读量：4963 次

发布时间：2019-06-12

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

人生的第一道树分治,要是早点学我南京赛就不用那么挫了,树分治的思路其实很简单,就是对子树找到一个重心(Centroid),实现重心分解,然后递归的解决分开后的树的子问题,关键是合并,当要合并跨过重心的两棵子树的时候,需要有一个接近O(n)的方法,因为f(n)=kf(n/k)+O(n)解出来才是O(nlogn).在这个题目里其实就是将第一棵子树的集合里的每个元素,判下有没符合条件的,有就加上,然后将子树集合压进大集合,然后继续搞第二棵乃至第n棵.我的过程用了map,合并是nlogn的所以代码速度颇慢,大概6s,题目时限10s,可以改成hash应该会快许多,毕竟用map实在太慢,用vector也可以,具体可以参见挑战程序设计竞赛代码.下面的代码查找重心用了挑战的代码.

#pragma comment(linker, "/STACK:102400000,102400000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #define maxv 50000#define ll long longusing namespace std;int n,k;vector
            
              G[maxv+50];ll val[maxv+50];ll prime[maxv+50];ll convert_three(ll v){ ll bas=1;ll res=0; for(int i=0;i
             
               sta;map
              
               ::iterator it;int compute_ssize(int v,int p){ int c=1; for(int i=0;i
               
                 search_centroid(int v,int p,int t){ pair
                
                  res=make_pair(INT_MAX,-1); int s=1,m=0; for(int i=0;i
                 
                   &ds){ if(ds.count(d)) ds[d]++; else ds[d]=1; for(int i=0;i
                  
                    tds; for(int i=0;i
                   
                    >n>>k){ ans=0; for(int i=0;i

转载于:https://www.cnblogs.com/chanme/p/3411639.html

你可能感兴趣的文章

SwaggerUI+SpringMVC——构建RestFul API的可视化界面