二叉索引树(树状数组)——题解
P1993[树状数组]种树题目描述：
Jzyz的机房的新规定明确说明，机房高一最强的人要接受惩罚，于是杨树辰就被罚去植树了。我们把jzyz对面的一条路看成一条长度为n的线，晗神给杨树神指定了一些区间让他种树，美其名曰让他减肥，但是晗神在中间会来检查杨树神的工作，询问杨树神一个点上有几棵树，但是杨树神不仅代码敲得贼好，而且眼神非常好，但是作为大佬的杨树神想考考你，并让你设计一个程序来帮他完成晗神的检查。
输入：
第一行：n和m。
第2到 m+1行：每行开头一个z Z=1，后跟两个整数L和R表示种树的区间L,R，0<=L<=R<=n. Z=2，后跟一个整数x，表示询问的地点的树的个数,0<=x<=n.
输出：
对于每个z==2的答案。1<=n,m<=1000000;
题解：这里是运用到了树状数组的区间操作，我们对于修改一个区间的元素已经很清楚了，只需要将所有的数组都加上就好了，那么检查的时候我们就需要将左端点到1种上-1棵树，然后右端点到1种上1棵树，这样的话我们就可以对于一个区间进行修改了。
但是恶意卡快读快输就不对了啊……
代码：1234 ...
二叉索引树(树状数组)——讲解
写在前面
追随树神的脚步！然而树神写的PPT还是很良心的，很快就看懂了，题解也不错。
原理
然后树状数组是不需要建树的，它的树成分并没有线段树那么强，是通过一个特殊的Lowbit来建立起来的；
树状数组的实现方式是用一个c数组维护原来的数组a，
Lowbit讲解：c[i]=sum(a[j]) i-lowbit(i)+1<=j<=i;
这里的 lowbit(i) 表示将i转换成二进制后的最右边的1到最后所形成的十进制的数。
例如 lowbit(6)=lowbit(110)2=(10)2=2
所以 c[6]=a[5]+a[6];
lowbit(4)=lowbit(100)2=(100)2=4
c[4]=a[1]+a[2]+a[3]+a[4]
lowbit[5]=lowbit(101) 2 =(1) 2=1;
c[5]=a[5]
Lowbit公式：下面是重点！！！
1lowbit(i)=i&(-i);
公式原理：上面这个公式是非常重要的，就是通过求出一个数的 Lowbit 将这些数据建立成一个树的，父子节点和线段树关系类似，都是通过某种固定的方式建立起来的。而 ...
二叉搜索树(线段树)
线段树线段树原理：首先，线段树是一棵“树”，而且是一棵完全二叉树。同时，“线段”两字反映出线段树的另一个特点：每个节点表示的是一个“线段”，或者说是一个区间。事实上，一棵线段树的根节点表示的是“整体”的区间，而它的左右子树也是一棵线段树，分别表示的是这个区间的左半边和右半边。
线段树就是这样一种数据结构。它能够将我们需要处理的区间不相交的分成若干个小区间，每次维护都可以在这样一些分解后的区间上进行，并且查询的时候，我们也能够根据这些被分解了的区间上的信息合并出整个询问区间上的查询结构。
下面是个线段树（线段）的图示：
然后这个也是一个线段树（点）的图示：
我们就是利用这种方法搞的。
线段树模板(点)：然后就是DFS模板：
查找最大值：123456789int Search(int Left,int Right,int Root){ if(y<Left||x>Right) return -123456789; if(x<=Left&&y>=Right) return a[Root]; int Mid=(Left+Ri ...
May 刷题柱
写在前面
少年你已经落后于别人不少了，如果你还想冲击NOI的话，赶快去刷题，不要浮躁，用自己的努力来证明自己！
刷题柱感觉自己完全太弱了啊，还是守着文化课吧，冲击省队毕尽只是梦想，转段考试结束就滚回去学文化课吧，停课还是不敢想了，毕竟进队概率太小，并且文化课太烂。OI最后去一下省选，如果靠着骗分暴力能够水进省队（毕竟HAOI）那么我就在全国赛上拼一把，争取搞一个铜牌签到浙大的一本线。如果没有进队，就体验一把APOI/CTSC彻底退役吧!纵然希望渺茫，也要做一条有梦想的咸鱼。
May/1 一道题：P1305；
May/2 一道题：P1301；
May/3 一道题：P1306；
May/4 一道题：P1512；
May/5 一道题：P1308；
May/6 休息；
May/7 休息；
May/8 三道题：P1308，P1243，P1244；
May/9 三道题：P1245；P1246；P1247；
May/10 两道题：P1227，P1241；
May/11 三道题：P1984，P1985，P1356；
May/12 四道题：P1455，P182 ...
树形DP(2)
P1305选课题目描述：
学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
输入：
输入文件的第一行包括两个整数N、M（中间用一个空格隔开），其中1≤N≤300,1≤M≤N。 以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。
输出：
第一行：只有一个数：实际所选课程的学分总数。
下面m行：从下到大所选择的课程。
题解：这道题相对于上一道题不过是多了一种选择的方案输出而已，我们在转化为二叉树的基础上，愉快的再次建立一个bool数组 ans[i] 来表示这个点 i 是否被选中，然后再次一个DFS递归，如果当前的 f[x][y]==f[Borther[x]][y] 那么我们 ...
树形DP(1)
说在前面
树形动态规划其实就是在树上进行其他的DP，不过存储由线性的一个数组变成了一个树结构，不过本质还是需要用到各种动态规划的，下面是几道题目：
P1300加分二叉树题目描述：
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
输入:
第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
输出：
tree的最高加分
tree的前序遍历
题解：其实这道题就是披着数规的皮，心是区间动态规划的心，我们需要在中序遍历的基础上进行区间动态规划就行，如果你建立一个图，就可以 ...
位运算
写在前面：
HAOI在位运算上吃了亏，无良老师乱定义运算符，害的我and当成xor进行运算，因此考完HAOI就来补位运算。
趋向于首先我列出来一个“趋向于”
1while(n-->0)
没错就是这样，我原本以为是什么位运算，结果就是自减之后判断时候是否大于某一个数。在100000000之内是略快于for的，但是超过100000000之后两者速度就相差无几了，甚至for略快于while，感觉这个东西没什么卵用（写在代码里装高端）。
位运算
其次放下来一张系统的图：
这些运算符分别叫做 and or xor not shl shr
但是 C++ 里面只能使用 and or xor 三种进行计算，其他的必须输入符号，所以以后就一直用符号计算吧，本来想的是用单词进行计算的。但是一直试到了not之后进行运算，发现not竟然是“ ！”。看来是没有办法全部使用单词计算了。
1. and运算(与运算 & )
and运算通常用于二进制的取位操作，例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数 ...
图论模板
写在前面
把所有的图论的代码都敲了一遍，以防止生疏QAQ
邻接表1234567void init(int xx,int yy,int vv)//邻接表{ a[++Len].Point=yy; a[Len].Next=Link[xx]; a[Len].Value=vv; Link[xx]=Len;}
边表123456void line_init(int xx,int yy,int vv)//边表{ a[++len].x=xx; a[len].y=y; a[len].v=vv;}
Floyd12345678void Floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}
Dijkstra1234567891011121314151617181920212223242526 ...
HAOI 2017 总结
HAOI说在前面：
昨天，2017/4/23，HAOI2017正式完结。
首先这次考试也让我再次看清楚了自己，再次看清楚了OI。
学OI就是在赌博，这句话在省选体现的淋淋尽致。
我开始有些迷茫了……
比赛经历：上午走到考试机房，的确有些累了，然后开始看题，第一题60分看起来很可行，直接上爆搜，但是实际上敲了100多行，自己构出来的几组数据都是可以过去的，当数据范围扩大到100度的时候就超时了……最后只拿到了10分。
然后其他两道题就输出了样例和while(true) cout<<“sro_centry_orz”<<endl;
下午懵逼一样的爬回去机房考试，看看题两道看起来都是可行的题目，但是老师定义了xor运算为and运算，当时我还没有学位运算，所以就傻不拉几的用起来了xor运算来计算，然后就没有然后了，明明看出来是个DP了啊……
第二题是一道字符串的题目，我想都没想直接开始暴力模拟，几重循环直接往上面开始套，结果只过了一个点。
这次考试总得来说就是拿稳暴力就是胜利，因为大家都在敲暴力（lzx等大佬除外）谁拿的暴力越稳，分数就自然越高。
这次一共20分，由于N ...
你的 bug！
写在前面写下来自己犯下的所有错误，以便以后减少程序Debug的时间……
邻接表存储的时候存下的是和这个点相邻的边，并不是一条连通的路。
用邻接表下标 i 做为其他的数组下标操作。
堆的比较方式是相反的。
第二重循环要用j ，并且千万记得不要出现声明 j却变成 i++：
在用memset的时候，头文件#include一定要加上。
用完文件输入输出，在OJ上提交程序的时候要注释掉文件输入输出。
在使用getchar()读入的时候记得将下面开启同步语句关闭：
1ios::sync_with_stdio(false);
当在递归重新声明一个数组变量的时候，数组变量不会清空，而会是你上次记录的值，需要重新归零（其实是地址还没有变化QAQ）。
递归传递数组（只在数组上面发现了）的值的时候，一旦改变，那么再返回到上一层的时候，上一层的值也会是改变的，所以最好的方法就是再次在递归当层进行声明一个数组，然后对这个数组进行赋值操作。或者是在开一维数组，把全部的都记录下来！
string类型的处理速度非常慢非常慢，如果遇到了需要用string处理，而且数据量是比较大的，那么我们就直 ...