poj3370Halloween treats抽屉原理

链接

简单的说就是已知c,n和n个无序数字，要求这n个数中那些的和能被c整除==

联想到课件给的

例题： POJ 2356

题意：

给定n个数，求其中的任意一个非空子集满足集合中的每个元素值加和正好是n的倍数。

分析：

把前缀和统计出来对n取模，任意两个相等的sum [i], sum [j] ,[i ,j ]内的数的和都满足这个条件。

n个数对n取模，范围为[0~n-1]，由抽屉原理可知，最少有一个数模n=0，或者两个数模n相等。

以及题目已知的c<=n得出结论这两个题是一样一样一样的~~~

因为根据抽屉原理，一定能找到连续的一段数字串使得其和为c的倍数，于是乎很傻很天真的照着课件敲上去，华丽丽的超时了~

发现这样太满了，肿么破……数组，和，找相等==哈希啊！！！

#include<iostream>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include<cstring>
using namespace std;
const int N=100009;
int n,m;
int a[N];
int sum[N];
int hash[N];
int main()
{
	while(scanf("%d%d",&n,&m),n+m)
	{
		memset(hash,0,sizeof(hash));
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&a[i]);
		}
		int s=1,t=1;
		sum[0]=0;
		for(int i=1;i<=m;i++)
		{
			sum[i]=(sum[i-1]+a[i])%n;
			//cout<<i<<" "<<sum[i]<<endl;
			if(sum[i]==0)
			{
				t=i;
				break;
			}
			if(hash[sum[i]]>0)
			{
				s=hash[sum[i]]+1;
				t=i;
				break;
			}
			hash[sum[i]]=i;
		}
		for(int i=s;i<t;i++)
		printf("%d ",i);
		printf("%d\n",t);
	}
return 0;
}

这个题还可以hash数组只用来标记有或者没有出现过这个余数，即布尔型就可以了

AC代码如下

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool num[1000101];
int a[1000010],c,n,sum[1000010];
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d%d",&c,&n))
    {
        if(c==0&&n==0) break;
        int st=-1,ed=-1;
        memset(num,false,sizeof(num));
        sum[0]=0;
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            if(ed==-1) {
                sum[i]=(a[i]%c+sum[i-1])%c;
                if(!sum[i]) {st=1;ed=i;}
                else if(num[sum[i]]) ed=i;
                num[sum[i]]=true;
              //  printf("i=%d %d\n",i+1,sum[i]);
            }
        }
        for(int i=1;i<=n&&(st==-1);i++)
        {
            if(sum[i]==sum[ed]){
                st=i+1;
                break;
            }
        }
        printf("%d",st);
        for(int i=st+1;i<=ed;i++)
        printf(" %d",i);
        printf("\n");
    }
    return 0;
}

之前有一个小问题没注意到就是可能这样余数是0的话从第一个数开始 wa了好多次就像酱紫是不对的

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool num[1000101];
int a[1000010],c,n,sum[1000010];
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d%d",&c,&n))
    {
        if(c==0&&n==0) break;
        int st,ed=-1;
        memset(num,false,sizeof(num));
        sum[0]=0;
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            if(ed==-1) {
                sum[i]=(a[i]%c+sum[i-1])%c;
                if(num[sum[i]]) ed=i;
                num[sum[i]]=true;
              //  printf("i=%d %d\n",i+1,sum[i]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(sum[i]==sum[ed]){
                st=i+1;
                break;
            }
        }
        printf("%d",st);
        for(int i=st+1;i<=ed;i++)
        printf(" %d",i);
        printf("\n");
    }
    return 0;
}