记录生活中的美

发表于 更新于 分类于 ，

金币-2015NOIP普及组

https://www.lanqiao.cn/problems/357/learning/

题目描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 N 天每天收到 N 枚金币后，骑士会在之后的连续 N+1 天里，每天收到 N+1 枚金币。

请计算在前 K 天里，骑士一共获得了多少金币。

输入描述

输入只有 1 行，包含一个正整数 K （1≤K≤10^4），表示发放金币的天数。

输出描述

输出只有 1 行，包含一个正整数，即骑士收到的金币数。

输入输出样例

示例 1

输入

1
6

输出

1
14

示例 2

输入

1
1000

输出

1
29820

暴力模拟即可，注意这个150，等差数列求和公式(1+n)*n/2 = 10000，解出来141。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 1e5;
int money[N];

void get_money() {
    int cnt = 1;
    for (int i = 1; i < 150; i++)
        for (int j = 1; j <= i; j++) money[cnt++] = i;
}
int main() {
    get_money();
    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++) res += money[i];
    cout << res << endl;
    return 0;
}

优秀的拆分-2020CSP-J

https://www.lanqiao.cn/problems/801/learning/

题目描述

一般来说，一个正整数可以拆分成若干个正整数的和。

例如，1=1，10=1+2+3+4 等。对于正整数 n 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n 被分解为了若干个不同的 2 的正整数次幂。注意，一个数 x 能被表示成 2 的正整数次幂，当且仅当 x 能通过正整数个 2 相乘在一起得到。

例如，10=8+2=2

3+2

1是一个优秀的拆分。但是，7=4+2+1=2

2+2

1+2

0 就不是一个优秀的拆分，因为 1 不是 2 的正整数次幂。

现在，给定正整数 n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

输入描述

输入只有一行，一个整数 n (1≤n≤10

7)，代表需要判断的数。

输出描述

如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。

若不存在优秀的拆分，输出 -1。

输入输出样例

示例 1

输入

1
6

输出

1
4 2

示例 2

输入

1
7

输出

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

int cnt = 1;
int pow2[30];
int rescnt = 1;
int res[30];

void get2() {
    for (int i = 1; pow2[cnt - 1] < 1e7 + 10; i++) pow2[cnt++] = pow(2, i);
}

int main() {
    int n;
    cin >> n;
    get2();

    int rest = n;

    for (int i = cnt; i > 0; i--)
        if (pow2[i] <= rest) rest -= pow2[i], res[rescnt++] = pow2[i];

    if (rest == 0)
        for (int i = 2; i < rescnt; i++) cout << res[i] << ' ';
    else
        cout << -1 << endl;

    return 0;
}

穿越雷区

http://lx.lanqiao.cn/problem.page?gpid=T2818

蓝肽子序列-2020国赛

https://www.lanqiao.cn/problems/1030/learning/

题目描述

L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。

生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。

具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。

在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。

如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。

给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。

输入描述

输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。

其中有 ，两个字符串的长度均不超过 1000。

输出描述

输出一个整数，表示最长的那个公共蓝肽子序列的长度。

输入输出样例

示例

输入

1
2
LanQiaoBei
LanTaiXiaoQiao

输出

1
2

发表于 分类于 ，

算式900-2017省赛

https://www.lanqiao.cn/problems/649/learning/

暴力dfs解决 答案是(6048-5973)*12=900。

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
#include <iostream>
using namespace std;
int st[10];
int n[10];

void dfs(int u)
{
  if(u > 9)
  {
    // 0 1 2 3
    int a = n[0] * 1000 + n[1] * 100 + n[2] * 10 + n[3];
    // 4 5 6 7
    int b = n[4] * 1000 + n[5] * 100 + n[6] * 10 + n[7];
    // 8 9
    int c = n[8] * 10 + n[9];
    if((a - b) * c == 900)
      cout << a << ' ' << b << ' ' << c << endl;
  }  
  else
  {
      for(int i = 0;i < 10;i ++)
      {
        if(st[i]) continue;

        st[i] = true;
        n[u] = i;
        dfs(u + 1);

        st[i] = false;
      }

  }
}

int main()
{
  dfs(0);
  return 0;
}

谈判

https://www.lanqiao.cn/problems/545/learning/

输入输出样例
示例 1
输入

1
2
4
9 1 3 5

输出

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

const int N = 1010;
int b[N];

int main() 
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> b[i];

    sort(b, b + n);

    int now = b[0] + b[1];
    int sum = now;
    
    for (int i = 2; i < n; i++)
    {
      now += b[i];
      sum += now;
    }


    cout << sum << endl;

    return 0;
}

幸运数-2013省赛

https://www.lanqiao.cn/problems/214/learning/

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

const int N = 1e6 + 10;
bool l[N];
int idx[N];

void makeLucky() {
    int index = 1;
    for (int i = 1; i < 100; i++) {
        if (l[i]) continue;
        // 记录是第几个幸运数字
        idx[i] = index++;
        // 开始删除数字
        int cnt = 0;
        for (int j = i + 1; j < 1e6 + 5; j++) {
            // 如果已经被删除了
            if (l[j]) continue;
            // 计数器
            cnt++;
            // 删除数字
            if (cnt % idx[i] == 0) l[j] = true;
        }
    }
}

int main() {
    int m, n;
    cin >> m >> n;

    makeLucky();

    int cnt = 0;

    for (int i = 0; i < N; i++) {
        if (i >= n) break;
        if (!l[i] && i >= m) cnt++;
    }

    for (int i = 1; i < 100; i++)
        if (!l[i]) cout << i << ' ';
    cout << cnt << endl;

    return 0;
}

123-2021国赛

https://www.lanqiao.cn/problems/1591/learning/

1

发表于 更新于 分类于 ，

1.带分数（全排列） https://www.lanqiao.cn/problems/208/learning/

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
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long n;           // 这是目标
int cnt;          // 计数器
bool number[10];  // 1-9 代表九位数字,flase 表示没用过，true 表示用过了
int state[10];      // 表示10位数字
long a, b, c, tmp;  // n=100 * c == a * c + b
void dfs(int u) {
    // 如果大于9，就代表穷举数字结束了，9 个位置都有数字s了
    if (u > 9) {
        /* dfs 测试语句
        for (int i = 1; i <= 9; i++) printf("%d", state[i]);
        puts("");
        */
        //那现在就是把这数字分割开来，分成 a, b,c 三部分
        // 先砍一刀在ab之间，目的是把 a 分出来
        for (int ab = 1; ab <= 9; ab++) {
            //再砍一刀，把 b 分出来
            for (int bc = ab + 1; bc <= 9; bc++) {
                int a = 0, b = 0, c = 0;
                tmp = ab;
                for (tmp; tmp != 0; tmp--) {
                    a = a * 10 + state[tmp];
                    if (a >= n) break;  // 剪枝
                }
                // cout << "a=" << a << endl;
                tmp = bc;
                for (tmp; tmp != ab; tmp--) {
                    b = b * 10 + state[tmp];
                }
                // cout << "b=" << b << endl;
                tmp = 9;
                for (tmp; tmp != bc; tmp--) {
                    c = c * 10 + state[tmp];
                }
                // cout << "c=" << c << endl;

                // cout << a << " " << b << " " << c << endl;
                //    都选择完了，那就看看是不是符合条件喽
                if (n * c == a * c + b) {
                    cnt++;
                    return;
                }
            }
        }
    }
    // 否则没结束，还有位数是空的
    // 先把 u 这一位的数字给确定了
    for (int i = 1; i <= 9; i++) {
        if (!number[i]) {
            // 如果没用过，就往下递推
            number[i] = true;
            state[u] = i;
            dfs(u + 1);
            number[i] = false;
        }
    }
}
int main() {
    scanf("%ld", &n);
    //这个意思表示第一位，123456789，总共九位
    dfs(1);
    printf("%d", cnt);
    return 0;
}
2.走迷宫（bfs）https://www.lanqiao.cn/problems/1216/learning/


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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;
const int N = 110;
int n, m;

int map[N][N];
int idx[N][N];

int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

void bfs(int x1, int y1, int x2, int y2) {
    memset(idx, -1, sizeof idx);
    queue<PII> q;
    q.push({x1, y1});
    idx[x1][y1] = 0;
    while (!q.empty()) {
        auto t = q.front();
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 1 && y < 1 && x > m && y > n) continue;
            if (map[x][y] == 0) continue;
            if (idx[x][y] != -1) continue;
            idx[x][y] = idx[t.x][t.y] + 1;
            q.push({x, y});
            if (x == x2 && y == y2) return;
        }
        q.pop();
    }
    return;
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) scanf("%d", &map[i][j]);

    int x1, y1, x2, y2;

    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

    bfs(x1, y1, x2, y2);

    if (idx[x2][y2] != -1)
        printf("%d\n", idx[x2][y2]);
    else
        printf("-1\n");

    return 0;
}

3.蓝桥幼儿园（并查集）https://www.lanqiao.cn/problems/1135/learning/
4.跳石头（贪心+二分）https://www.lanqiao.cn/problems/364/learning/

发表于 分类于 ，

巧排扑克牌-2012省赛

https://www.lanqiao.cn/problems/735/learning/

题目描述

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

小明刚上小学，学会了第一个扑克牌“魔术”，到处给人表演。魔术的内容是这样的：

他手里握着一叠扑克牌：A，2，….J，Q，K 一共 13 张。他先自己精心设计它们的顺序，然后正面朝下拿着，开始表演。

只见他先从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是 A；然后再从最下面拿一张放到最上面，再从最下面拿一张翻开放桌子上，是 2；……如此循环直到手中只有一张牌，翻开放桌子上，刚好是 K。

这时，桌上牌的顺序是：A,2,3,4,5,6,7,8,9,10,J,Q,K

请你计算一下，小明最开始的时候手里牌的顺序是怎样的。

把结果写出来，逗号分割，小明“魔术”开始时，最下面的那张牌输出为第一个数据。

1

质数拆分-2019国赛

https://www.lanqiao.cn/problems/809/learning/

题目描述

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

将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？

注意交换顺序视为同一种方法，例如 2 + 2017 = 2019 与 2017 + 2 = 2019 视为同一种方法。

1

日志统计-2018省赛

https://www.lanqiao.cn/problems/179/learning/

题目描述

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。其中每一行的格式是：

ts id

表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入描述

输入格式：

第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts 和 id。

输出描述

按从小到大的顺序输出热帖 id。每个 id 一行。

输入输出样例

示例

输入

1
2
3
4
5
6
7
8
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出

1
2
1
3
1

递增三元组-九省赛

http://lx.lanqiao.cn/problem.page?gpid=T2728
　　给定三个整数数组
　　A = [A1, A2, … AN],
　　B = [B1, B2, … BN],
　　C = [C1, C2, … CN]，
　　请你统计有多少个三元组(i, j, k) 满足：
　　1. 1 <= i, j, k <= N
　　2. Ai < Bj < Ck
输入格式
　　第一行包含一个整数N。
　　第二行包含N个整数A1, A2, … AN。
　　第三行包含N个整数B1, B2, … BN。
　　第四行包含N个整数C1, C2, … CN。

　　对于30%的数据，1 <= N <= 100
　　对于60%的数据，1 <= N <= 1000
　　对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
输出格式
　　一个整数表示答案
样例输入
3
1 1 1
2 2 2
3 3 3
样例输出
27

1

外卖店优先级

https://www.lanqiao.cn/problems/184/learning/

题目描述

“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中?

输入描述

第一行包含 3 个整数 N,M,T。

以下 MM 行每行包含两个整数 ts,id，表示 ts 时刻编号 id 的外卖店收到一个订单。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

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

输出

1
1

样例解释：

6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。

1

发表于 分类于 ，

猴子分香蕉-2018省赛

https://www.lanqiao.cn/problems/618/learning/

题目描述

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

5 只猴子是好朋友，在海边的椰子树上睡着了。这期间，有商船把一大堆香蕉忘记在沙滩上离去。

第 1 只猴子醒来，把香蕉均分成 5 堆，还剩下 1 个，就吃掉并把自己的一份藏起来继续睡觉。

第 2 只猴子醒来，把香蕉均分成 5 堆，还剩下 2 个，就吃掉并把自己的一份藏起来继续睡觉。

第 3 只猴子醒来，把香蕉均分成 5 堆，还剩下 3 个，就吃掉并把自己的一份藏起来继续睡觉。

第 4 只猴子醒来，把香蕉均分成 5 堆，还剩下 4 个，就吃掉并把自己的一份藏起来继续睡觉。

第 5 猴子醒来，重新把香蕉均分成 5 堆，哈哈，正好不剩！

请计算一开始最少有多少个香蕉。

暴力解决，答案是3141。

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
#include <iostream>
using namespace std;
int main() {
    // 假设开始有n个
    for (int i = 0; i < 1000000; i++) {
        int n = i;
        // 第一只
        if (n > 0 && n % 5 == 1)
            n = n - n / 5 - 1;
        else
            continue;
        // 第二只
        if (n > 0 && n % 5 == 2)
            n = n - n / 5 - 2;
        else
            continue;
        // 第三只
        if (n > 0 && n % 5 == 3)
            n = n - n / 5 - 3;
        else
            continue;
        // 第四只
        if (n > 0 && n % 5 == 4)
            n = n - n / 5 - 4;
        else
            continue;
        // 最后一只
        if (n > 0 && n % 5 == 0) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

等差数列-2019省赛

https://www.lanqiao.cn/problems/192/learning/

题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入描述

输入的第一行包含一个整数 N。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

1
2
5
2 6 4 10 20

输出

1
10

样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。

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

const int N = 1e5 + 10;
int a[N];
// 0 和另一个数的最大公约数都是另一个数
int d = 0;

// 欧几里得算法求最大公约数，这个需要背诵
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    sort(a, a + n);

    if (a[0] == a[n - 1]) {
        // 如果首尾相同的
        printf("%d", n);
    } else {
        // 否则就求他们的最小公倍数
        for (int i = 0; i < n - 1; i++) d = gcd(d, a[i + 1] - a[i]);
        // cout << d << endl;
        // 求队列
        cout << ((a[n - 1] - a[0]) / d) + 1 << endl;
    }

    return 0;
}

平方序列-2019国赛

https://www.lanqiao.cn/problems/808/learning/

题目描述

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

小明想找到两个正整数 X 和 Y，满足

  1. 2019 < X < Y;

请你求出在所有可能的解中，X + Y 的最小值是多少？

暴力解决，答案是7020。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
#include <iostream>
using namespace std;

int res = 0x3f3f3f;

int main() {
    for (int x = 2019 + 1; x < 100000; x++)
        for (int y = x + 1; y < 100000; y++) {
            if ((y * y - x * x) == (x * x - 2019 * 2019)) {
                res = min(x + y, res);
            }
        }
    cout << res << endl;
    return 0;
}

倍数问题-2018省赛

https://www.lanqiao.cn/problems/168/learning/

题目描述

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。

输入描述

第一行包括 2 个正整数 n, K。

第二行 n 个正整数，代表给定的 n 个数。

输出描述

输出一行一个整数代表所求的和。

输入输出样例

示例

输入

1
2
4 3
1 2 3 4

输出

1
9
1
不会

发表于 分类于 ，

奇数倍数-2019国赛

https://www.lanqiao.cn/problems/818/learning/

题目描述

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

请你找到最小的整数 X 同时满足：

  1. X 是 2019 的整倍数；
  2. X 的每一位数字都是奇数。

运行限制

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

暴力解决，答案是139311.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

bool check(int x) {
    while (x) {
        if (x % 2 == 0) return false;
        x /= 10;
    }
    return true;
}

int main() {
    for (int i = 2019; i;) {
        if (check(i)) {
            cout << i << endl;
            break;
        }
        i += 2019;
    }
    return 0;
}

第几个幸运数字-2018省赛

https://www.lanqiao.cn/problems/613/learning/

题目描述

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

到 X 星球旅行的游客都被发给一个整数，作为游客编号。

X 星的国王有个怪癖，他只喜欢数字 3,5 和 7。

国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。

我们来看前 10 个幸运数字是：

3 5 7 9 15 21 25 27 35 45

因而第 11 个幸运数字是： 49

小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505 是第几个幸运数字。

运行限制

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

这个题目只能顺着它的意思，从低到高次分别求3 5 7到乘方，再相乘，用来组成一个幸运数字。
而不能反过来枚举 1 - N ，分别对 3/5/7 求余···。这是为什么呢？
提示-有个东西叫质数。

答案是1905。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cmath>
#include <iostream>
using namespace std;

typedef long long LL;
const LL N = 59084709587505;
LL cnt;

int main() {
    for (int i = 0; pow(3, i) <= N; i++)
        for (int j = 0; pow(5, j) <= N; j++)
            for (int k = 0; pow(7, k) <= N; k++)
                if (pow(3, i) * pow(5, j) * pow(7, k) <= N) cnt++;
    cout << cnt - 1 << endl;
    return 0;
}

四平方和-2016省赛

http://lx.lanqiao.cn/problem.page?gpid=T2766
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。

比如：

（^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开

例如，输入：
5
则程序应该输出：
0 0 1 2

再例如，输入：
12
则程序应该输出：
0 2 2 2

再例如，输入：
773535
则程序应该输出：
1 1 267 838

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
#include <iostream>
#include <unordered_map>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;
const int N = 5000000;
int n;
unordered_map<int, PII> m;
int a, b, c, d;

int main() {
    cin >> n;
    // 首先枚举后面两个大的c d
    for (int c = 0; c * c <= n; c++)
        for (int d = c; c * c + d * d <= n; d++) {
            int res = c * c + d * d;
            m[res] = {c, d};
        }
    
    // 再枚举前面两个
    for (int a = 0; a * a <= n; a++)
        for (int b = a; a * a + b * b <= n; b++) {
            int cd = n - a * a - b * b;
            if (m.find(cd) != m.end()) {
                cout << a << ' ' << b << ' ' << m[cd].x << ' ' << m[cd].y
                     << endl;
                return 0;
            }
        }

    return 0;
}

迷宫-2019省赛

https://www.lanqiao.cn/problems/602/learning/

题目描述

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

下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。

1
2
3
4
010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。

请注意在字典序中 D<L<R<U。

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
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

运行限制

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

找路bfs_find写出来了，但是回溯输出路径改了半天也不对…
先这样吧，有空了再改。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 60;
char m[N][N];
bool visited[N][N];
int dist[N][N];

int dx[4] = {0, -1, 1, 0}, dy[4] = {-1, 0, 0, 1};
char dists[4] = {'L', 'D', 'U', 'R'};
vector<char> road;

// 这是找路的 bfs
void bfs_find(int x, int y) {
    queue<PII> q;
    q.push({x, y});
    dist[x][y] = 0;
    while (!q.empty()) {
        auto u = q.front();
        visited[u.x][u.y] = true;
        for (int i = 0; i < 4; i++) {
            int ax = u.x + dx[i], ay = u.y + dy[i];
            if (visited[ax][ay]) continue;
            // 如果越界
            if (ax < 0 || ax > 3 || ay < 0 || ay > 5) continue;
            // 只要不是路，就退出
            if (m[ax][ay] != '0') continue;
            // 再加入之前判重
            if (dist[x][y] != 0) continue;
            // 路
            dist[ax][ay] = dist[u.x][u.y] + 1;
            // 如果到了，就退出
            if (ax == 3 && ay == 5) return;
            q.push({ax, ay});
        }
        q.pop();
    }
    return;
}

// 根据找路得到的dist，从迷宫出口回溯找周围dist - 1的格子，把路径放在vector里
void bfs_road(int x, int y) {
    queue<PII> q;
    q.push({x, y});
    while (!q.empty()) {
        auto u = q.front();
        for (int i = 0; i < 4; i++) {
            // 计算地址
            int x = u.x + dx[i], y = u.y + dy[i];
            // 如果找到了dist-1
            if (dist[x][y] == dist[u.x][u.y] - 1) {
                // 就把这个对应的符号加进去
                road.push_back(dists[i]);
                // 入列
                q.push({x, y});
                // 不用找了，因为旁边肯定只有一个dist - 1的点
                break;
            }
            // 如果到了，就退出
            if (x == 0 && y == 0) return;
        }
        q.pop();
    }
    return;
}

int main() {
    memset(m, -1, sizeof m);
    for (int i = 0; i < 4; i++) cin >> m[i];
    bfs_find(0, 0);
    bfs_road(3, 5);
    for (int i = road.size(); i >= 0; i--) {
        printf("%c", road[i]);
    }
    cout << dist[3][5] << endl;
    return 0;
}

发表于 分类于 ，

年龄巧合-2014国赛

https://www.lanqiao.cn/problems/694/learning/

题目描述

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

小明和他的表弟一起去看电影，有人问他们的年龄。小明说：今年是我们的幸运年啊。我出生年份的四位数字加起来刚好是我的年龄。表弟的也是如此。已知今年是 2014 年，并且，小明说的年龄指的是周岁。

请推断并填写出小明的出生年份。

运行限制

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

直接暴力解决，算出来两个数1988和2006。
问的是小明的出生日期（而不是他弟弟的，那当然是1988了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
// 开始时间
const int START = 1950;
const int NOW = 2014;

int age(int n) {
    int ages = 0;
    while (n) {
        ages += n % 10;
        n /= 10;
    }
    return ages;
}

int main() {
    for (int i = START; i < NOW; i++)
        if ((NOW - i) == age(i)) cout << i << endl;
    return 0;
}

纸牌三角形-2014省赛

https://www.lanqiao.cn/problems/639/learning/

题目描述

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

A,2,3,4,5,6,7,8,9 共 9 张纸牌排成一个正三角形（A 按 1 计算）。要求每个边的和相等。 下图就是一种排法。

这样的排法可能会有很多。

如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？

请你计算并提交该数字。

运行限制

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

暴力 DFS 即可
解释一下最后为啥是/ 6：
三边可以互换位置要/ 3，每一次旋转都有左右颠倒两种可能所以还要/ 2。
题目只说旋转和镜像是同一种，所以中间两个数互换位置是两种情况哦，不需要减去。

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

const int MAX = 7 + 8 + 9 + 10;
bool used[10];
// 用来模拟金字塔的树组
int w[10];
// 计数
int cnt;

// 现在在选第几位
void dfs(int u) {
    // 现在选的如果超过第 9 位
    if (u > 9) {
        //  那就判断是否符合条件
        int f1 = w[1] + w[2] + w[3] + w[4];
        int f2 = w[4] + w[5] + w[6] + w[7];
        int f3 = w[7] + w[8] + w[9] + w[1];
        // 如果符合就加一
        if (f1 == f2 && f2 == f3) cnt++;
        return;
    } else {
        // 如果没过，就循环选择这个位数上的数字
        for (int i = 1; i <= 9; i++)
            // 如果这个数字没用过
            if (!used[i]) {
                // 选择它
                used[i] = true;
                w[u] = i;
                dfs(u + 1);
                // 选完了记得还原现场
                used[i] = false;
                w[u] = 0;
            }
    }
}

int main() {
    dfs(1);
    cout << cnt / 6 << endl;
    // 三边可以互换位置要`/ 3`，每一次旋转都有左右颠倒两种可能所以还要`/ 2`。
    return 0;
}

取球游戏-2012省赛

https://www.lanqiao.cn/problems/278/learning/

题目描述

今盒子里有 n 个小球，A、B 两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。

我们约定：

每个人从盒子中取出的球的数目必须是：1，3，7 或者 8 个。轮到某一方取球时不能弃权！A 先取球，然后双方交替取球，直到取完。被迫拿到最后一个球的一方为负方（输方）

请编程确定出在双方都不判断失误的情况下，对于特定的初始球数，A 是否能赢？

输入描述

先是一个整数 n (n<100)，表示接下来有 n 个整数。

然后是 n 个整数，每个占一行（整数< 10^4），表示初始球数。

输出描述

程序则输出 n 行，表示 A 的输赢情况（输为 0，赢为 1）。

输入输出样例

示例

输入

1
2
3
4
5
４
１
２
10
18

输出

1
2
3
4
0
1
1
0

运行限制

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

发表于 分类于 ，

1.排他平方数-2013省赛

https://www.lanqiao.cn/problems/712/learning/

题目描述

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

小明正看着 203879203879 这个数字发呆。

原来，203879 * 203879 = 41566646641。

这有什么神奇呢？仔细观察，203879 是个 6 位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。

具有这样特点的 6 位数还有一个，请你找出它！

再归纳一下筛选要求：

  1. 6 位正整数；
  2. 每个数位上的数字不同；
  3. 其平方数的每个数位不含原数字的任何组成数位。

运行限制

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

直接暴力解决，算出来是203879，639172。

唯一一个需要注意的是类型转换。

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

bool w[10];

bool isUnique(int x) {
    memset(w, false, sizeof w);
    while (x) {
        if (w[x % 10])
            return false;
        else {
            w[x % 10] = true;
            x /= 10;
        }
    }
    return true;
}

bool isVeryUnique(int x) {
    // 类型转换要提前
    LL square = (LL)x * x;
    while (square != 0) {
        if (w[square % 10])
            return false;
        else
            square /= 10;
    }
    return true;
}

int main() {
    for (int i = 1e5; i < 1e6; i++) {
        if (isUnique(i) && isVeryUnique(i)) cout << i << endl;
    }
    return 0;
}

2.买不到的数目-2013省赛

https://www.lanqiao.cn/problems/213/learning/

题目描述

小明开了一家糖果店。他别出心裁：把水果糖包成 4 颗一包和 7 颗一包的两种。糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是 17。大于 17 的任何数字都可以用 4 和 7 组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入描述

输入两个正整数，表示每种包装中糖的颗数(都不多于 1000 )。

输出描述

输出一个正整数，表示最大不能买到的糖数。

不需要考虑无解的情况

输入输出样例

示例

输入

1
4 7

输出

1
17

运行限制

  • 最大运行时间：3s
  • 最大运行内存: 64M

这种题目的公式的证明过于复杂，数学不好的我不理解。

找几个数字猜出规律出来就行。
首先选择质数。
3 5——可以表示的数字3 5 6 **8 9 10**...（有 3 个连续的数字后所有的数字都可以表示了）—— 最大不能表示的数是 7
3 6——可以表示的数字3 6 9 12...(题目表示一定有解，都是偶数没啥考虑的
3 7——可以表示的数字3 6 7 9 10 **12 13 14** 15 —— （有 3 个连续的数字后所有的数字都可以表示了）最大不能表示的数是 11
3 8——可以表示的数字3 6 8 9 11 12 **14 15 16** —— （有 3 个连续的数字后所有的数字都可以表示了）所以最大不能表示的数是 13

3 5最大不能表示的数字是7。
3 7最大不能表示的数字是11。
3 8最大不能表示的数字是13。
3不变，后面那个数字每增加1，最大不能表示的数字就加2 。
大胆猜测这就是规律，那么3 10最大不能表示的数字是17吗？

3 10——可以表示的数字3 6 9 12 13 15 16 **18 19 20**——最大不能表示的数真的是 17。

猜测正确了！

那么加的2代表什么呢？我们不知道，但是这个数字肯定和3有关，应该是3-1=2吧。

所以表达式应该是（a - 1）*（xxxxxxx不知道）之类的。

后面一段什么呢？

这个公式大概率是对称的。

因为所给的a b（指所给的第一个数和第二个数）是随机的，a（3）不变，b + 1，最大不能表示的数要加上a - 1（2） ；那么 b不变，a + 1，最大不能表示的数也应该是加上b - 1 。所以猜测公式是（a - 1）*（b - 1）。

然后带入计算发现公式确实是（a - 1）*（b - 1）- 1。

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>

using namespace std;

int main() {
    int p, q;
    cin >> p >> q;
    cout << (p - 1) * (q - 1) - 1 << endl;
    return 0;
}

3.回文日期-2020省赛

https://www.lanqiao.cn/problems/498/learning/

题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入描述

输入包含一个八位整数 NN，表示日期。

对于所有评测用例，10000101≤N≤89991231，保证 N 是一个合法日期的 8 位数表示。

输出描述

输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。

输入输出样例

示例

输入

1
20200202

输出

1
2
20211202
21211212

运行限制

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

有些常用的函数需要背诵下来

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
60
61
62
63
64
65
66
67
68
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

//  这个函数需要背诵下来！
bool checkVaild(int date) {
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;
    int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (!month || month >= 13 || !day) return false;
    if (month != 2 && day > months[month]) return false;

    if (month == 2) {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

bool ishw(int n) {
    int lhalf = n / 10000;
    int rhalf = 0;
    for (int i = 0; i < 4; i++) {
        rhalf = 10 * rhalf + n % 10;
        n /= 10;
    }
    if (lhalf == rhalf)
        return true;
    else
        return false;
}

bool isABhw(int n) {
    int lab = n / 1000000;
    int rab = 0;
    n = n / 100;
    for (int i = 0; i < 2; i++) {
        rab = 10 * rab + n % 10;
        n /= 10;
    }
    if (lab == rab)
        return true;
    else
        return false;
}

int main() {
    int n;
    cin >> n;
    int a, b;
    int i = n + 1;
    for (; i <= 99999999; i++)
        if (checkVaild(i) && ishw(i)) {
            a = i;
            break;
        }

    for (int j = i; j <= 99999999; j++)
        if (checkVaild(j) && ishw(j) && isABhw(j)) {
            b = j;
            break;
        }

    cout << a << endl << b << endl;
}

4.约瑟夫环-2018国赛

https://www.lanqiao.cn/problems/231/learning/

题目描述

n 个人的编号是 1 ~ n，如果他们依编号按顺时针排成一个圆圈，从编号是 1 的人开始顺时针报数。

（报数是从 1 报起）当报到 k 的时候，这个人就退出游戏圈。下一个人重新从 1 开始报数。

求最后剩下的人的编号。这就是著名的约瑟夫环问题。

本题目就是已知 n，k 的情况下，求最后剩下的人的编号。

输入描述

输入是一行，2 个空格分开的整数 n, k(0 < n,k < 10^7)。

输出描述

要求输出一个整数，表示最后剩下的人的编号。

输入输出样例

示例

输入

1
10 3

输出

1
4

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M
1
国赛题，看不懂题解，弃之。

发表于 分类于 ，

国赛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;
}

发表于 更新于 分类于

2022 年 3 月 1 日开课啦！
报名链接：https://www.icourse163.org/learn/ZJU-93001?tid=1466830443

常用软件下载
https://bytodance.feishu.cn/docs/doccn7ZRXBvN8HMEfF8LNq9gKig
备用下载地址
https://pan.mhatp.cn/%E8%BD%AF%E4%BB%B6

01-复杂度3 二分查找 (20 分)

复习一下二分查找模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Position BinarySearch( List L, ElementType X )
{
    int l=1,r=L->Last;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(L->Data[mid] >= X){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    if(L->Data[r] == X){
        return r;
    }else{
        return NotFound;
    }
    
}

01-复杂度1 最大子列和问题 (20 分)

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 <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
// typedef long long ll;
// 后来发现 int 也能过
using namespace std;

const int N = 1e5 + 10;

int n;
int arr[N];
int thissum = 0, maxsum = -0x3f3f3f;

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    for (int i = 0; i < n; i++) {
        thissum += arr[i];
        if (thissum < 0) thissum = 0;
        maxsum = max(maxsum, thissum);
    }

    printf("%d", maxsum);
    return 0;
}

01-复杂度2 Maximum Subsequence Sum (25 分)

不知道哪错了，呜呜

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
60
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
typedef long long ll;
using namespace std;

const int N = 1e5 + 10;

int n;
int arr[N];
int thissum = 0, maxsum = -0x3f3f3f;

int main() {
    
    scanf("%d", &n);

    for (int i = 0; i < n; i++)  scanf("%d", &arr[i]);

    int maxl, maxr;
    
    bool first = true;
    
    int thisl,thisr;

    for (int i = 0; i < n; i++) {
        
        thissum += arr[i];
       
        if(first){
            thisl = i;
            thisr = i;
            first = false;
        }else{
            thisr = i;
        }
        
         
        if (thissum < 0) {
           // 重新开始一个
            
            thissum = 0;

            first = true;
        }
        
        
        if (thissum > maxsum) {
            maxsum = thissum;
            maxl = thisl;
            maxr = thisr;
        }
        
        
    }
    
    printf("%d %d %d\n", maxsum, maxl, maxr);
    
    return 0;
}

测试视频，请忽视

0%