题意：给n个正方形分子，分子的边在一定条件下可以结合，求这些分子能不能形成无穷大的结构。
我们从分子的某条边开始铺，假设从下图中的边K+开始铺。K+与K-相结合，再下一步，可以从C-、D+、D+边铺。假设D+与D-相结合后，结合的分子有一条边为K+，那么下一步可以从此K+边开始。问题又回到了起点，按照与之前相同的选择，可以不断重复而组合成无穷大的结构。也就是说，如果从某条边开始，不断地铺，能够到达一条跟它有相同标号的边，那么能够形成无穷大的结构；否则，不能够形成。
考虑以图来建模，把标号作为结点，结点的数目最多有26*2个（不考虑00，因为00不可能在有向圈上）。假设正方形的四条边的标号分别为abcd，记dual(a)表示可以和标号a相结合的标号（如K+和K-可以结合），那么dual(a)可以到达b，dual(b)可以到达a…。问题转化为了找有向图中是否存在有向圈，用拓扑排序可以做。
PS：把dual函数修改了后从50ms到了40ms，rank top 了…
题意：给定一个n个顶点m条边的无向图，图中可能有多重边和自环。求顶点1到顶点n最少需要经过的边数，并且输出字典序最小的边的颜色序列。
从顶点1到顶点n的最少边数可以通过BFS求得，关键是字典序最小的颜色序列。想到的做法是，从顶点n到顶点1进行BFS，得到每个顶点与顶点n的距离。之后，想象按照距离把图分层，然后从顶点1开始，每往下走一层，都选择颜色值最小的边。
若是从顶点1到顶点n进行BFS，之后再按照到顶点1的距离分层，在往下一层走时，假设某条边e(u,v)的颜色值最小，我们选择了边e，但是顶点v到顶点n可能需要（比最少边数）更多的边数！
一个坑：因为图中存在多重边，假设我们从顶点u往下一层走时，选择的最小颜色值与边e(u,v)相同，且有3000条颜色值相同的边e(u,v)，那么结点v要入队（这里使用队列维护）3000次！因此，需要保证入队一次，不然空间和时间都会爆炸😄。
题意：给定n个长方体，求这些长方体组合成的物体的表面积和体积。想象组合后的几何体完全浸泡在水中，所求的即为几何体与水接触的面积以及所占据的体积。
可以考虑在坐标系中一个点一个点填充几何体，然后DFS标记出“水区域”。这样，与“水区域”接触的几何体的面积即为所求的表面积，非“水区域”的体积即为所求的体积。因为所给的坐标范围比较大，但n的范围比较小，需要对坐标进行离散化处理。
离散化的一些细节：若所给区间为[x,y]，S为所有坐标点排序后的数组，考虑下面两种：
拓扑排序的模板题，主要是来学习一下用DFS来判断是否有环，以及输出拓扑排序的序列。用DFS进行拓扑排序需要借助一个标记c[v]，c[v]=0表示图中的结点未被访问过，c[v]=1表示正在访问结点（及其后继），c[v]=2表示结点访问完成。（当然，也可以设置为其他有相同含义的不同的数值。）
有向图中存在环，当且仅当访问到一个结点v有c[v]=1。证：设当前正在访问结点u，其直接后继v满足c[v]=1，那么一定存在一条从v到u的路径，又存在有向边(u,v)，则图中存在环。若c[v]!=1，那么不存在从v到u的路径，也就没有环。
另一种比较熟悉的做法是不断从图中删去入度为0的结点，并把其加入拓扑序列。如果图中剩余的所有结点都不满足入度为0，则说明图中存在环。
题意：给定一个黑白图片的16进制表示，识别出图片中包含的象形文字。
首先需要把十六进制表示转化为二进制表示。因为每个象形文字的黑色像素是连通的，所以黑色像素的连通分量的数目即为象形文字的数目。各象形文字可以用其包含的白色区域的数目来区别。想到的做法是，dfs填充白色像素区域，并返回区域的边界：0 表示没有边界（边界都是白色像素），1,2,3… 表示边界是对应的黑色连通分量，-1 表示边界是整个图像的边界。若边界是黑色像素，则对应的黑色连通分量包含的白色区域数+1。这样，即可区分出不同的象形文字。
一个想错的地方是，认为返回的区域边界不会为0。想象这样一种情况，一个白色像素其周围的三个白色像素都已经遍历到，则返回0。而这种情况是有可能的。
紫书中的做法是增加了白色边界，方便处理；从黑色区域找与其相连的白色区域。
题意：给定两个四分树的先序遍历序列，四分树的每个结点与图像的某个区域对应，求两个图像合并后黑色像素的数目。
想到的做法是同时遍历两个四分树，在遍历的过程中遇到p结点则向下；如果两个结点都不是p结点且其中一个为f结点，则加上对应区域的像素数目。
紫书中的解法是考虑四分树对应的图像。一个学到的地方是（正方形）区域的表示：区域的左上角坐标(x,y)以及区域的宽度w。这样，在表示四分区域时非常方便。
题意：给N个数，进行两种操作：1.0 X Y对第X和第Y个数之间的数开根号；2.1 X Y对
第X和第Y个数之间的数求和。
开根号操作需要对区间内的每个数进行，才能使得区间的和得到更新。
没有想到的地方在于，\(2^{64}\)恰好需要开7次根号变为1，一个小于\(2^{63}\)的数最多开6次根号会变为1（如果最初的数>0)，之后再开根号数值不会变化。
因此，可以得到的解法是，更新操作更新到叶结点，并记录线段树结点开根号的次数，如果次数>=6，则不再向下更新。也就是说，开始的时候每次更新都会更新到叶结点，复杂度为\(O(n)\)，对整个区间更新6次后，复杂度变为\(O(logn)\).interesting…
POJ 3253 Huffman树
错误：结果超出了int的范围，应该用long long；而且printf("%lld",ans)，注意是lld
POJ 2686 Traveling by Stagecoach（DAG，状压dp）
题目大意：m个结点的无向图，每个结点表示一个城市，n张票，经过一条边消耗一张票，每张票有一个数值，经过一条边的时间为边的长度/票的数值。给定起点a，问终点b是否可达，若可达，求最短时间。
用搜索来做，在结点v，有k张票，每条边用k张票去试。这样可以重新建一张有向图，图中结点表示状态，即所在城市+手中余票，边表示原来边的长度/所用票的数值。问题转化为了从起点到终点的最短路问题。这个有向图呢，是一个DAG，因此可考虑用dp来求最短路，把票的状态压缩成一个整数T，相当于填一张T*m的表。
POJ 3734，3233 （dp，矩阵快幂）
POJ 2932 平面扫描（line sweep）
POJ 2187 Graham凸包，旋转卡壳求凸多边形直径（最远点对）
POJ 1741 树的点分治
POJ 3264 RMQ问题，sparse table or segment tree
题意：一个0\1序列，初始为全1，会把某个点从0变1，或从1变为0，求包含x的最长全1序列长度。
开始想到的解法是：求包含x的最长全1序列长度，那么从x向左找到第一个0的位置，从x向右找到第一个0，这中间的即为所求序列。因此，线段树的每个结点需要维护的信息为mi[k],mx[k]，即最左0和最右0的位置。每次查询时求出[1,x+1)区间中最右的0和[x+1,n+1)区间中最左的0的位置，两者之间元素的数目即为所求长度。