codeforces #346 div 2 E. New Reform (和图有关的的计数)

题意:

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

思路:

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

Read more

codeforces 439 C – The Intriguing Obsession (和图有关的计数,组合数学)

题意:

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

思路:

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

那么其实,对于每一对岛屿群,是相互独立的。[……]

Read more

codeforces # 440 div2 E. Points, Lines and Ready-made Titles (和图有关的计数,思维题)

题目链接

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

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

思路:

参考题解

好菜啊不会做,转载一段题解。

bzoj 1854的并查集思路蜜汁契合 // 看[……]

Read more

hdu 2157 How many ways?? (矩阵快速幂经典题目)

题意:给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值

思路:
 把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k[……]

Read more

codeforces 560 E. Gerald and Giant Chess (dp+lucas定理,求大组合数 mod p,p为质数)

dp方程想错了.果然还是欠练啊.

如果我们不考虑坏点,那么从 (0,0)到(x,y)的方案数是c(x+y,x)或者c(x+y,y)

因为有坏点的存在,我们可以逆向思维,先求出总数,然后减去那些由于坏点的影响不能走的方案数.

由于存在黑点i(x,y),从左上到该黑点的方案数sum[i[……]

Read more