HDU 5877 Weak Pair （2016年大连网络赛 J dfs+反向思维）

阅读量：6253 次

发布时间：2019-06-22

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

正难则反的思想还是不能灵活应用啊

题意：给你n个点，每个点有一个权值，接着是n-1有向条边形成一颗有根树，问你有多少对点的权值乘积小于等于给定的值k，其中这对点必须是孩子节点与祖先的关系

我们反向思考，可以知道任一点都只对其每个祖先有贡献。所以我们可以转化为求每个点与其每个祖先的乘积小于等于给定的值k的对数。

我们dfs遍历这颗树使用树状数组维护，dfs遍历孩子就添点回溯就删点，接着对每个点计算树状数组里不大于（k/此点）的个数。注意值太大我们需要离散化，而且我们可以把每个点m与k/m都离散化出来，然后就是每次树状数组更新这个点的个数（加减1），查询不大于（k/此点）的个数

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x
                 
                   0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                  
                   >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=200010;struct node{ int pos; ll val;} nod[Max];int bit[Max],vis[Max],n;ll k,ans,rop[Max];int head[Max],nnext[Max],to[Max],e;bool cmp(struct node p1,struct node p2){ if(p1.val==p2.val) return p1.pos

Weak Pair

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5870036.html

你可能感兴趣的文章