题意：

给出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

map <F5> :call Co()<CR>
func! Co()
    exec "w"
    exec "!g++ % -std=gnu++11 -Wall -o %<"
    exec "! ./%<"

endfunc
syntax on
set nu

 1autocmd BufNewFile *.cpp  exec ":call SetTitle()"
 2func SetTitle()
 3    let l = 0
 4    let l = l + 1 | …

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

环节长度。

原理见广义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]的值，改变后，程序还能针对改