111qqz的小窝

老年咸鱼冲锋!

poj 3274 Gold Balanced Lineup (抽屉原理?错题?)

poj 3274 题目链接

题意:给出n个数和k,每个数不超过k位二进制。现在问最长的一段区间,满足该区间中所有数相加,k个位置上的数相等。

思路:k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。

于是抽屉原理搞了一发。。一直wa..

正解是数字hash。。。

不过我拍了一下。。。如果不是我理解错了题意的话。。。我是把一份ac代码 hack掉了。。。。。

用来对拍的ac代码:

 

 
 

我的代码:

 

 
数据生成器:

 

 
出错的输入:

 

 
我的输出:

 

 
ac代码的输出:

 

 

 

 
 

poj 2356 Find a multiple (剩余类,抽屉原理)

 

http://poj.org/problem?id=2356

题意:有n个数,从中选取若干个(1..n),和能被n整除。问是否有解,无解输出0,有解的话,输出个数以及选择的a[i]( 不是i)

由抽屉原理可知一定有解:
做一个带模的前缀和 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]==sum[j](i<=j)
那么a[i]到a[j]的和一定能被n整除。

hdu 1205 吃糖果 (鸽笼原理)

http://acm.hdu.edu.cn/showproblem.php?pid=1205
题意:有n种糖果,第i种糖果有a[i]个,相邻两次不能吃一样的糖果,问能否有办法吃完所有糖果…
思路:如果第i种糖果有k个的话,那么其他所有种类的糖果之和至少有k-1个,才可能吃完。复杂度O(n)
看到有人说是抽屉原理…..大概。。。?不过不太明显。。直接想就好吧

codeforces #319 B – Modulo Sum (抽屉原理,dp)

背包还是理解的不够透彻..

因为每次都是用那个一维形式的.

这道题的做法类似01背包.

此外还可以有一个优化…

当n>m的时候...根绝抽屉原理..一定为yes..

复杂度可以从o(nm)优到 o(m^2)

poj 3370 Halloween treats (剩余类,抽屉原理)

昨天那道签到的数学题没搞出来不开心.
是时候刷一波数学了
这题题意是说,从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]
  那么sum[1],sum[2],sum[3]…sum[n]最多也有n种.
  我们分情况讨论:
    (1)sum[1],sum[2],sum[3]…sum[n]互不相同,那么一定存在sum[i]=0,也就是前i个数的和为n的倍数.
    (2)情况(1)的反面,也就是存在sum[i]==sum[j]  (i<j),那么 从a[i+1] 到 a[j]的和就是n的倍数.
因为题目中的数据 c<=n ,所以解一定存在.
具体做法就是处理出来一个前缀和%c
然后如果有0,则为解,输出.
否则记录sum[i]%d出现的位置,存在一个数组里
如果sum[i]%d第二次出现,就输出这段下标.
嘛,大括号换风格了….
都写开代码太长了==

HUST team contest #2 C Divisible Subsequences ||poj 3844 (剩余类)

算是签到帖,竟然卡住了。

我数学还是太差了。。

然后去找题解。。竟然看不懂!

我数学真的有这么差嘛。。。

然后多亏了队友 @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]的和为 sum[j]-sum[i-1]

也就是(sum[j]-sum[i-1] )%d==0

也就是sum[j] 和 sum[i-1] 关于 d 同余

如果我们在处理得到前缀和的时候就%dshuxue

那么就是sum[j]==sum[i-1]

所以我只要对于d的每一个剩余类有多少个统计出来。

然后对于每个剩余类,只需要任意取出两个,就是一种答案。

需要注意的是如果只有一个0,也是一种答案。

我们可以定义sum[i] = 0

还有一个需要注意的是要开long long