蓝桥杯打卡-Day2

发表于 分类于 ，

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
国赛题，看不懂题解，弃之。