AtCoder Beginner Contest 114 Solution
分类:
IT文章
•
2022-05-16 11:10:45
A 753
Solved.
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int mp[10];
5
6 int main()
7 {
8 mp[7] = mp[5] = mp[3] = 1;
9 int x; cin >> x;
10 puts(mp[x] ? "YES" : "NO");
11 }
View Code
B 754
Solved.
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 char s[20];
5
6 int f(int x)
7 {
8 int res = 0;
9 for (int i = 0; i < 3; ++i) res = res * 10 + s[i + x] - '0';
10 return res;
11 }
12
13 int main()
14 {
15 while (scanf("%s", s + 1) != EOF)
16 {
17 int res = 0x3f3f3f3f, len = strlen(s + 1);
18 for (int i = 1; i <= len - 2; ++i) res = min(res, abs(f(i) - 753));
19 printf("%d
", res);
20 }
21 return 0;
22 }
View Code
C 755
Solved.
题意：
找出$[1, n]中有多少个只由'7', '5', '3' 组成，并且每个字符至少出现一次的数$
思路：
这样的数不会太多，DFS构造，然后二分
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 vector <int> v;
5
6 bool ok(int x)
7 {
8 int flag[10] = {false};
9 while (x)
10 {
11 flag[x % 10] = 1;
12 x /= 10;
13 }
14 if (flag[3] == 0 || flag[5] == 0 || flag[7] == 0) return false;
15 return true;
16 }
17
18 void DFS(int cur, int num)
19 {
20 if (cur == 10)
21 {
22 if (ok(num)) v.push_back(num);
23 return;
24 }
25 DFS(cur + 1, num);
26 DFS(cur + 1, num * 10 + 3);
27 DFS(cur + 1, num * 10 + 5);
28 DFS(cur + 1, num * 10 + 7);
29 }
30
31 int main()
32 {
33 DFS(0, 0);
34 sort(v.begin(), v.end());
35 v.erase(unique(v.begin(), v.end()), v.end());
36 int n;
37 while (scanf("%d", &n) != EOF) printf("%d
", (int)(upper_bound(v.begin(), v.end(), n) - v.begin()));
38 return 0;
39 }
View Code
Upsolved.
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int n;
5 int cnt[110];
6 int tot[2100];
7
8 int f(int l, int r)
9 {
10 int res = 0;
11 for (int i = l; i <= r; ++i) res += tot[i];
12 return res;
13 }
14
15 int main()
16 {
17 while (scanf("%d", &n) != EOF)
18 {
19 memset(cnt, 0, sizeof cnt);
20 memset(tot, 0, sizeof tot);
21 for (int i = 2; i <= n; ++i)
22 {
23 int tmp = i;
24 for(int j = 2; ; ++j)
25 {
26 while (tmp % j == 0)
27 {
28 ++cnt[j];
29 tmp /= j;
30 }
31 if (tmp == 1) break;
32 }
33 }
34 for (int i = 2; i <= 100; ++i) ++tot[cnt[i] + 1];
35 int res = f(75, 2000);
36 res += f(25, 2000) * f(3, 24);
37 res += f(25, 2000) * (f(25, 2000) - 1);
38 res += f(15, 2000) * f(5, 14);
39 res += f(15, 2000) * (f(15, 2000) - 1);
40 res += (f(5, 2000) * (f(5, 2000) - 1) / 2) * f(3, 4);
41 res += ((f(5, 2000) * (f(5, 2000) - 1) / 2) * (f(5, 2000) - 2));
42 printf("%d
", res);
43 }
44 return 0;
45 }
