【算法分析】
以(x0,y0)为起点向x轴正方向作一水平射线，如果中间穿过奇数个多边形上的点，应该是在多边形内，否则应该是在多边形外。
但是有不少特殊情况。
WA了好多次，找了下资料，原来遵循下面几个原则即可：
1对于多边形的水平边不作考虑；
2对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；
3对于P在多边形边上的情形，直接可判断P属于多边形
【CODE】http://xiudaima.appspot.com/code/detail/3434005
分类存档：默认分类
[SGU121 Bridges painting]【构造法】
【题目大意】
给定一个无向图，把每条边黑白染色，使得所有的度大于等于2的点有至少有一条黑边和一条白边相连。
【算法分析】
很久之前写过随机算法过了，现在贴一个构造法的。
其实主要是update函数非常精髓。
首先构建dfs树，无向图dfs树具有的一大优点是该点只会向自己的祖先或子孙有非树边。
然后按深度交替染色。返祖边与自己的儿子涂同样的颜色。
如果dfs树中根结点度超过1，那么就找一条边染不同的颜色。
否则看根结点是否满足条件，如果不是，那么找一个与根结点相连的叶子，向上找到一个度大于2的点为止，将该路径上所以边反色，并且将根与该叶子的边反色。如果找不到度大于2的点，那么是奇环，无解。
【CODE】
C++ CODE :SGU121 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99100101 #include
NOIP2010提高组解题报告——Flow
【题目大意】
给定一个N*M(N,M<=500)的矩阵，矩阵中每一个格子都有一个权值。
1、只有第一行的格子能够建蓄水厂。
2、若与该格子有公共边的格子已经建有水利设施，并且这个建有水利设施的格子的权值大于该格子的权值，那么该格子可以建一个输水站。
问：能否使最后一行所有的点都建上水利设施？若能，则输出最少建多少个蓄水厂可以达到要求。若不能，则输出最后一行有多少个格子无法建立水利设施。
【算法分析】
首先注意到两个性质。
1、假设i,j都为第一行建蓄水厂的位置，那么他们供给最后一行的水利设施的配对关系可以不交叉。
如图：
若交叉，那么i必然能控制j现在控制的点。于是反证得该性质正确。
2、假设最后一行的每个点都能被覆盖，那么对于第一行的每一个结点，它所能控制最后一行的位置必然是连续的。
如图：
若不连续，根据性质1可知，其它点也无法覆盖红色部分，于是与“有解”这一前提矛盾，反证得该性质正确。
得出这两个性质以后解法就呼之欲出了。
首先把所有第一行的结点放入队列之中，进行广度优先搜索，然后可以看最后一行有多少个点被扩展到，从而得出是否有解以及有多少个点无法被覆盖到。
下面处理有解的情况。
对于每一个点，建立两个项L[i][j],R[i][j]，表示从这个点流出去，能覆盖到最后一行的最左端点及最右端点。
那么怎么快速处理得出所有点的L[i][j]及R[i][j]呢？
我们初始化所有L[N][i]=i , R[N][i]=i。
然后扩展开去影响其他的点。
笔者认为扩展有两类比较好的方法：
1、这个过程比较类似于最短路的扩展，所以SPFA或者Dijkstra+Heap都是不错的选择。使用它们的时间复杂度分别是O(kNM)、O(NM lg NM)
2、这个图显然是有向无环图，我们可以对它拓扑排序，然后按拓扑序扩展。这样做的时间复杂度O(NM)。或者说更直接一点按所有点的权值排序，然后按权值从小到大的顺序扩展。这样做的时间复杂度是O(NM lg NM)。
处理出所有的L[i][j]以及R[i][j]以后，问题就转化为：用最少的第一行的区间覆盖[1,M]这段所有的点。
令L’[i]=L[1][i]，R’[i]=R[1][i]。
我们按L’[i]把第一行的区间排序以后，就可以使用一个简单的贪心算法在O(M)的复杂度内解决这个问题。
这个贪心的C++代码如下，其中Q[i].L等价于L’[i],Q[i].R等价于R’[i]：
int MaxR=0,ans=0,tmp;
i=1;
while (MaxR tmp=MaxR; while (i<=m && Q[i].L<=MaxR+1) tmp=max(tmp,Q[i++].R); MaxR=tmp; ans++; } printf("%dn",ans); 【复杂度分析】 综上，我们如果在扩展时使用拓扑排序，那么可以做到 O(NM+M lg M)的时间复杂度 (这已经和读入数据所必须耗费的时间差不多了) O(NM )的空间复杂度
NOIP2010提高组解题报告——Prison
【题目大意】
给定一个无向图。
我们用三个值来描述一条边：Edge.w(该边的权值),Edge.x,Edge.y(该边所相连的两个顶点)。
现需要把该图里的点分在两个集合A,B中。
令Weight_A=Max(Edge.w | Edge.x∈A，Edge.y∈A)
令Weight_B=Max(Edge.w | Edge.x∈B, Edge.y∈B)
则Answer=Max(Weight_A,Weight_B)
问Answer最小能是多少？
【算法分析】
本题有两种思路。
【算法一】
先二分答案，然后单独地判定可行性。
注意到二分答案Limit以后，使用所有Edge.w>Limit的边构成一个新图。然后这个可行性问题可以转化为：判定该新图是否一个二分图。
对于这个问题，我们可以通过对每个点黑白染色来判定。
染色过程如下：
使用广度优先搜索或者深度优先搜索遍历全图，对于一个连通分量，先对其中一个点染上白色。然后再将与它相邻的点都染成和该点相反的颜色。如此下去，不同连通分量分别处理，最后得到一个所有顶点都经过染色的图。然后检测是否存在一条边所连接的两个顶点颜色相同，若是，则不可行，否则可行。
【时间复杂度】O(V lg 10^9+E lg 10^9)
【空间复杂度】O(V+E)
【算法二】
注意到答案一定是某条边的权值，那么我们把边按权值从大到小排序，然后枚举答案，并考虑答案的改变，情况会发生什么变化。
答案每次减少一点，就会加入几条边，我们现在要在线判定新加边以后，该图是否还是二分图。那么我们用并查集维护每个连通分量，利用该点到并查集中根的距离判定染白色还是黑色。然后如果新加入一条边，连接同一连通块的两点并且他们到根的奇偶性相同，那么出现矛盾，不可行。否则，合并两个集合。
【时间复杂度】O(E lg E + V α(V))
【空间复杂度】O(V+E)
NOIP2010提高组解题报告——Tortoise
【题目大意】
给定N(1<=N<=350)个排在一行的格子，每个格子上都有一个权值。同时给出M(1<=M<=120)张卡片，每张卡片上有[1,4]中的一个数字。一开始游戏者站在第一个格子处，每使用一张写着数字x的卡片，那么向后跳x步，并得到该格子上的权值。卡片不可重复使用。数据保证每种卡片的数量不超过40，并且所有卡片上的数字之和与N-1相等。
【算法分析】
本题很容易使用动态规划解决，而且可以通过所有数据的状态定义也有很多种。由于转移都比较简单，并且几乎都一样思路，所以转移方程在此略去。
【算法一】
F[i][j][k][l]表示写着数字1、2、3、4的卡片分别剩下i、j、k、l张时的最大得分。
(可以使用n-(i*1+j*2+k*3+l*4)来得知当前到达哪一个格子)
【时间复杂度】
O(41^4+N+M)
【空间复杂度】
O(41^4+N+M)
【算法二】
F[i][j][k][l]表示跳到了第i个格子，写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。
(可以使用n-i-j*2-k*3-l*4来得知1号牌剩下多少张)
【时间复杂度】
O(N*41^3+N+M)
【空间复杂度】
O(N*41^3+N+M)
【算法三】
F[i][j][k][l]表示剩下i张牌可用，写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。
(可以使用i-j-k-l得知1号牌剩下多少张)
【时间复杂度】
O(M*41^3+N+M)
【空间复杂度】
O(M*41^3+N+M)