题解 - [POJ 2356] [Ural 1032] Find a multiple

发表于 更新于 分类于 ， 本文字数： 394 阅读时长 ≈ 1 分钟

题目链接

原始题面

Description

The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k)

Input

The first line of the input contains the single number N. Each of next N lines contains one number from the given set

Output

In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order

If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them

Sample Input

1
2
3
4
5
6
5
1
2
3
4
1

Sample Output

1
2
3
2
2
3

Source

Ural Collegiate Programming Contest 1999

题意简述

给出 \(n\) 个数，取其中的一个子集，使得该子集中所有元素的和是 \(n\) 的自然数倍

解题思路

对这 \(n\) 个数求其模 \(n\) 意义下的前缀和 sum[1..n] , 如果其中有一个 sum[i] == 0 , 则所求子集即为从第 1 个到第 i 个的所有元素

否则 sum[1..n] 均在 \([1,n-1]\) 内，此时由抽屉原理可知，必有两前缀和相等，即存在 \(1\leqslant i<j\leqslant n\) 使得 sum[i] == sum[j], 此时所求子集即为从第 i + 1 个到第 j 个的所有元素

复杂度

\(O(n)\)

代码参考

Show code

POJ_2356view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
const int N = 1e4 + 5;
int a[N], sum[N];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    if (!(sum[i] = (sum[i - 1] + a[i]) % n)) {
      printf("%d\n", i);
      for (int j = 1; j <= i; ++j) printf("%d\n", a[j]);
      return 0;
    }
  }
  for (int i = 1; i < n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (sum[i] == sum[j]) {
        printf("%d\n", j - i);
        for (int k = i + 1; k <= j; ++k) printf("%d\n", a[k]);
        return 0;
      }
}