poj 3274 题目链接 题意：给出n个数和k，每个数不超过k位二进制。现在问最长的一段区间，满足该区间中所有数相加，k个位置上的数相等。 思路：k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。 于是抽屉原理搞了一发。。一直wa.. 正解是数字hash。。。 不过我拍了一下。。。如果不是我理解错了题意的话。。。我是把一份ac代码　hack掉了。。。。。 用来对拍的ac代码： #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using …

http://poj.org/problem?id=2356 题意：有n个数，从中选取若干个（1..n），和能被n整除。问是否有解，无解输出0，有解的话，输出个数以及选择的ai 由抽屉原理可知一定有解： 做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n n个数，sum[i]最多有n种。 如果某个sum[i]为0，那么表示从1到i的和能被n整除。 如果所有的sum[i]不为0，那么一共有n个sum[i]，n-1个值（1..n-1），一定有sum[i]==sumj 那么a[i]到a[j]的和一定能被n整除。 …

http://acm.hdu.edu.cn/showproblem.php?pid=1205 题意：有n种糖果，第i种糖果有a[i]个，相邻两次不能吃一样的糖果，问能否有办法吃完所有糖果... 思路：如果第i种糖果有k个的话，那么其他所有种类的糖果之和至少有k-1个，才可能吃完。复杂度O(n) 看到有人说是抽屉原理.....大概。。。？不过不太明显。。直接想就好吧 /* *********************************************** Author :111qqz Created Time :2016年02月29日 星期一 20时40分00秒 File Name :code/hdu/1205.cpp …

背包还是理解的不够透彻．． 因为每次都是用那个一维形式的． 这道题的做法类似01背包. 此外还可以有一个优化... 当n>m的时候．．．根绝抽屉原理．．一定为yes.. 复杂度可以从o(nm)优到　o(m^2) /************************************************************************* > File Name: code/cf/#319/B.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年09月15日 星期二 19时54分44 …

昨天那道签到的数学题没搞出来不开心. 是时候刷一波数学了 这题题意是说,从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] 　那 …

算是签到帖，竟然卡住了。 我数学还是太差了。。 然后去找题解。。竟然看不懂！ 我数学真的有这么差嘛。。。 然后多亏了队友 @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] …