题目链接 题意：给出n和m,初始给出1<<n个数，先相邻的两个数进行或操作（a[1]^a[2],a[3]^a[4]...），得到的新数列再相邻的两个数进行异或操作。 最后得到一个数，即为答案。现在给出m个操作，每个操作两个数p,b，表示令a[p]=b,每次变化后输出最终的结果。 思路：线段树。这道题让我学到了，线段树的数组tree[i]存储的信息可能不唯一，可以不同层存储的是不同的信息。 比如这道题中，距离叶子节点距离为奇数的点存储的是或操作的结果，距离叶子节点距离为偶数的点存储的是异或操作的结果。 还需要注意的是，build和update操作都是从顶向下，最后一个操作是异或还是或取决于n的奇偶性，记得判断。 /* …

题目链接 题意： 在二维坐标平面内进行_n_ (1 ≤ _n_ ≤ 2·105) 次操作。一共有三种类型操作。 1.add x,y 将点(x,y)加进坐标系。 2.remove x,y 将点(x,y)移除. 3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。 x,y均为非负数。以上操作均合法。 思路：没有思路。。。不会啊。。。以为要二维线段树什么的。。。。总之是不会做。。。 大概从中午开始看题解。。。8个小时。。。。终于完全搞懂了orz 很巧妙得把二维问题转化成了一维问题。。。 我来说一下大概做法，具体的细节见代码注释： 在x轴方向维护一课线段树，线段 …

poj 2828 题目链接 题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1) 现在问最后的序列，从1到n输出n个人的rp值 思路：第二道线段树，并不会做，看了题解。 比较关键的一点是：按照顺序的话，当后来的一个人插入到前面，那么之前很多人排好的位置将发生改变，这个代价是巨大的。 由于越后来的人越容易确定位置，因此正确的做法是倒序处理。 对于第i个人，我们把他放在从前往后数的第i个空的位置即可。 接下来需要做的就是线段树处理，线段树存储的信息是某一个区间中空位置的个数。 感觉是一道很好的题目，对于新手来说并不是很容易， …

题目链接 题意：找两个不相交点集使得对于每一条边至少有一个顶点在点集中 思路：判断能否构成二分图。染色即可。 需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333. /* *********************************************** Author :111qqz Created Time :2016年09月03日 星期六 01时04分40秒 File Name :code/hdu/687A.cpp ************************************************ */ #include <cstdio> #include …

题目链接：题目链接 题意：给出一个无向图，该图是通过仅包含‘a’ 'b' 'c'三个字母，以规则“i,j之间有边，当且仅当s[i]和s[j]相同，或者s[i]和s[j]在字母表中相邻”（也就是只有'a'和'c'是没有边相连的）得到的，现在问能否还原这个字符串，如果能，输出任意一个解。 思路：其实就是简单构造。。。 构造的一个技巧是。。把能确定的地方先确定了。。。。 我们发现'b'比较特殊。。因为b和任意点都相连。。。 于是可以统计一下度。。。然后确定字符串中的b 然后对于某个没有确定的位置，我放置一个a,并且把所有和这个位置相连的都放成a 字符串中剩下的没有确定的位置就一定是c了。 这个时候我再判断是否满足题中图的条件。 /* …

题目链接：hdu 5285 题目lianjie 题意：给定n个小朋友，以及小朋友之间的关系，要求将小朋友分成两组，**并且每组至少一个人，**现在问能否这样分组，如果有解，输出两组的人数，并保证第一组的人数尽可能地大。 思路：。。。一开始看到n的数据范围。。。想当然的以为会给认识的人的关系。。。尼玛。。。求个补图就够受的了。。。。不会做，卒。 结果发现。。竟然给的是两个人不认识的关系。。。2333 那么我们来交叉染色。。。 实际上交叉染色的过程中，颜色相同的点属于二分图中相同的点集合。 交叉染色其实是在模拟交错轨的过程...？ 由于图不一定联通，可能由多个联通块。 我们在交叉染色的时候记录一下0,1的个数（也就是两个点集的大小） 然 …

hdu 5215 思路:询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以由相同的点，不能有相同的边） 思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。 感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的，不同的环之间由相同的点的情况。 比如这组数据： 5 6 1 2 2 3 3 1 1 4 4 5 5 1 两个三元环扣在一起。 实际上是既有奇数环，又有偶数环的。 但是按照我的做法，由于每次只去染没有染过的点，无法发现偶数环。 因此正解是增加一步回溯，这样使得之前存在与某个环中的点还可以出现在其他环中。 然而这样复杂度会 …

hdu 2444题目链接 题意：判断一个有向图是否是二分图，是的话求最大匹配数。 思路：交叉染色判二分图，是的话跑遍匈牙利即可。1A. /* *********************************************** Author :111qqz Created Time :2016年09月01日 星期四 14时24分36秒 File Name :code/hdu/2444.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu 4751 题目链接 题意：n个人，给出每个人认识的人的信息。问能否将这些人分成两组，保证每组至少1个人，并且两两互相认识。 思路：首先是反向建图。由于要求同组内两个人互相认识，那么两个人u,v，只要u不认识v或者v不认识有一个满足，就连接双向边u,v，表示u,v不能分到同一组。 由于图反向以后不保证联通，因此求补图以后可能会得到几个联通分量。 而合法的条件是，每个联通分量都合法。 不合法的条件是，只要由一个联通分量不合法。 以及：之前把交叉染色部分写错了。上道题可以通过纯粹是因为数据水。。？ /* *********************************************** Author :111qqz …

uva10004题目链接 题意：给出一个无向图，问是否可以组成二分图。 思路：交叉染色法。 **首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:** **　1.未染色 那么继续染色此节点(染色为另一种颜色)** **　2.已染色但和当前节点颜色不同 跳过该点** **　3.已染色并且和当前节点颜色相同 返回失败(该图不是二分图)** 学习链接 upd:更正dfs中的一个错误。 把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false; 之前的写法中，当前层之后的层的没有起到任何作用。。。 而实际上应该是后面只要某一层不满足，整体就该为false. 写成这样这题还能过我也是醉了。。。。 /* …