蓝桥杯打卡-Day1

发表于 分类于 ，

国赛2021-纯质数

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个正整数只有 1 和它本身两个约数，则称为一个质数（又称素数）。

前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · ·。

如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如2,3,5,7,23,37 都是纯质数，而 11, 13, 17, 19, 29, 31不是纯质数。当然 1, 4, 35也不是纯质数。

请问，在 11 到 20210605中，有多少个纯质数？

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M

这是一个填空题，直接输出答案 1903 就行，直接暴力解决。下面是计算的代码。

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
31
32
33
34
35
#include <iostream>
using namespace std;

const int N = 20210605;

bool prime[N + 10];

bool isprime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;

    return true;
}

bool ischun(int n) {
    while (n) {
        int t = n % 10;
        if (t == 1 || t == 4 || t == 6 || t == 8 || t == 9 || t == 0)
            return false;
        n /= 10;
    }
    return true;
}

int main() {
    int res = 0;
    for (int i = 2; i < N; i++) {
        if (isprime(i) && ischun(i)) {
            res++;
        }
    }
    cout << res << endl;
    return 0;
}

2021省赛-最小筹码

问题描述

你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。

输入格式

输入包含一个正整数 N。

输出格式

输出一个整数代表答案。

样例输入

1
7

样例输出

1
3

样例说明

3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。

1 = 1；

2 = 6 − 4(天平一边放 6 ，另一边放 4 ）；

3 = 4 − 1；

4 = 4；

5 = 6 − 1；

6 = 6；

7 = 1 + 6；

少于 3 个砝码不可能称出 1 至 7 的所有重量。

评测用例规模与约定

对于所有评测用例，1 ≤ N ≤ 1000000000。

似乎是比较简单的贪心，为啥我是看了题解才勉强会写呢…

贪心思路：

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
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;

LL cnt;
LL sum;
LL res;

int main() {
    LL n;
    cin >> n;
    for (int i = 0; i < 0x3f3f3f; i++) {
        sum += pow(3, i);
        if (sum >= n) {
            res = i;
            break;
        }
    }

    cout << res + 1 << endl;
    return 0;
}

2021模拟赛-灌溉

题目描述

小蓝负责花园的灌溉工作。

花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。

小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。

每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。

给定花园水管的位置，请问 k 分钟后，有多少个方格被灌溉好？

输入描述

输入的第一行包含两个整数 n, m。

第二行包含一个整数 t ，表示出水管的数量。

接下来 t 行描述出水管的位置，其中第 i 行包含两个数 r, c 表示第 r 行第 c 列有一个排水管。

接下来一行包含一个整数 k。

其中，1 \leq n, m \leq 100, 1 \leq t \leq 10, 1 \leq k \leq 1001≤n,m≤100,1≤t≤10,1≤k≤100。

输出描述

输出一个整数，表示答案。

输入输出样例

示例 1

输入

1
2
3
4
5
3 6
2
2 2
3 4
1

输出

1
9

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 128M
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;

const int N = 110;
// 偏移量
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
// 队列
typedef pair<int, int> PII;
queue<PII> q;
bool watered[N][N];

int n, m, t, k;

int cnt;
void water() {
    // 第一个元素
    auto sign = q.front();
    q.push(q.front());
    do {
        auto t = q.front();
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i];
            int y = t.y + dy[i];
            // 如果越界
            if (x < 0 || x > n || y < 0 || y > m) continue;
            // 如果已经灌溉过了
            if (watered[x][y]) continue;
            // 如果没有
            watered[x][y] = true;
            cnt++;
            q.push({x, y});
        }
        q.pop();
    } while (q.front() != sign);
}

int main() {
    scanf("%d%d%d", &n, &m, &t);
    while (t--) {
        int r, c;
        scanf("%d%d", &r, &c);
        watered[r][c] = true;
        q.push({r, c});
        cnt++;
    }
    scanf("%d", &k);
    // 每一个 k 就是一次灌溉的过程
    while (k--) {
        water();
    }
    printf("%d", cnt);
    return 0;
}