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

题意:

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

思路:

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

因此对于有环的联通块答案为0,没环的答案为1.

 

 

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

题意:

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

思路:

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

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

对于任意一对岛屿群,设两边岛屿的数量分别为a,b

我们可以从两边各取0个,1个,最多取min(a,b)

需要注意的是,选取了端点之后有顺序的区别。

所以对于该对岛屿,答案是SUM{C[a][k] * C[b][k] * k!}   (k属于0..min(a,b) )

对于其他 两对同理。

 

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

题目链接

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

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

思路:

参考题解

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

bzoj 1854的并查集思路蜜汁契合 // 看完了题解的我这样想道

首先显然可以将图分为若干个联通块。

且慢,哪里来的图? 那就先考虑建图? 不急不急,先来想想看每一个联通块的性质。

如果该联通块中有环的话,肯定每条边都能取到;如果联通块是一棵树,那么必有一条边取不到(具体阐述见上bzoj 1854),所以只需要知道

  1. 这个联通块中有多少条边
  2. 这个联通块是不是环

这两个信息就可以了

那么可以直接上并查集。

什么样的点可以并到一起呢?横坐标相同的或者纵坐标相同的。

有没有环怎么维护呢?看有没有加进去的边的端点本身就在一个集合里。

联通块中边的数目又怎么知道呢?这倒还挺有意思的,其实只要直接看出现过多少个横坐标或者纵坐标就可以了,因为一个横坐标或者一个纵坐标就代表一条可以选的直线,所以这块联通块的贡献就是2^(x+y)者2^(x+y)-1

然后呢?就做完了。

然而呢?比赛结束。一天了。

相关并且有趣的题目:bzoj1854
codeforces #346 div2

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为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要快速幂求出A^k即可。

M67_十个利用矩阵乘法解决的经典题目

这个转化好美啊。。。

 

 

 

whust2016 warm up A ||codeforces 682 A. Alyona and Numbers (计数问题,水)

cf682A题目链接

 

题意:两个数组,分别为1..n和1..m。。。从两个数组中各取一个,问和能被5整除的方案数。。。

思路:傻逼题。。。统计%5。。。然后乘法原理。。

 

 

BZOJ 1632: [Usaco2007 Feb]Lilypad Pond (BFS,dp)

1632: [Usaco2007 Feb]Lilypad Pond

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 496  Solved: 153
[Submit][Status][Discuss]

Description

Farmer John 建造了一个美丽的池塘,用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有惊人的坚固的莲花,还有一些岩石,其余的只是美丽,纯净,湛蓝的水。 贝茜正在练习芭蕾舞,她从一个莲花跳跃到另一个莲花,当前位于一个莲花。她希望在莲花上一个一个的跳,目标是另一个给定莲花。她能跳既不入水,也不到一个岩石上。 令门外汉惊讶的是,贝茜的每次的跳跃像中国象棋的马一样:横向移动1,纵向移动2,或纵向移动1,横向移动2。贝茜有时可能会有多达8个选择的跳跃。 Farmer John 在观察贝茜的芭蕾舞联系,他意识到有时候贝茜有可能跳不到她想去的目的地,因为路上有些地方没有莲花。于是他想要添加几个莲花使贝茜能够完成任务。一贯节俭的Farmer John想添加最少数量的莲花。当然,莲花不能放在石头上。 请帮助Farmer John确定必须要添加的莲花的最少数量。在添加的莲花最少基础上,算出贝茜从起始点跳到目标点需要的最少的步数。最后,还要算出满足添加的莲花的最少数量时,跳跃最少步数的跳跃路径的条数。

Input

第 1 行: 两个整数 M , N

第 2..M + 1 行:第 i + 1 行,第 i + 1 行 有 N 个整数,表示该位置的状态: 0 为水; 1 为莲花; 2 为岩石; 3 为贝茜开始的位置; 4 为贝茜要去的目标位置.

Output

第 1 行: 一个整数: 需要添加的最少的莲花数. 如果无论如何贝茜也无法跳到,输出 -1.

第 2 行: 一个整数: 在添加的莲花最少基础上,贝茜从起始点跳到目标点需要的最少的步数。如果第1行输出-1,这行不输出。 第 3 行: 一个整数: 添加的莲花的最少数量时,跳跃步数为第2行输出的值的跳跃路径的条数 如果第1行输出-1,这行不输出。

Sample Input

4 8
0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 1
0 0 0 0 0 4 0 0
3 0 0 0 0 0 1 0

Sample Output

2
6
2

输出说明

至少要添加2朵莲花,放在了’x’的位置。

0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
0 x 0 0 0 2 0 1 0 0 0 0 0 2 0 1
0 0 0 0 x 4 0 0 0 0 x 0 x 4 0 0
3 0 0 0 0 0 1 0 3 0 0 0 0 0 1 0
贝茜至少要条6步,有以下两种方案

0 0 0 C 0 0 0 0 0 0 0 C 0 0 0 0
0 B 0 0 0 2 0 F 0 0 0 0 0 2 0 F
0 0 0 0 D G 0 0 0 0 B 0 D G 0 0
A 0 0 0 0 0 E 0 A 0 0 0 0 0 E 0

题意;一个n*m的maze,0是空,1是荷花,2是石头,出发地是3,每次跳象棋的马字步,只能走在荷花上,但是可以在水上添加荷花,问从3到4,在添加荷花数最少的前提下,添加的荷花数是多少,最少的步数是多少,以及在前面两个最少的前提下,有多少种路径。
思路:前两个好搞。。最后一个路径数难住我了。。没有写过这种。。一开始是想在bfs或者dfs一遍找路径,但是可能不同路径会经过相同的点,所以vis的标记会是个问题。。回溯呢。。?反正我是没搞出来。。
正解是用到了类似dp的思想。。具体可以看代码。
以及:一开始我是想添加一些节点的信息到结构体里。。但是发现那样写起来会很麻烦。。
所以这道题最好再开几个数组存储节点的额外信息。。。
还有路径数比较多,要记得开long long

hdu 4451 Dressing (计数,思维题)

http://acm.hdu.edu.cn/showproblem.php?pid=4451
题意:N clothes, M pants and K shoes,然后给出p个不合法的搭配,形式是“clothes x pants y” or “pants y shoes z”.” 问有多少种合法的方案。
思路:一开始觉得是容斥。。当然可以。。但是实际上,不合法的搭配的形式比较简单,每种不合法的发配都是两个两个的不合法,以及每种不合法的形式都有pants,那么我们就可以通过先确定pants,对于每种pants,方案数就是能和当前pants搭配的clothes数,乘以能和当前pants搭配的shoes数,然后累加每种pants的答案即可。

hdu 5145 NPY and girls

http://acm.hdu.edu.cn/showproblem.php?pid=5145
题意:有n个女孩,编号1..n,第i个女孩在第a[i]个教室,m次访问,每次访问编号[L,R]的女孩,处于同一个教室的女孩一次只能访问一个,问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。

思路:正好刚刚听完学堂在线上的组合数学的那一节,讲到有重复元素的不重复排列的个数的计算方法:可以先将所有元素看成不重复,再除以每个元素的重复度的阶乘(重复度定义为每个元素个数)。

增加一个元素的影响是,乘一个增加的长度,并且除以该元素的重复度(因为每增加一个元素就要除以以此重复度,那么当同一元素c增加到第i次时,除以的就是i的阶乘),减少一个元素的影响正相反。 两种改变都可以O(1)实现,因此可以上莫队。

之前要预处理下逆元。

 

 

 

codeforces #334 div 2 D.Moodular Arithmetic

http://codeforces.com/contest/604/problem/D
题意:一个恒等式 f(k*x%p)=k*f(x)%p ,k,p为常数,且满足x对于定义域为0..p-1的p的整数,值域也在0..p-1范围(不一定一一对应)。问满足题意的f有多少个。
思路:
f(0)=0,对于其他的值,当f(x)确定时,f(k*x%p)也随之确定,那么把k*x%p看做新的x,f(k*k*x%p)也随之确定…相当于【1,p-1】被分为r个小环,确定每个环可以任选一个数字,ans=p^r。环的个数可以用dfs跑一遍得到r.
注意当k=1的时候是特殊情况,f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1),每一个都可以任意取p种值。

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] = C(x+y,x),其中如果在黑点i的左上还有黑点j(u,v),那么应该减去sum[j]*C(x-u+y-v)(y-u)

然后可以把坏点按照x为第一关键字,y为第二关键字排序.

从左上出发,往右下扫黑点.

还有一个考点是大组合数的求法

因为太大,递推也不行.

可以用欧拉公式求逆元的方法求解.

或者是lucas定理.

记得拿到骑士(1,1)到(n,m)的题和这道题很像.

也是从坐上到右下,中间有些坏点,不过骑士的走法并不是向下或者想有1步,而是向右p步,向下q步,或者向又q步,向下p步.

而且那道题的n和m是 10^9的数量级…

那道题的话就只能用lucas定理了貌似

这道题算是那道题的弱化版本,在此orz zhangk,果然厉害

所以我还是决定写lucas定理的解法

lucas定理适用于 求C(n,m)%p,p为素数 且n,m很大的情况.

引用一段题解: