题意:
3个岛屿群,每个岛屿群有若干岛屿。现在要在岛屿之间连桥,桥的长度是1,规定2个属于相同岛屿群的岛屿的距离要大于等于3.
思路:
一直在纠结大于等于3的距离的事情。。。其实这句话等价于,同一个岛屿,对于另外两个岛屿群,都最多只能连接1个岛屿。
阅读更多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的答案即可。
阅读更多http://poj.org/problem?id=1322 题意:
思路:别看n,m很大。。。但是想一下。。m显然不可能大于c(如果大于c,那么根据抽屉原理,至少存在一种巧克力大于一个,然而大于一个就会被取走...矛盾) 这样概率为0.m也不可能大于n,因为最好的情况就是取出的巧克力都放在了桌子上,如果总共取的还不到n个,又怎么可能剩下m(m>n)个呢。此外,还需要n,m奇偶性相同,否则设n-m=2K+1 ,说明如果要剩余m个,那么就要减少2k+1个,但是巧克力是两个两个减少的,减少的个数一定是偶数,因此矛盾。所以n,m奇偶性相同。
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=1028 题意:求整数拆分数。 思路:母函数模板题。关于母函数的学习:http://www.cnblogs.com/syxchina/archive/2011/07/07/2197205.html http://www.cppblog.com/tanky-woo/archive/2010/08/02/121969.html
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=5145 题意:有n个女孩,编号1..n,第i个女孩在第a[i]个教室,m次访问,每次访问编号[L,R]的女孩,处于同一个教室的女孩一次只能访问一个,问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。
阅读更多http://codeforces.com/contest/604/problem/D 题意:一个恒等式 f(kx%p)=kf(x)%p ,k,p为常数,且满足x对于定义域为0..p-1的p的整数,值域也在0..p-1范围(不一定一一对应)。问满足题意的f有多少个。 思路: f(0)=0,对于其他的值,当f(x)确定时,f(kx%p)也随之确定,那么把kx%p看做新的x,f(kkx%p)也随之确定...相当于【1,p-1】被分为r个小环,确定每个环可以任选一个数字,ans=p^r。环的个数可以用dfs跑一遍得到r. 注意当k=1的时候是特殊情况,f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1),每一个 …
阅读更多D. Symmetric and Transitive
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Little Johnny has recently learned about set theory. Now he is studying binary relations. You've probably heard the term "equivalence relation". These relations are very …
阅读更多