51Nod 1103 N的倍数 前缀和+抽屉原理

本文主要是介绍51Nod 1103 N的倍数 前缀和+抽屉原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1103 N的倍数

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 20 分
6.  
7. 3级题

一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。

例如：N = 8，数组A包括：2 5 6 3 18 7 11 19，可以选2 6，因为2 + 6 = 8，是8的倍数。

 收起

输入

第1行：1个数N，N为数组的长度，同时也是要求的倍数。(2 <= N <= 50000)
第2 - N + 1行：数组A的元素。(0 < A[i] <= 10^9)

输出

如果没有符合条件的组合，输出No Solution。
第1行：1个数S表示你所选择的数的数量。
第2 - S + 1行：每行1个数，对应你所选择的数。

输入样例

8
2
5
6
3
18
7
11
19

输出样例

2
2
6

分析：

前缀和sum[i]%n总共有0~n-1这n种情况；

如果sum[i]=0，那么1~i的数之和就是N的倍数；

如果不存在sum[i]=0，那么根据抽屉原理，有n个前缀和，n-1种情况，那么一定存在sum[i]=sum[j]，那么i+1~j的数之和就是n的倍数

所以根本不会出现错误情况

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e18;
const int N = 500050;
const int MOD=1e9+7;
LL sum[N],a[N],vis[N];
LL ans,ans_l,ans_r,ans_size;
int main()
{int n,m;scanf("%d",&n);int flag=0;for(int i=1; i<=n; i++){scanf("%lld",&a[i]);sum[i]=(sum[i-1]%n+a[i]%n)%n;if(sum[i]%n==0){ans_size=i;flag=1;}vis[sum[i]]++;if(vis[sum[i]]>=2){ans_r=i;}}if(flag==1){printf("%lld\n",ans_size);for(int i=1; i<=ans_size; i++){printf("%lld\n",a[i]) ;}}else{for(int i=ans_r-1; i>=1; i--){if(sum[i]==sum[ans_r]){ans_l=i;break;}}printf("%lld\n",ans_r-ans_l+1);for(int i=ans_l+1; i<=ans_r; i++){printf("%lld\n",a[i]) ;}}return 0;
}

 

这篇关于51Nod 1103 N的倍数 前缀和+抽屉原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---