3783. 【NOIP2014模拟8.19】签到题

科技前沿 • 2025-01-29 21:07 • 阅读 51

大家好，我是讯享网，很高兴认识大家。

Description

给定n个数，求出这n个数的一个非空子集，使得这个子集中的数的和能被n整除，无解输出-1.

Input

Output

对于每一组数据，如果无解输出一行一个整数-1；否则第一行输出一个正整数m，表示子集的大小，然后在第二行输出m个数，分别是这个子集中的数。如果有多种方案，输出任意一种。

Sample Input

1 1 1

讯享网

Sample Output

讯享网1 1

Data Constraint

对于30%的数据 n<=20
对于50%的数据 n<=100
对于70%的数据 n<=1000
对于100%的数据 n<=,T<=10

Solution

我们可以证明取连续的一段区间是可以满足要求的。

讯享网

取每一位的前缀和，加上0一共有n+1项，当每一位上的数都模上n后的取值只有0~n-1一共n中，因此必定有一种重复，取两个重复的端点相减的差一定能整除n。

因此，我们对于每个位置上的数记录在一个桶中，当有出现重复时取这个区间的数就可以了。

当然，你也可以用2^n暴力做这道题。

Code1

#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define I int #define ll long long #define F(i,a,b) for(register I i=a;i<=b;i++) #define Fd(i,a,b) for(register I i=a;i>=b;i--) #define mem(a,b) memset(a,b,sizeof(a)) #define N  using namespace std; void rd(I &x){ x=0;I w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x*=w; } I T,n,a[N],ans[N],bz[N]; void dg(I x,ll sum,I tot){ if(bz[0]) return; if(sum&&sum%n==0){ F(i,1,n) ans[i]=bz[i]; ans[0]=tot; bz[0]=1;return; } if(x>n) return; if(!bz[0]){ bz[x]=1;dg(x+1,sum+a[x],tot+1); bz[x]=0; } if(!bz[0]) dg(x+1,sum,tot); } I main(){ freopen("checkin.in","r",stdin); freopen("checkin.out","w",stdout); rd(T); while(T--){ rd(n); F(i,1,n) rd(a[i]); mem(ans,0); bz[0]=0; dg(1,0,0); if(!ans[0]) printf("-1\n"); else{ printf("%d\n",ans[0]); F(i,1,n) if(ans[i]) printf("%d ",a[i]); printf("\n"); } } return 0; }

Code2

讯享网#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define I int #define ll long long #define F(i,a,b) for(register I i=a;i<=b;i++) #define Fd(i,a,b) for(register I i=a;i>=b;i--) #define mem(a,b) memset(a,b,sizeof(a)) #define N  using namespace std; void rd(I &x){ x=0;I w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x*=w; } I T,n,x,a[N],b[N],c[N],l,r; I main(){ freopen("checkin.in","r",stdin); freopen("checkin.out","w",stdout); rd(T); while(T--){ rd(n); mem(a,0);mem(b,0); F(i,1,n){rd(c[i]);a[i]=(a[i-1]+c[i]%n+n)%n;} F(i,1,n){ if(!a[i]){l=1,r=i;break;} if(b[a[i]]){l=b[a[i]]+1,r=i;break;} b[a[i]]=i; } printf("%d\n",r-l+1); F(i,l,r) printf("%d ",c[i]); printf("\n"); } return 0; }