1.  http://acm.pku.edu.cn/JudgeOnline/problem?id=3207
题意:在一个圆圈上顺时针或逆时针排好N个点(0-->N-1),现在要以给定的M组端点画M条曲线段,曲线段可在圆内或圆外,判断是否存在一种画法使得这M条曲线段不相交。
分析:每一条曲线段可置于圆内或圆外。这样可用两个顶点分别表示曲线段的摆放情况,例如(顶点2*i表示第i条曲线段置于圆内,顶点2*i+1表示第i条曲线段置于圆外)。
这样对于如下图的两条曲线段 seg[i]=[a,b],seg[j]= [c,d],seg[i]和seg[j]是不能都置于园内,或都置于圆外的。所以顶点2*i和顶点2*j+1,顶点2*j和顶点2*i+1的真值情况必然相同。
                                                                                       
【顺时距离==>用于判断圆内曲线段是否相交】
对于圆内判断是否相交可以这样:如果在a顺时到达b的过程中经过并且只经过了c,d中的一点,那么seg[a,b]和seg[c,d]必然相交。定义顺时距dist[a,b]为a顺时到达b所经过的距离(这个距离可以有几种形式),那么如果 dist[a,c]+dist[c,b]==dist[a,b] 则 “c 在a,b内”,这样如果 c,d中有且只有一点在a,b内,那么seg[a,b]和seg[c,d]必然相交。
POJ_3207

另外此题是判定能否将曲线段划分到两个集合中。可以用并查集来写

POJ_3207


2. http://acm.hdu.edu.cn/showproblem.php?pid=3622 (二分答案+2-sat判定)
HDU_3622_Bomb_Game
 
3. http://acm.pku.edu.cn/JudgeOnline/problem?id=2723
 二分答案 + 2-sat判定。
最开始我构图不够严谨,只是以用了某个钥匙为顶点。然后判断是不是用了某两个属于同一组的钥匙从而判断是否有解。
其实这样是不够的,因为有解的话并不一定要从同一组钥匙中选一个。所以这样转化成2-sat是不行的,应该将用第i类钥匙和不用第i类钥匙作为图的 p 和 ¬p顶点,这样p和¬p必选其一。

POJ_2723_Get_Luffy_Out

4. http://acm.pku.edu.cn/JudgeOnline/problem?id=2749
 (二分+ 2SAT)
牛i 连S1和S2分别为顶点Pi 和¬Pi之后二分就行 (第一次WA后发现没用memcpy将信息备份那个nedge一直在增加,第二次WA后发现竟然将enemy和friend的输入顺序搞反了,太没素质了。悲剧)。
POJ_2749_Building roads