目录
显示
题目链接
https://atcoder.jp/contests/abc105
A – AtCoder Crackers
大意
将 \(n\) 个物品分给 \(k\) 个人,问分到最多物品的人和最少物品的人,他们物品数量的差最小是多少。
题解
显然,\(n \bmod k=0\) 时答案为 0,否则答案为 1。
#include <stdio.h> int main() { int n,k; scanf("%d%d",&n,&k); if(n%k)puts("1"); else puts("0"); return 0; }
B – Cakes and Donuts
大意
给出 \(n\),求出 \(4x+7y=n\) 是否有自然数解。
题解
不得不说,小凯的疑惑要比这道题高出好几个档次了吧。
#include <stdio.h> int main() { int n; scanf("%d",&n); for(int i=0;4*i<=n;i++) if((n-4*i)%7==0) { puts("Yes"); return 0; } puts("No"); return 0; }
C – Base -2 Number
大意
将一个 10 进制数转换成 -2 进制数。
题解
虽然是负进制数,但我们还是可以采用短除法。
但是要注意 C++ 中除号和 MOD 的 feature,除法是向 0 取整的,所以 \(-9/(-2)=4\),根据余数的定义,可以得出 \(-9 \bmod (-2)=-9-4*(-2)=-1\)。(负负得负?)
#include <cstdio> #include <algorithm> using namespace std; int a[35],cnt; int main() { int n; scanf("%d",&n); if(n==0)printf("0"); else { while(n!=0) { a[++cnt]=abs(n%2); if(n>=0)n/=-2; else n=(n-1)/(-2); } for(int i=cnt;i>=1;i--) printf("%d",a[i]); } return 0; }
D – Candy Distribution
大意
给一个长度为 \(n\) 的序列,求其中连续子段和恰好为 \(m\) 的倍数的子段的个数。
题解
先处理前缀和并对 \(m\) 取模,然后就是计数问题了。
显然,当 \(a[j]=a[i]=k\) 时,两者之间的子段一定是 \(m\) 的倍数。我们只需将所有余数记录下来,就可以处理出答案。
#include <iostream> #include <map> using namespace std; long long n,m,a[100005],c[100005]; map<long long,long long> mp; int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { c[i]=c[i-1]+a[i]; c[i]%=m; mp[c[i]]++; } long long ans=mp[0]; if(mp[0]>1)ans+=mp[0]*(mp[0]-1)/2;//前缀和相同的可以两两配对 mp[0]=0; for(int i=1;i<=n;i++) if(mp[c[i]]) ans+=mp[c[i]]*(mp[c[i]]-1)/2,mp[c[i]]=0; cout<<ans; return 0; }