口胡笔记_ AtCoder AGC 021的几道水(神)题[贪心, 清奇脑回路]

AtCoder的题挺有趣的…

A

签到题, 让9尽量多就可以啦

考虑到对答案的贡献显然是9越多越好…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (20 + 5)
#define LL long long
using namespace std;
int main()
{
LL n;
scanf("%lld", &n);
LL dq = 0, wz = 1, ans = 0;
for (; dq + wz * 9 <= n; )
{
dq += wz * 9;
wz *= 10;
ans += 9;
}
for (int i = 9; i; i--)
{
if (dq + wz * i <= n)
{
ans += i;
break;
}
}
printf("%lld", ans);
return 0;
}

B

C

D

By Cansult