Loading [MathJax]/extensions/tex2jax.js

Atcoder Beginner Contest 105

题目链接

https://atcoder.jp/contests/abc105

A – AtCoder Crackers

大意

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

题解

显然,\(n \bmod k=0\) 时答案为 0,否则答案为 1。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include <stdio.h>
int main()
{
int n,k;
scanf("%d%d",&n,&k);
if(n%k)puts("1");
else puts("0");
return 0;
}
#include <stdio.h> int main() { int n,k; scanf("%d%d",&n,&k); if(n%k)puts("1"); else puts("0"); return 0; }
#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\) 是否有自然数解。

题解

不得不说,小凯的疑惑要比这道题高出好几个档次了吧。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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\)。(负负得负?)

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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\) 的倍数。我们只需将所有余数记录下来,就可以处理出答案。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理