比赛的时候以为是贪心... 想了好久. 不过最后没敢写,因为没办法证明正确性,只是直觉== 最后剩下的时间给队友改另一道题了.. 果然明智... 蠢的人的直觉真心不靠谱.. 这题是dp 我们可以把车按照方向的不同分为A车和B车 dp[i][j][0..1]表示已经经过了a方向的i辆车,经过了b方向的j辆车,并且最后一辆车是a/b方向的情况的离开道路的时间. 似乎问题不大. 然后就一直wa... wa到怀疑人生好么!!! 最后发现 问题出在! dp数组初始化赋值成正无穷的时候,溢出啦! 然后我搜了下,发现0x7fffffff果然不是什么好东西! 以后正无穷用0x3f3f3f3f 这东西>1E9,相加不超过int 而且最重要的是, …

如果问题中各数据的范围明确，那么无穷大的设定不是问题，在不明确的情况下，很多程序员都取0x7fffffff作为无穷大，因为这是32-bit int的最大值。如果这个无穷大只用于一般的比较（比如求最小值时min变量的初值），那么0x7fffffff确实是一个完美的选择，但是在更多的情况下，0x7fffffff并不是一个好的选择。 很多时候我们并不只是单纯拿无穷大来作比较，而是会运算后再做比较，例如在大部分最短路径算法中都会使用的松弛操作： if (d[u]+w[u][v]我们知道如果u,v之间没有边，那么w[u][v]=INF，如果我们的INF取0x7fffffff，那么d[u]+w[u][v]会溢出而变成负数，我们的松弛操作便出错 …

算是签到帖，竟然卡住了。 我数学还是太差了。。 然后去找题解。。竟然看不懂！ 我数学真的有这么差嘛。。。 然后多亏了队友 @zcy 妹子的讲解。。 其实很好理解啊。。。 不过数到底还是数学太差了== 今天七夕，废话有点多== 这道题的题意是，找序列中连续的一段，使得和 可以整除d 我们观察到数列中的数的范围是1..1 000 000 000 的 而d只有1 000 000 我们考虑余数相同，读入的时候就可以直接先 % 掉 d 因为只会和余数有关。 我们可以先处理出来一个前缀和数组sum[i]，表示前i个元素的和。 如果有一段序列从a[i] 到 a[j] 满足题意 根据题意那么这段序列的和一定%d=0 a[i] 到 a[j] …

蠢了。 这道题显然可以搜。。 然后自己搜索的姿势果然还是不怎么地。。 最后是蔡大神过掉的。 他的思路是枚举素数，然后把素数的各位拆开，看这些数字是否在给出的字符串中出现过。 一开始TLE掉了。 后来又预处理出来一个标记数组，如果字符串中没有数字2，那么20w+的素数就可以直接跳过去，然后A掉了。 其实因为数字的位数最多才7位。。 暴力也不是不可以。。。。 STL中求全排列的那个函数我也不是没用过。。。比赛的时候怎么就没想到== 再开个map判重 然后素数打表部分。 队友是打了个30000+行的表。。。。 说起来。。。我好像还没用C++写过筛法求素数。。。 说来惭愧啊。。。。 pascal的时候倒是写过几次呢。 再复习下。。。 …

TAG 素数 数论 素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。 基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子2 。。N^(0.5) ，看看能否整除N。 如果需要判断的次数较多，则先用下面介绍的办法预处理。 一般的线性筛法 首先先介绍一般的线性筛法求素数 [cpp] view plaincopy void make_prime() { memset(prime, 1, sizeof(prime)); prime[0]=false; prime[1]=false; int N=31700; for (int i=2; i if (prime[i]) { primes[++cnt ]=i; for …

。

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