关于ACM的输入输出（一） 写给第一次参加现场赛的同学们 一般来说ACM的现场赛会规定输入输出 或者是文件输入标准输出 也可能是文件输入文件输出 如果没有规定的话那么一般就是标准的输入输出了 那说一下输入输出的重定向 一般用下面两种方法 c++常用: #include ifstream filein("data.in"); // 定义一个文件输入流 ofstream fileout("data.out"); //cout<< --> fileout<< filein.eof() //文件到末尾,返回非零值 data.in表示输入的数据文件 本地测试的话本来输入的数 …

水题 写一遍的目的是。。。复习一下快速筛的写法　喵呜 /************************************************************************* > File Name: code/poj/2909.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月22日 星期六 14时25分34秒 ************************************************************************/ …

题意是说，能构造多少本元勾股数和勾股数，要求构造的数<=n 所谓本元勾股数，就是三个勾股数没有公因数，两两互质。 由本元勾股数扩大k倍，就可以得到其他勾股数。 而构造本元勾股数的方法如下： ***a=st,b=(s^2-t^2)/2,c=(s^2+t^2)/2 其中s>t>=1是任意没有公因数的奇数！ 引用一段构造正确性的证明： 本原勾股数组（PPT)是一个三元组（a，b，c),其中a，b，c无公因数，且满足a² +b² =c²。 很明显存在无穷多个勾股数组（abc同乘以n），下面研究abc没有公因数的情况，先写出一些本原勾股数组： case:(3,4,5) (5,12,13) (8,15,17) …

转载自：http://www.cnblogs.com/vongang/archive/2013/03/10/2952978.html POJ【数论/组合/博弈论】题目列表 原来的列表比较水，今天换了一个难一些的列表，重新开始做~ 博弈论 POJ 2234 Matches Game POJ 2975 Nim POJ 2505 A multiplication game POJ 1067 取石子游戏　威佐夫博弈，奇异局势（必败局）为ak = [k*(1 + sqrt(5))/2], bk = ak + k; POJ 2484 A Funny Game　这题真欢乐 POJ 2425 A Chess Game POJ 2960 S-Nim …

昨天那道签到的数学题没搞出来不开心. 是时候刷一波数学了 这题题意是说,从n个数中任选m个,使得m个的和为c的倍数. 如果有解,输出选的数的下标,否则输出无解字符串. 抽屉原理的原始描述是,如果有n+1个物品,有n个抽屉,那么至少有一个抽屉有2个物品. 由抽屉原理我们可以退出一个结论,对于任意 n个自然数,一定有连续的一段和为n的倍数. 证明如下: 　设这n个自然数分别为a1,a2,a3,a4....an 　处理一个前缀和sum[i] = (sum[i-1] + a[i])%n 　因为n的剩余类有n种,分别为0,1,2...n-1 　所以sum[1],sum[2],sum[3]..sum[n] 　那 …

比赛的时候以为是贪心... 想了好久. 不过最后没敢写,因为没办法证明正确性,只是直觉== 最后剩下的时间给队友改另一道题了.. 果然明智... 蠢的人的直觉真心不靠谱.. 这题是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 …