首页 > 代码库 > HDU 5877 Weak Pair
HDU 5877 Weak Pair
题目：Weak Pair
链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5877
题意：给一棵树和一个定值k，每个点的值w，对于两点（u、v），如果u 是v 的祖先，且w[u]*w[v]<=k，则说u、v是弱的，问树中有多少对u、v是弱的。
思路：
第一个要求u 是v 的祖先，那么可以dfs，遍历到v时，所有他上方的都是满足第一条件的u，做多了树就很容易想到在退出某个子树的时候消除这个影响，这样就能保证所有有影响的都是祖先。要求w[u]*w[v]<=k，那么到v的时候，所有小于等于k/w[v]的u都满足，可以想到树状数组。结点的值最大10亿，肯定要离散化，离散化的时候要把k/w[v]加进去一起离散。
AC代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<set> 6 #include<map> 7 #include<list> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 #include<string> 12 #include<iostream> 13 #include<algorithm> 14 using namespace std; 15 #define lson rt<<1 16 #define rson rt<<1|1 17 #define N 100010 18 #define M 100010 19 #define Mod 1000000007 20 #define LL long long 21 #define INF 0x7fffffff 22 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++) 23 #define For(i,f_start,f_end) for(int i=f_start;i<f_end;i++) 24 #define REP(i,f_end,f_start) for(int i=f_end;i>=f_start;i--) 25 #define Rep(i,f_end,f_start) for(int i=f_end;i>f_start;i--) 26 #define MT(x,i) memset(x,i,sizeof(x)) 27 #define gcd(x,y) __gcd(x,y) 28 const double PI = acos(-1); 29 30 int c[N<<1]; 31 int Lowbit(int x) 32 { 33 return x&(-x); 34 } 35 int getsum(int pos) 36 { 37 int sum=0; 38 while(pos>0) 39 { 40 sum+=c[pos]; 41 pos-=Lowbit(pos); 42 } 43 return sum; 44 } 45 void update(int pos,int num,int n) 46 { 47 while(pos<=n) 48 { 49 c[pos]+=num; 50 pos+=Lowbit(pos); 51 } 52 } 53 54 int n; 55 LL sum,k; 56 LL w[N<<1]; 57 vector<int> v[N]; 58 int p[N<<1]; 59 int xin; 60 void dfs(int rt) 61 { 62 int pos; 63 pos=w[rt+n]; 64 sum += getsum(pos); 65 66 update(w[rt],1,xin); 67 For(i,0,v[rt].size()){ 68 int son = v[rt][i]; 69 dfs(son); 70 } 71 update(w[rt],-1,xin); 72 } 73 74 bool cmp(int x,int y) 75 { 76 return w[x]<w[y]; 77 } 78 79 bool f[N]; 80 int main() 81 { 82 int t,x,y; 83 scanf("%d",&t); 84 while(t--) 85 { 86 scanf("%d%I64d",&n,&k); 87 FOR(i,1,n){ 88 scanf("%I64d",&w[i]); 89 if(w[i]==0) w[n+i]=INF; 90 else w[n+i]=k/w[i]; 91 p[i]=i; 92 p[n+i]=n+i; 93 } 94 sort(p+1,p+n+n+1,cmp); 95 xin = 0; 96 int pre = -1; 97 FOR(i,1,n+n) 98 { 99 if(w[p[i]]>pre){ pre=w[p[i]]; w[p[i]]=++xin; }100 else{ pre=w[p[i]]; w[p[i]]=xin; }101 }102 memset(f,0,sizeof(f));103 For(i,1,n){104 scanf("%d%d",&x,&y);105 v[x].push_back(y);106 f[y]=1;107 }108 MT(c,0);109 sum = 0;110 FOR(i,1,n){111 if(f[i]==false)112 {113 dfs(i);114 break;115 }116 }117 printf("%I64d\n",sum);118 FOR(i,1,n){119 v[i].clear();120 }121 }122 return 0;123 }
HDU 5877 Weak Pair
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。