蓝桥打卡-Day16

发表于 2022-03-24 分类于代码，蓝桥杯

距离和- 2021模拟

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

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

两个字母之间的距离定义为它们在字母表中位置的距离。例如 A 和 C 的距离为 2，L 和 Q 的距离为 5。

对于一个字符串，我们称字符串中两两字符之间的距离之和为字符串的内部距离。

例如：ZOO 的内部距离为 22，其中 Z 和 O 的距离为 11。

请问，LANQIAO 的内部距离是多少？

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  string s = "LANQIAO";
  int res = 0;
  for (int i = 0; i < s.size() - 1; i ++ )
    for (int j = i + 1; j < s.size(); j ++ )
      res += abs(s[i] - s[j]);
  
  cout << res << endl;
  return 0;
}

扩散-2020国赛

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

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

小蓝在一张无限大的特殊画布上作画。

这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。

小蓝在画布上首先点了一下几个点：(0,0),(2020,11),(11,14),(2000,2000)。

只有这几个格子上有黑色，其它位置都是白色的。

每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色（如果原来就是黑色，则还是黑色）。

请问，经过 2020 分钟后，画布上有多少个格子是黑色的。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;

const int N = 10000;
typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};

bool m[N][N];
int cnt = 4;
//(0, 0), (2020, 11), (11, 14), (2000, 2000)。
void bfs() {
    queue<PII> q;

    q.push({3000, 3000});
    m[3000][3000] = true;

    q.push({5020, 3011});
    m[5020][3011] = true;

    q.push({3011, 3014});
    m[3011][3014] = true;

    q.push({5000, 5000});
    m[5000][5000] = true;

    int res = 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 < 0 || y < 0) continue;
            if (m[x][y]) continue;
            // 没选过
            m[x][y] = true;
            q.push({x, y});
            cnt++;
        }
        // 把头元素加入队列方便计数
        if (t.x == 3000 && t.y == 3000) {
            q.push({3000, 3000});
            res++;
        }
        if (res == 2021) break;

        q.pop();
    }
    return;
}

int main() {
    bfs();
    cout << cnt << endl;
    return 0;
}

错误票据-2013省赛

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

题目描述

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的 ID 号。全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。

因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。

你的任务是通过编程，找出断号的 ID 和重号的 ID 。

假设断号不可能发生在最大和最小号。

输入描述

要求程序首先输入一个整数 N (N<100)表示后面数据行数。

接着读入 N 行数据。

每行数据长度不等，是用空格分开的若干个（不大于 100 个）正整数（不大于10 5）。

输出描述

要求程序输出 1 行，含两个整数 m,n，用空格分隔。

其中，m 表示断号 ID，n 表示重号 ID。

输入输出样例

示例

输入

1
2
3

2
5 6 8 11 9
10 12 9

输出

7 9

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
const int N = 1010;

int a[N];

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

    int i = 0;
    while (cin >> a[i++])
        ;

    sort(a, a + i);

    int m, n;

    for (int j = 1; j < i; j++) {
        if (a[j] == a[j - 1])
            m = a[j];
        else if (a[j - 1] + 1 != a[j])
            n = a[j] - 1;
    }

    cout << n << ' ' << m << endl;

    return 0;
}

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int maxid = -INF, minid = INF;
int id[N];

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

    int c;
    while (cin >> c) {
        maxid = max(maxid, c);
        minid = min(minid, c);
        id[c]++;
    }

    int m, n;
    for (int i = minid; i <= maxid; i++) {
        // 找重复的
        if (id[i] == 0) m = i;
        // 找缺少的
        if (id[i] == 2) n = i;
    }

    cout << m << " " << n << endl;
    return 0;
}

倍数问题-2018省赛

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

题目描述

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

输入描述

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

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

其中，1≤n ≤10^5, 1≤K ≤10^3，给定的 n 个数均不超过 10^8。

输出描述

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

输入输出样例

示例

输入

1 2	4 3 1 2 3 4

输出