频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 2356 Find a multiple 鸽巢原理
2012-08-05 13:47:00           
收藏   我要投稿

题意:有n个数,求是否存在一些数的和是n的倍数。若存在,输出即可。不存在,输出0.
思路:鸽巢原理的题目,组合数学课本上的原题。可以把和求出来,然后对n取余,因为有n个和,对n取余,如果余数中没有出现0,根据鸽巢原理,一定有两个数的余数相同,两个和想减就是n的倍数。如果余数出现0,自然就是n的倍数。也就是说,n个数中一定存在一些数的和是n的倍数。求余输出即可。
代码:
[cpp]
#include <iostream> 
#include <cstdio> 
#include <string.h> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
const int N = 10010; 
int num[N],sum[N],pos[N]; 
bool flag[N]; 
int main(){ 
    //freopen("1.txt","r",stdin); 
    int n; 
    while(scanf("%d",&n) != EOF){ 
        CLR(num,0); 
        CLR(sum,0); 
        CLR(pos,-1); 
        CLR(flag,false); 
      for(int i = 1; i <= n; ++i){ 
          scanf("%d",&num[i]); 
          sum[i] = sum[i-1] + num[i]; 
      } 
      for(int i = 1;i <= n; ++i){ 
        int x = sum[i] % n; 
        if(flag[x]){ 
          int y = pos[x]; 
          printf("%d\n",i - y); 
          for(int j = y+1; j <= i; ++j) 
              printf("%d\n",num[j]); 
          break; 
        } 
        if(x == 0){ 
          printf("%d\n",i); 
          for(int j = 1; j <= i;++j) 
              printf("%d\n",num[j]); 
          break; 
        } 
        flag[x] = true; 
        pos[x] = i; 
      } 
    } 
    return 0; 

 


作者:wmn_wmn
点击复制链接 与好友分享!回本站首页
相关TAG标签 原理
上一篇:HDU 4335 What is N? 多校4(数论)
下一篇: C++程序注册Dll
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站