Atcoder Beginner Contest 105

题目链接

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;
}