首页 > 代码库 > HDU4605---Magic Ball Game（主席树 好题）
HDU4605---Magic Ball Game（主席树 好题）
题意：一颗二叉树，任意节点要么有两个孩子要么没孩子。
然后有一个球，从结点1开始往子孙结点走。
每碰到一个结点，有三种情况
如果此球重量等于该结点重量，球就停下了
如果此球重量小于该结点重量，则分别往左右儿子走的可能都是1/2
如果此球重量大于该结点重量，则走向左儿子的概率是1/8，右儿子的概率是7/8
然后若干个询问（10^5次），问一个重量为x的球经过结点v的概率
观察路径，可以发现路径可以分成两种，向左走的路径和向右走的路径，分成这两种是因为各自的计算公式，在向左走的路径中，设大于x的点权有a个，小于x的点权有b个，同理定义c d，我们只需要求出a b c d 就可以了。
做法：
貌似很多做法，，我是用主席树多的，对于节点V，建立根节点1到V的前缀线段树，（此过程bfs实现）利用主席树的性质。
然后主席树里面存两个信息，一个是向左走的一个是向右走的。（此题一些细节，二分的时候不注意的话就会一直wa）
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 #include <queue> 5 #include <cstring> 6 using namespace std; 7 8 const int maxn = 1e5+10; 9 struct Edge 10 { 11 int to,next,kind; 12 } e[maxn<<1]; 13 int head[maxn],edge_idx; 14 void add_edge(int x,int y,int kind) 15 { 16 e[edge_idx].to = y; 17 e[edge_idx].next = head[x]; 18 e[edge_idx].kind = kind; 19 head[x] = edge_idx++; 20 } 21 //---------------------------------- 22 int lcnt[maxn*30],rcnt[maxn*30],lson[maxn*30],rson[maxn*30]; 23 int tree[maxn<<1],tot,tree_max; 24 int build (int l,int r) 25 { 26 int root = tot++; 27 lcnt[root] = rcnt[root] = 0; 28 if (l != r) 29 { 30 int mid = (l + r) >> 1; 31 lson[root] = build(l,mid); 32 rson[root] = build(mid+1,r); 33 } 34 return root; 35 } 36 int update (int root,int pos,int lval,int rval) 37 { 38 int newroot = tot++; 39 int tmp = newroot; 40 int l = 1,r = tree_max; 41 lcnt[newroot] = lcnt[root] + lval; 42 rcnt[newroot] = rcnt[root] + rval; 43 while (l < r) 44 { 45 int mid = (l + r) >> 1; 46 if (pos <= mid) 47 { 48 r = mid; 49 rson[newroot] = rson[root]; 50 root = lson[root]; 51 lson[newroot] = tot++; 52 newroot = lson[newroot]; 53 } 54 else 55 { 56 l = mid + 1; 57 lson[newroot] =lson[root]; 58 root = rson[root]; 59 rson[newroot] = tot++; 60 newroot = rson[newroot]; 61 } 62 lcnt[newroot] = lcnt[root] + lval; 63 rcnt[newroot] = rcnt[root] + rval; 64 } 65 return tmp; 66 } 67 int query(int root,int l,int r,int ua,int ub,int kind) 68 { 69 if (ub < ua) 70 return 0; 71 if (ua <= l && ub >= r) 72 { 73 if (kind) 74 return rcnt[root]; 75 else 76 return lcnt[root]; 77 } 78 int mid = (l + r) >> 1; 79 int t1 = 0, t2 = 0; 80 if (ua <= mid) 81 t1 = query(lson[root],l,mid,ua,ub,kind); 82 if (ub > mid) 83 t2 = query(rson[root],mid+1,r,ua,ub,kind); 84 return t1 + t2; 85 } 86 87 int W[maxn],vec[maxn],idx; 88 int hash_(int x) 89 { 90 return lower_bound(vec,vec+idx,x) - vec + 1; 91 } 92 void init() 93 { 94 memset(head,-1,sizeof(head)); 95 idx = tot = 0; 96 edge_idx = 0; 97 } 98 int main(void) 99 {100 #ifndef ONLINE_JUDGE101 freopen("in.txt","r",stdin);102 #endif103 int T;104 scanf ("%d",&T);105 while (T--)106 {107 init();108 int n,q,m;109 scanf ("%d",&n);110 for (int i = 0; i < n ; i++)111 {112 scanf ("%d",W+i+1);113 vec[idx++] = W[i+1];114 }115 sort(vec,vec+idx);116 idx = unique(vec,vec+idx) - vec;117 scanf ("%d",&m);118 for (int i = 0; i < m; i++)119 {120 int x,lf,rg;121 scanf ("%d%d%d",&x,&lf,&rg);122 add_edge(x,lf,0);123 add_edge(x,rg,1);124 }125 tree_max = n;126 tree[1] = build(1,n);127 128 queue<int>Q;129 while (!Q.empty())130 Q.pop();131 Q.push(1);132 while (!Q.empty())133 {134 int x = Q.front();135 Q.pop();136 for (int i = head[x]; ~i; i = e[i].next)137 {138 int v,k;139 v = e[i].to, k = e[i].kind;140 tree[v] = update(tree[x],hash_(W[x]),k == 0, k == 1);141 Q.push(v);142 }143 }144 scanf ("%d",&q);145 for (int i = 0; i < q; i++)146 {147 int x,v;148 scanf ("%d%d",&v,&x);149 if (v == 1)150 {151 printf("0 0\n");152 continue;153 }154 int tmp = x; //155 x = hash_(x); // 二分得到的值可能原数组并不存在156 int ua = x-1, ub = x; //理论上要查询x+1，但是如果tmp在原数组中不存在，那么就不用+1了157 int flag = 0;158 flag = query(tree[v],1,n,x,x,0) + query(tree[v],1,n,x,x,1);159 if (vec[x-1] == tmp)160 {161 if (flag)162 {163 printf("0\n");164 continue;165 }166 ub++;167 }168 int lf_small = query(tree[v], 1, n, 1, ua, 0);169 int lf_big = query(tree[v], 1, n, ub, n, 0);170 int rg_small = query(tree[v], 1, n, 1, ua, 1);171 int rg_big = query(tree[v], 1, n, ub, n, 1);172 int ans1 = 0, ans2 = 0;173 ans1 += rg_small;174 ans2 += 3*(rg_small+lf_small) + rg_big + lf_big;175 printf("%d %d\n",ans1,ans2);176 }177 }178 return 0;179 }
HDU4605---Magic Ball Game（主席树 好题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。