今天讲了并查集、堆和Hash表，并讲了几道比较难的题.

例1.

分析：其实这道题我们用一颗很普通的线段树，维护区间最大值就好了，因为最大值开方后还是最大值嘛.

但是开方有一个比较重要的性质：一个10^7的数大概7,8次开方就是1了，以后不管怎么开方都是1，我们能不能不考虑这部分1呢？也就是说，我们能不能用一个数据结构跳过1呢？可以想到用双向链表，但是这样能不能做到线性呢？回想一下链表的操作，我们的第一步是要“找到”链表，也就是说我们要找到当前区间的第一个不是1的表头，这样其实很容易卡掉，考虑一组数据：21111112，如果我们当前处理的区间是[2,6],那么我们要寻找整个区间，复杂度O(nq),通不过所有测试点，能不能有一个数据结构，当我们处理到某个点时，能够跳到下一个非1的点呢？我们考虑这样做：

如果这个点非1，那么就自己指向自己，否则指向下一个点，直到遇到自环，有没有感觉非常像并查集？

其实我们只需要路径压缩一下，复杂度O(nlogn)。

   这样我们得到了做法：利用并查集暴力枚举每一个非1的数来修改，在修改的同时维护区间最值，最后利用线段树来查询.

例2：传送门

例3：

分析：这道题目的意思是如果u,v的路径只有1种颜色，那么这种颜色的边能联通u,v.我们可以把每个颜色的边给“抽"出来，单独建一个图，然后利用并查集维护连通性，但是如果对于每个图都开一个数组，会有点炸内存啊，10^9的数组可不是说开就能开的，那么怎么做呢？其实可以发现有很多点是孤立的，我们把这些点给排除掉，最后剩下大概2m个点，可是这些点也很多啊，我们能怎么办呢？hash!

     因为我们用f[i][j]记录第i个图j的祖先嘛，我们可以用pair+map完美解决，也可以把i和j拼成一个字符串然后用字符串hash，解决一下hash碰撞就好了。

例4：

分析：这道题可以模拟，但是没啥用，因为过不了题......但是因为小球不标号，我们可以这么想：两个小球发生碰撞和两个小球对穿而过是等价的，于是每个球的答案就是xi + vi*t.

例5：

这个题意是错的，原题目为有标号的小球

分析：先看前一组数据，考虑模拟，两个小球相碰撞的情况是方向相反且距离最近，我们把每两队小球碰撞的时间放进一个优先队列，每次处理时间最短的那一个，那么其它的几对小球相撞的时间就要减去第一队所花的时间，还要把新的相撞的小球对放进优先队列里，不过给每一个元素加上这个时间复杂度实在是太高了，我们可以考虑noip蚯蚓那道题的做法：我们把不需要处理的数加上我们原本要减去的数就好了，用一个变量记录我们到底要减去多少，到时候减回来就好了，这是第一组数据的做法.

     考虑第二组数据，我们利用例4的做法，我们先给每个小球以坐标大小为依据来编个序号，可以发现，最后下来，这个序号还是这个顺序，也就是说，一开始这个小球是第几个，那么之后他还是第几个，利用这个性质再利用例4的结论，就能A掉此题.

例6：传送门

例7：

分析：因为断言没有矛盾，所以不可能出现一个好人或者坏人说自己是坏人的情况。我们现在考虑几种情况：1.如果A说B是好人，A是好人，那么B是好人。2.如果A说B是好人，A是坏人，那么B是坏人。3.如果A说B是坏人，A是坏人，那么B是好人。4.如果A说B是坏人，A是好人，那么B是坏人。可以看出：如果A说B是好人，不管A是什么，AB都是同类的，如果A说B是坏人，那么两人不同类。那么我们可以利用noip2010关押罪犯的处理方式来用并查集存和自己同一类的，不同类的人。

     现在来建图，如果A和B是同类，则从A向B连一条权值为1的无向边，否则连权值为0的，这样我们确定一个起点就能够推出整个连通块的好人坏人数量，有两种可能:(a,b),(b,a).

     但是有多个连通块，每个连通块有两种可能，我们要怎么合并答案呢？这个其实非常像背包啊，每个可以取第一个或者取第二个，我们考虑好人的数量，设f[i][j]表示前i个连通块中，有j个好人的方案数，因为有两种组合，可以得到f[i][j] = f[i-1][j - a[i]] + f[i-1][j - b[i]],看最后f[n][p1]是不是等于1就可以了。

     因为只用涉及到01运算，所以可以用bool数组优化计算.

例8：

分析：这道题题的题意就是如果u和v只用1条边就连通，那么|xu-xv|就必须≤1,否则就必须≥1

     看上去似乎非常难以分析得到答案，我们从最简单的情况来分析：

     1.两个点，这个直接弄就好了。

     2.三个点，这个有很多方法，比如112,221什么的。

     3.四个点：

会发现无论怎么样都不能满足要求，但是如果我们在中间加上一笔：

可以发现最左边和最右边填1，上面填2，下面填0就能满足要求，现在我们思考一下，为什么左边和右边的能填成一样的？可以发现，这两个点所连上的点加上自己的集合相等，而上下两个不相等.为什么会这样呢？因为这个集合里保存的都是直接与自己相连的，都满足限制|xu-xv|≤1,如果两个集合不相等，那么就有点不在某个集合内，这个数值就必须要改变。

   根据这个性质，我们可以把两个填相同数值的点合并成一个点,可能会出现这样的情况：

然后我们可以发现，下面的点还可以继续合并，这就与之前的合并矛盾了，所以如果图中存在度数大于等于3的点，那么一定是无解的.

   那么接下来就只有两种可能了：环或者链，合并后环是不可能出现的，因为可以继续合并成1个点，那么只有链了，从头到尾依次填0,1,2,3,...,n即可，不过注意我们操作的是合并后的点，记得一定要还原.

2017.8.11 数据结构课小结