。

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) …

问两个长度相同的字符串是否等价． 相等的条件是，两个字符串相等，或者两个偶数长度（因为要分成长度相同的两段，所以一定是偶数长度才可分）字符串平均分成两部分，每部分对应相等(不考虑顺序) 一开始有一点没想清楚. 如果字符串a分成相等长度的两部分a1,a2,字符串b分成相等的两部分b1,b2 我错误得以为,如果a1和a2等价&&b1;和b2等价,那么a 和 b 就相等了(a和b一定等价,但不一定相等),于是只判断了 equal(a1,b2)&&equal;(a2,b1) wa了一次. < …

题意：给定一个六边形的六条边的长，问能分割成多少个单位正三角形． 分割不好办，那我们就反着来，先补成一个包含这个六边形的正三角形． 对于边长为a的正三角形，显然我们可以分割成a*a个单位正三角形 大正三角形的边长为连续的三条边的和 而要减掉的三个小三角形的边长为与之前连续的三条边的起始边的序号的奇偶性相同的三条边． 就是说如果求和的时候求的是前三条边，那么三个要减掉的小三角形的边长就是第一，三，五条边． 如果求和的时候求的是后三条边，那么三个要减掉的小三角形的边长就是第二，第四，第六条边． …

/************************************************************************* > File Name: code/cf/#313/B.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: Wed 22 Jul 2015 09:52:54 PM CST ************************************************************************/ #include<iostream> …

做过一道类似的题 因为是问最短，很容易想到是bfs 对于点x，可以到达点x-1,和点2*x 需要注意的是上界限。 并不是max(m,n) 因为可能先达到比m大，之后再减回来的情况是更优的。 max(2m,2n)肯定是足够的 /************************************************************************* > File Name: code/cf/#295/B.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月17日 星期一 04时16分51 …

给一个字符串，问这个字符串中是否26个字母都出现过（大小写只出现一个就算出现过） 开个布尔数组，扫一遍即可。 嘛，做两道水题放松下== 反正也是要清的。 /************************************************************************* > File Name: code/cf/#295/A.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月17日 星期一 04时05分12 …

将博客搬至CSDN

题意是说，给定一个有向图，对于每一条边，问是否是s到t的最短路上一定会经过的边． 如果是就输出yes 如果不是，问能否通过减少这条边的权值（减少的权值就是修理费用），使得这条边成为新的最短路上的边． 对于一条边是否一定是最短路上的边，我们可以从s做一遍最短路，然后反响建边，从t再做一遍最短路． 得到两个d1,d2数组 如果一条边d1[u] + d2[v] + w(u, v) = 最短路，那这条边在最短路上的边．但是未必不能缺少． 我们还要判断这条边是否是不能缺少的． 不能缺少的意思是说，如果没有这条边，就不能构成最短路． 那么这条边一定是桥． 我们可以用tarjan算法求桥． 据说是水题，不过图论还没怎么刷，所以对我来说还是很有难度 …

很容易看出来是dp 我们左右一起，一对一对放． 对于每一对，有三种方法，分别是两左，一左一右，两右． 初始区间长度为２n，每次放完后缩小区间长度 ，最后一定是放２个n，这个时候区间长度缩小为２，表明一种满足题意的情况． 状态转移的时候需要分别判断三个状态是否满足题目中给出的k组限制条件． 细节见注释． /************************************************************************* > File Name: code/cf/#314/F.cpp > Author: 111qqz > Email: rkz2013@126.com > …