single dog

115 阅读 0 评论 76 点赞

我是靠谱客的博主畅快楼房，这篇文章主要介绍single dog，现在分享给大家，希望可以做个参考。

假如没有情侣存在，那么单身狗一定是一个非常恐怖的生物。他们可以去电影院最多一人占据3个座位（大概是因为他们不愿意和别人坐在相邻的位置）难以想象他们为什么会有这么强大的战斗力。

那么问题来了。

假如一只单身狗的ID十进制下表示为N，在D进制下，他的战斗力为数字x出现的次数，而他的最大战斗力，则是所有进制下的战斗力中最大的那个。

n不大于10000， x为0到9中的一个数。D大于等于2.

给出n和x，问这只单身狗的战斗力。

样例输入：

3 1

样例输出：

2

这是一道好题:)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
int singledog(int n, int x) {
int d, i = 0, a[10000] = {0}, maxfight = 0;
for (d = x+1; d <= n; d++) {
int temp, m = n;
while (m != 0) {
temp = m % d;
if (temp == x) a[i] = a[i] + 1;
m = m / d;
}
if (a[i] > maxfight) maxfight = a[i];
i++;
}
printf("%dn", maxfight);
}
int main() {
int n, x;
scanf("%d%d", &n, &x);
singledog(n, x);
return 0;
}

然而上面这段代码在数据大的时候会超时、、、╥﹏╥…

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
int MAX(int a, int b) {
return a > b ? a : b;
}
int sol(int n, int d, int x) {
int tmp, sum = 0;
while (n > 0) {
tmp = n % d;
if (tmp == x) sum++;
n /= d;
}
return sum;
}
int main() {
int n, x, i;
scanf("%d%d", &n, &x);
int ans = 0;
for (i = 2; i <= n+1; i++) {
ans = MAX(sol(n, i, x), ans);
}
printf("%dn", ans);
return 0;
}