- 浏览: 583892 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
关于树状数组:参看:http://128kj.iteye.com/blog/1743633
POJ3321 题意:
一棵具有n个节点的树,一开始,每个节点上都有一个苹果。现在给出m组动态的操作:
(C,i)是摘掉第i个节点上面的苹果(若苹果不存在,则为加上一个苹果),(Q,i)是查询以第i个节点为根的子树有几个苹果(包括第i个节点)。
输入是叉之间的关系,
1 2
1 3
就是主干上面两个叉分别是2 和3.
样例:
Sample Input
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
分析:
用树状数组求和,这个数组怎么来定?
从root开始dfs下去记录第一次访问u点时的时间戳为Begin[u](下标),当访问完以u为根的所有子树以后要向上回溯的时候,再记录一个时间戳End[u](下标),这样,这棵树上子树u上的所有苹果和就是Begin[u]到End[u]的区间和,操作就和普通的树状数组一样了~
下面是AC过的代码:
源码:
POJ3321 题意:
一棵具有n个节点的树,一开始,每个节点上都有一个苹果。现在给出m组动态的操作:
(C,i)是摘掉第i个节点上面的苹果(若苹果不存在,则为加上一个苹果),(Q,i)是查询以第i个节点为根的子树有几个苹果(包括第i个节点)。
输入是叉之间的关系,
1 2
1 3
就是主干上面两个叉分别是2 和3.
样例:
Sample Input
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
分析:
用树状数组求和,这个数组怎么来定?
从root开始dfs下去记录第一次访问u点时的时间戳为Begin[u](下标),当访问完以u为根的所有子树以后要向上回溯的时候,再记录一个时间戳End[u](下标),这样,这棵树上子树u上的所有苹果和就是Begin[u]到End[u]的区间和,操作就和普通的树状数组一样了~
下面是AC过的代码:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.*; public class Main{ //把苹果树作图处理了。 private List<ArrayList<Integer>> G;// 邻接表。注:使用邻接矩阵内存溢出。 private int k;//顶点数目 private boolean[] visited;//判断顶点是否被访问过 private int[] Begin; private int[] End; private int Count=0; private int Tree[];//树状数组 public Main(int k,List<ArrayList<Integer>> G){ this.k=k; this.G=G; visited = new boolean[k+1]; Begin=new int[k+1]; End=new int[k+1]; Tree=new int[k+1]; } public int getBegin(int i){ return Begin[i]; } private void cl(){ for(int i=0;i<=k;i++) visited[i]=false; } private int getEnd(int i){ return End[i]; } public boolean getVis(int i){ return visited[i]; } private void setVis(int i,boolean fal){ visited[i]=fal; } private int lowbit(int i) { return i&(-i); } void Update(int i,int Num){ while(i<= k){ Tree[i] += Num; i += lowbit(i); } } int Sum(int i){ int sum = 0; while(i>0){ sum += Tree[i]; i -= lowbit(i); } return sum; } public static void main(String[] args) throws IOException{ StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); int k; sc.nextToken(); k = (int) sc.nval; //顶点数 List<ArrayList<Integer>> G; //构建邻接表 G = new ArrayList<ArrayList<Integer>>(); for(int i = 0;i<=k;i++) G.add(new ArrayList<Integer>());//初始化邻接表 for (int i = 1; i <k; i++) { sc.nextToken(); int u = (int) sc.nval; sc.nextToken(); int v = (int) sc.nval; if(!G.get(u).contains(v)) {//避免重边的情况比如a b可能出现两次的情况 G.get(u).add(v); } //对于无向图 if(!G.get(v).contains(u)) { G.get(v).add(u); } } Main ma=new Main(k,G); ma.dfs(1); for(int i = 1;i <= k;i++){ ma.Update(i,1); } sc.nextToken(); int M=(int) sc.nval; ma.cl(); for(int i = 0;i < M;i++){ sc.nextToken(); String Op=sc.sval; sc.nextToken(); int Num=(int) sc.nval; if(Op.equals("C")){ if(!ma.getVis(Num)) ma.Update(ma.getBegin(Num),-1);//摘苹果 else ma.Update(ma.getBegin(Num),1);//长一个 ma.setVis(Num,!ma.getVis(Num)); }else if(Op.equals("Q")){ System.out.printf("%d\n",ma.Sum(ma.getEnd(Num))-ma.Sum(ma.getBegin(Num)-1)); } } } // 深搜 private void dfs(int v) { Begin[v] = ++Count; visited[v] = true; //System.out.print(v+" "); for (int i = 0; i <G.get(v).size(); i++) { //递归调用搜索没有被访问过的当前节点的下一个节点(邻接点) int k=G.get(v).get(i); if (!visited[k]) dfs(k); } End[v] = Count; } }
源码:
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3660题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1526POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2327北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1945import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2981POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1431POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1848题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1593关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1822关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1830POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1725POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1563分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2173接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1354接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2418当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1674关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1749关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1701一、树状数组是干什么的? 平常我们会遇到一些对数组进 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1772172
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1744222
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1746750
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
POJ 1328 java做!雷达问题!java版本!AC答案~
用java的biginteger实现的poj1001,比较简单的方法
NULL 博文链接:https://128kj.iteye.com/blog/1733777
NULL 博文链接:https://128kj.iteye.com/blog/1749213
NULL 博文链接:https://128kj.iteye.com/blog/1705139
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
POJ1048,加强版的约瑟夫问题 难度中等
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
北大poj JAVA源码
NULL 博文链接:https://128kj.iteye.com/blog/1757060
pku acm 第3356题 AGTC Java代码,有详细的注释,动态规划
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138