首页 > 代码库 > POJ 2356 && POJ 3370 鸽巢原理
POJ 2356 && POJ 3370 鸽巢原理
POJ 2356：
题目大意：
给定n个数，希望在这n个数中找到一些数的和是n的倍数，输出任意一种数的序列，找不到则输出0
这里首先要确定这道题的解是必然存在的
利用一个 sum[i]保存前 i 个数的和对n的取模
sum[0] = 0;
那么sum[0] ~ sum[n]有n+1个数据，这些数据的范围都是 0~n ， 要是存在 sum[i] = 0,那么输出前 i 个数据即可
要是不存在那根据鸽巢原理可以说明必然能找到一个 sum[i] = sum[j] ，那么说明 (sum[i+1] + sum[i+2] ...+sum[j])%n = 0的，把这j-i个数输出即可
那么说明我们总是能找到一段连续的数据使其和是n的倍数
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 const int N = 10005; 6 7 bool vis[N]; 8 int sum[N] , a[N] , pos[N]; 9 10 int main()11 {12 // freopen("a.in" , "r" , stdin);13 int n;14 while(scanf("%d" , &n) != EOF)15 {16 for(int i=1 ; i<=n ; i++){17 scanf("%d" , a+i);18 }19 memset(vis , 0 , sizeof(vis));20 vis[0] = 1 , pos[0] = 0;21 for(int i=1 ; i<=n ; i++){22 sum[i] = (sum[i-1]+a[i])%n;23 if(vis[sum[i]]){24 int l = pos[sum[i]];25 printf("%d\n" , i-l);26 for(int j = l+1 ; j<=i ; j++){27 printf("%d\n" , a[j]);28 }29 break;30 }31 pos[sum[i]] = i;32 vis[sum[i]] = 1;33 }34 }35 return 0;36 }
POJ3370：
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 #define N 100005 6 bool vis[N]; 7 int sum[N] , a[N] , pos[N]; 8 9 int main()10 {11 // freopen("a.in" , "r" , stdin);12 int c , n;13 while(scanf("%d%d" , &c , &n) , c||n)14 {15 for(int i=1 ; i<=n ; i++)16 scanf("%d" , a+i);17 memset(vis , 0 ,sizeof(vis));18 sum[0] = 0 , vis[0] = 1 , pos[0] = 0;19 for(int i=1 ; i<=n ; i++){20 sum[i] = (sum[i-1] + a[i])%c;21 if(vis[sum[i]]){22 int l = pos[sum[i]];23 for(int j=l+1 ; j<=i ; j++){24 if(j == l+1) printf("%d" , j);25 else printf(" %d" , j);26 }27 printf("\n");28 break;29 }30 vis[sum[i]] = 1;31 pos[sum[i]] = i;32 }33 }34 return 0;35 }
POJ 2356 && POJ 3370 鸽巢原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。