Codeforces#441 Div.2 四小题
A. Trip For Meal
小熊维尼喜欢吃蜂蜜。他每天要在朋友家享用N次蜂蜜 ， 朋友A到B家的距离是 a ，A到C家的距离是b ，B到C家的距离是c （A- >Rabbit B- >Owl C ->Eeyore），他不能连续两顿饭都在同一位朋友家里蹭
他现在位于A的家里， 请问他一天最少要跑多少路。
当然是要找一条最短的路折返跑了啊,是不是很简单。
#include<bits/stdc++.h>
using namespace std;
int N,a,b,c;
int main()
{
cin>>N>>a>>b>>c;
if (N==)printf("0\n");
else if (N==)printf("%d\n",min(a,b));
else if (N>=){
int k=min(a,b);
if(k<=c)
printf("%d\n",(N-)*k);
else printf("%d\n",k+(N-)*c);
}
return ;
}
A
B. Divisiblity of Differences
给你一个有N个元素的可重集合，你需要找出一个含k个元素的子集，使里面的数两两的差都能被m整除
差 + 整除 -> 同余 -> 子集中的数对m同余
每个数都mod m 然后枚举余数就好了。
#include<bits/stdc++.h>
using namespace std;
int N,M,K,a[],vis[],ans=-;
int main()
{
scanf("%d%d%d",&N,&K,&M);
for(int i=;i<=N;i++){
scanf("%d",&a[i]);
vis[a[i]%M]++;
}
for(int i=;i<M;i++){
if(vis[i]>=K){
ans=i;
break;
}
}
if(ans!=-){
printf("Yes\n");
for(int i=;i<=N&&K;i++)
if(a[i]%M==ans)printf("%d ",a[i]),K--;
printf("\n");
}
else printf("No\n");
}
B
C. Classroom Watch
先定义一个f(x) ， f(x)的值就是 x的每一位加在一起 在加上它本身 f(123)=1+2+3+123=129
给你一个int范围内的整数N，求满足f(x)=N 的x有多少 和这些x的值
最多就十位数 各数位的数加在一起也超不过100 于是就 枚举 N-100~N 的所有数
#include<bits/stdc++.h>
using namespace std;
int N,ans[],cnt;
void judge(int x)
{
int sum=x,i=x;
while(i){
sum+=i%;
i=i/;
}
if(sum==N)ans[++cnt]=x;
}
int main()
{
scanf("%d",&N);
for(int i=N->=?N-:;i<=N;i++){
judge(i);
}
printf("%d\n",cnt);
for(int i=;i<=cnt;i++)
printf("%d\n",ans[i]);
return ;
}
C
D. Sorting the Coins
每次就是寻找最后一个O前面有多少x ，很容易 ，看到有人拿树状数组什么的其实没必要 ，这个尤其好维护，而且很水
#include<bits/stdc++.h>
using namespace std;
int N,a[],vis[],ans;
int main()
{
scanf("%d",&N);
printf("1 ");
int zer=N;
for(int i=;i<=N;i++){
scanf("%d",&a[i]);
vis[a[i]]=;
if(a[i]>zer){
printf("%d ",ans+);
}
else{
ans++;
while(vis[zer])ans--,zer--;
printf("%d ",ans+);
}
}
return ;
}
D