- 浏览: 601608 次
- 来自: ...
文章分类
最新评论
-
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 3747题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1658POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2396北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1987import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3054POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1478POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1929题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1641关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1870关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1880POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1897POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1766POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1647分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2252接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1544关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1397接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2468当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1821关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1819关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1773一、树状数组是干什么的? 平常我们会遇到一些对数组进 ...
相关推荐
【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...
标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...
它扩展了一维树状数组(也称作线段树),能够处理二维或多维的数组更新和查询操作。在POJ 2029这个题目中,我们可能面临的问题是需要对一个二维矩阵进行动态更新和求和查询,例如计算某一个矩形区域内的元素总和。 ...
【标题】"树状数组练习:POJ 3067" 树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。...
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
二维树状数组(也称为2D BIT,即二维前缀和)是一种在计算机科学和算法设计中用于高效处理数组更新和查询的数据结构。它在处理矩阵或网格状数据时非常有用,尤其对于需要频繁进行区间求和或者更新的场景。在本篇中,...
### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...
* 树状树组 + poj1195, poj3321 * RMQ + poj3264, poj3368 * 并查集的高级应用 + poj1703, poj2492 * KMP算法 + poj1961, poj2406 四、搜索 * 最优化剪枝和可行性剪枝 * 搜索的技巧和优化 + poj3411, poj1724
树状数组,又称线段树(Segment Tree),是一种用于高效解决区间查询与修改问题的数据结构。在上述题目中,树状数组被广泛应用于各种不同的场景,如星星坐标的等级计算、矩阵操作、序列排序优化以及线路交叉点的计算...
标题中的“字典树练习 POJ 1056”是指一个编程问题,源自编程竞赛网站POJ(Programming Online Judge)的题目1056。POJ是一个在线平台,程序员可以在这里提交代码并测试其正确性,以解决给定的问题。这类问题通常...
【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...
标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...
最小生成树是一棵树形结构,包含了原图的所有顶点,并且其所有边的权重之和最小。 Prim算法的基本思想是从一个起始顶点开始,逐步将与已选顶点集合连接的、具有最小权重的边加入到生成树中,直到所有顶点都被包含。...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
"C++ 数组扩充"提示我们问题可能与如何在C++编程语言中处理数组的增长有关,而"poj 26_poj 2682_poj26"似乎是重复提及问题编号,可能是用户在整理文件时的习惯。 描述中提到的“数链思想”可能是指一种处理数组元素...
**树状数组**(Binary Indexed Tree, BIT),又称**费尼克树**(Fenwick Tree),是一种特殊的数据结构,它能高效地完成对数组元素的累加查询和更新操作。相较于其他数据结构如线段树,树状数组在实现上更为简洁,...
用java的biginteger实现的poj1001,比较简单的方法