题意：

给出n个点m条边，以及已知的好点和坏点。一个边连接的2个点一定是一好一坏，问是否有合法方案，使得每个点被确定好坏。

思路：

判断二分图。

先染已知的，再染未知的。

题意：

给出n个点，条边的无向图，无重边，无自环。现在要求把所有的无向边换成有向边，使得入度为0的点最少。问最少的入度为0的点是多少。

思路：

对于每个联通快，如果有环，我们可以顺时针连接环上的点，以指向环的方向连接联通快上的其他点，这样就可以保证所有点的入度都不为0. 如果是树形结构，则不可避免得使得一个点的入度为0.

Description

lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？

题意：

3个岛屿群，每个岛屿群有若干岛屿。现在要在岛屿之间连桥，桥的长度是1，规定2个属于相同岛屿群的岛屿的距离要大于等于3.

思路：

一直在纠结大于等于3的距离的事情。。。其实这句话等价于，同一个岛屿，对于另外两个岛屿群，都最多只能连接1个岛屿。

题目链接

题意：有n个整点，每个点处可以什么都不画，或者画一条垂直方向的直线，或者画一条水平方向的直线。

现在给出n个点的坐标，问最多右多少种不同的图案。(只要有一处不同，就认为两个不同）

弄了点比较短的，赛场上用的配置文件orz

 1map <F5> :call Co()<CR>
 2func! Co()
 3    exec "w"
 4    exec "!g++ % -std=gnu++11 -Wall -o %<"
 5    exec "! ./%<"
 6
 7endfunc
 8syntax on
 9set nu
10
11autocmd BufNewFile *.cpp  exec ":call SetTitle()"
12func SetTitle()
13    let l = 0
14 …

**问题：**给定 ，满足 ，求 的循

环节长度。

原理见广义Fibonacci数列找循环节

这里只说做法

我们先写出递推式的特征式子   x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b

起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭

可持久化线段树的本质是很多棵形态完全相同的线段树。

也可以理解成是，保存了不同时刻版本的线段树的数据结构。

题目链接

题意：

给定一个序列 n，有 m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。

思路：

先分解一下问题，我们要求一段区间位置的中位数，其实可以分解成，求区间中不同数的个数+求区间中第k大的下标。

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1

],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改

题意：

求区间第k大数

思路：

可持久化线段树。

其实这东西在国内更常见的名字应该是 zhu xi 树？应该是由于“中国高端数据结构领导者”的hjt比较早得引入（？推广？）而得来的。

题目链接

题意：

给定二维平面的n个点，要求一个面积最小的正方形，使其能覆盖所有的点。

思路：

先考虑如果水平竖直地放置正方形（边和坐标轴平行）圈住所有点的最小正方形的边长是:

题目链接

题意：

有n个点，表示n个圆的圆心，问一组圆的半径，满足相邻(i,i+1)或者(n,1) 圆相外切。

思路：

我们发现确定第一个半径之后，其他的圆的半径似乎能解出来？

题意：

给定一个 N∗N(N≤4e9) 的矩阵，现在经过这样一个变换：将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0≤x<N,0≤y<N) 现在求经过多少次这样的变换之后在回到 N∗N 的原始矩阵。

题意：

有一棵树，水源在根节点1，房子在叶子节点。有若干操作，操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水，可以通过切断边实现（如果某个叶子节点到根节点的路径上有一条边被切掉，那么就不能供水了。）对于每次操作后，问不给所有歹徒供水最少要切多少条边，并且问在切满足前面最小的情况下，最少使得多少个良民受影响。初始没有歹徒。

题目链接

题意：

在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。

题目链接

题意&思路：

给出n个圆

求恰好k个圆相交的面积，k属于1..n

先放个别人的代码。。。

我真是体会到了。。。软件工程这门课的重要性。。。

这代码真是烂得印象深刻。。。几何题全是面向过程？

题目链接

题意：

多n个圆的面积并。

思路：

发现和求2个圆的完全不一样，具体请参考

SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU）

圆的面积并 

格林公式在面积并问题中的应用

（用格林公式搞真是跪烂了。。。。

题目链接

题意:

If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1

问每个point的level是多少。

思路：

cdq分治，先去重并统计相同的点的数量，需要注意要记录原id对应到了哪个新id

Description

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。