Atcoder Beginner Contest 105

第一次参加了一回Atcoder的比赛,感觉ABC的题目还真不是一般的水啊…

题目链接

https://beta.atcoder.jp/contests/abc105

A – AtCoder Crackers

大意

将\(n\)个物品分给\(k\)个人,问分到最多物品的人和最少物品的人,他们物品数量的差最小是多少。

题解

显然,\(n \mod 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 \mod (-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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注