首页 > 代码库 > AC日记——N的倍数 51nod 1103
AC日记——N的倍数 51nod 1103
1103 N的倍数
思路：
先计算出前缀和；
然后都%n；
因为有n个数，所以如果没有sum[i]%n==0的化，一定有两个取模后的sum相等；
输出两个sum中间的数就好；
来，上代码：
#include <cstdio>using namespace std;#define maxn 50005int n,ai[maxn],sum[maxn],ioss[maxn];inline void in(int &now){ register char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}int main(){ in(n); for(int i=1;i<=n;i++) in(ai[i]),sum[i]=(sum[i-1]+ai[i])%n; for(int i=1;i<=n;i++) { if(sum[i]==0) { printf("%d\n",i); for(int j=1;j<=i;j++) printf("%d\n",ai[j]); return 0; } if(ioss[sum[i]]==0) ioss[sum[i]]=i; else { int pos=ioss[sum[i]]; printf("%d\n",i-pos); for(int j=pos+1;j<=i;j++) { printf("%d\n",ai[j]); } return 0; } } printf("No Solution\n"); return 0;}
疯狂优化没什么卵用版：
#include <cstdio>int n,u[50001],s[50001],o[50001];inline void w(register int x){ if(x>9) w(x/10); putchar(x%10+48);}int main(){ scanf("%d",&n); int *a=&u[0],*b=&s[0]; for(int i=1;i<=n;i++) { a++,b++; register char Cget=getchar();*a=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { *a=*a*10+Cget-‘0‘; Cget=getchar(); } *b=(s[i-1]+*a)%n; if(*b==0) { w(i),putchar(‘\n‘); for(register int *p=&u[1];p!=&u[i+1];p++) w(*p),putchar(‘\n‘); return 0; } if(o[*b]==0) o[*b]=i; else { int pos=o[*b]; w(i-pos),putchar(‘\n‘); for(register int *p=&u[pos+1];p!=&u[i+1];p++) w(*p),putchar(‘\n‘); return 0; } } printf("No Solution\n"); return 0;}
AC日记——N的倍数 51nod 1103
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。