Note: This article is available in Chinese only. 本文暂无英文版本。
View original
昨天那道签到的数学题没搞出来不开心.
是时候刷一波数学了
这题题意是说,从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第二次出现,就输出这段下标.
嘛,大括号换风格了….
都写开代码太长了==
1/*************************************************************************
2 > File Name: code/poj/3370.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月21日 星期五 13时06分34秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int a[N];
33LL sum[N];
34int p[N];
35int n,c;
36int main()
37{
38 while (~scanf("%d %d",&c,&n)){
39 if (c==0&&n==0) break;
40 sum[0] = 0;
41 for ( int i = 1 ; i <= n ;i++){
42 scanf("%d",&a[i]);
43 a[i] = a[i] % c;
44 sum[i] = (sum[i-1] + a[i])%c;
45 }
46 memset(p,0,sizeof(p));
47 for ( int i = 1 ; i <= n ; i++ ){
48 if (sum[i]==0){
49 for ( int j = 1 ; j <= i ; j++){
50 cout<<j<<" ";
51 // cout<<"wang wang wang !"<<endl;
52 }
53 cout<<endl;
54 break;
55 }
56 if (p[sum[i]]){
57 for ( int j = p[sum[i]]+1 ; j <= i ; j++){
58 cout<<j<<" ";
59 // cout<<"111qqz"<<endl;
60 }
61 cout<<endl;
62 break;
63 }
64 p[sum[i]] = i ;
65 }
66 }
67
68 return 0;
69}