本文主要是介绍POJ2536、3370，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
n
a1,a2,a3....an (1<=ai<=n,切有可能ai=aj)
问这个数列中是否存在k个数的数字之和可以被n整除
鸽笼原理的一个应用
考虑 a1, a1+a2,a1+a2+a3,....a1+a2+a3+a4,,+an 一共有n个正数
若这个n个正数都可以被n整除那么肯定是存在k的，
现在设这n个正数除n都有一个非0的余数，因为余数共有n-1种，有n个数，肯定有两个余数是相同的，
因此存在a1+a2..+ak = bn+r 和a1+a2+...+al =cn+r都余r
则 ak+1...+al = (c-b)n 说明了整除性一定存在。
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std;
const int maxn=1e5;
int mod[maxn];
int val[maxn];
int sum[maxn];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n;while(scanf("%d",&n)!=EOF){memset(sum,0,sizeof(sum));memset(val,0,sizeof(val));memset(mod,-1,sizeof(mod));for(int i=1; i<=n; ++i){scanf("%d",&val[i]);sum[i] = ( sum[i-1] + val[i] )%n; }mod[0] = 0;for(int i=1; i<=n;++i){if(mod[sum[i]] == -1){mod[sum[i]] = i;}else{cout<<i-mod[sum[i]]<<endl;for(int j=mod[sum[i]]+1; j<=i;++j)cout<<val[j]<<endl;break;}}}return 0;
}题目好像要求在有多个结果得时候输出一个数量最少得
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std;
const int maxn=1e5;
int mod[maxn];
int val[maxn];
int sum[maxn];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n;while(scanf("%d",&n)!=EOF){memset(sum,0,sizeof(sum));memset(val,0,sizeof(val));memset(mod,-1,sizeof(mod));for(int i=1; i<=n; ++i){scanf("%d",&val[i]);sum[i] = ( sum[i-1] + val[i] )%n; }mod[0] = 0;for(int i=1; i<=n;++i){if(mod[sum[i]] == -1){mod[sum[i]] = i;}else{cout<<i-mod[sum[i]]<<endl;for(int j=mod[sum[i]]+1; j<=i;++j)cout<<val[j]<<endl;break;}}}return 0;
}POJ3370
给你两个整数C和N，再给你N个正数的序列，从中找到若干数，使得其和刚好是 C的倍数。输出这些数的序号。
//POJ3370
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
int mod[maxn];
int val[maxn];
int pos[maxn];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n,c;while(scanf("%d%d",&c,&n)!=EOF){if(c==0&&n==0) return 0;memset(mod,0,sizeof(mod));memset(pos,-1,sizeof(pos));mod[0] = 0;for(int i=1;i<=n;++i){scanf("%d",&val[i]);mod[i] = ( mod[i-1] +val[i] )%c; }pos[0] = 0;int k,r;for(int i=1;i <= n;++i){if(pos[ mod[i] ] == -1)pos[mod[i]] = i;else{k= pos[mod[i]] ;r= i; //cout<<k<<' '<<r<<endl;break;}}// cout<<k<<' '<<r<<endl;for(int i=k+1; i<r;++i)cout<<i<<' ';cout<<r<<endl;}return 0;
}
这篇关于POJ2536、3370的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
