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第二次出现,就输出这段下标.
嘛,大括号换风格了....
都写开代码太长了==
/*************************************************************************
> File Name: code/poj/3370.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月21日 星期五 13时06分34秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x3f3f3f3f;
24const int N=1E5+7;
25int a[N];
26LL sum[N];
27int p[N];
28int n,c;
29int main()
30{
31 while (~scanf("%d %d",&c,&n)){
32 if (c==0&&n==0) break;
33 sum[0] = 0;
34 for ( int i = 1 ; i <= n ;i++){
35 scanf("%d",&a[i]);
36 a[i] = a[i] % c;
37 sum[i] = (sum[i-1] + a[i])%c;
38 }
39 memset(p,0,sizeof(p));
40 for ( int i = 1 ; i <= n ; i++ ){
41 if (sum[i]==0){
42 for ( int j = 1 ; j <= i ; j++){
43 cout<<j<<" ";
44 // cout<<"wang wang wang !"<<endl;
45 }
46 cout<<endl;
47 break;
48 }
49 if (p[sum[i]]){
50 for ( int j = p[sum[i]]+1 ; j <= i ; j++){
51 cout<<j<<" ";
52 // cout<<"111qqz"<<endl;
53 }
54 cout<<endl;
55 break;
56 }
57 p[sum[i]] = i ;
58 }
59 }
return 0;
}