111qqz的小窝

老年咸鱼冲锋!

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第二次出现,就输出这段下标.
嘛,大括号换风格了….
都写开代码太长了==

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363