第三届 “图灵杯” 趣味网络邀请赛

#题目结构

初级
中级
- A. 括号匹配
- B. 质数
- C. 机器人
- D. 欧拉回路
高级
- A. 机器人
- B. 欧拉回路
- C. 划分
- D. 正则表达式

#信友队

时间限制：1000ms ，空间限制 512MB

#题面

#题目描述

欢迎参加图灵杯！

集天下英才、育天下人，信友队已经培养出了非常多优秀的人才。

现在，信友队给了你三块 $(2n+1) \times (2n+1)$ 的网格画板，请你给每个格子填充黑色或白色，写下大大的 $\text{X,\ Y,\ D}$ （信友队的三个首字母）！

#输入格式

一个正整数表示 $n$ 。

#输出格式

依次输出 $3$ 个 $(2n+1) \times (2n+1)$ 的字母 $\text{X,\ Y,\ D}$ ，相邻两个字母之间用一个空行隔开。

黑色字母用 + 表示，白色用空格表示。

#思路

由于数据不大，直接模拟即可。

#代码

打表版

时间复杂度 $O(1)$

#include <bits/stdc++.h>

using namespace std;

int n;
string ans[15][10];

int main() {
    cin >> n;
    // X
    ans[1][1] = "+ +\n +\n+ +\n";
    ans[2][1] = "+   +\n + +\n  +\n + +\n+   +\n";
    ans[3][1] = "+     +\n +   +\n  + +\n   +\n  + +\n +   +\n+     +\n";
    ans[4][1] = "+       +\n +     +\n  +   +\n   + +\n    +\n   + +\n  +   +\n +     +\n+       +\n";
    ans[5][1] = "+         +\n +       +\n  +     +\n   +   +\n    + +\n     +\n    + +\n   +   +\n  +     +\n +       +\n+         +\n";
    ans[6][1] = "+           +\n +         +\n  +       +\n   +     +\n    +   +\n     + +\n      +\n     + +\n    +   +\n   +     +\n  +       +\n +         +\n+           +\n";
    ans[7][1] = "+             +\n +           +\n  +         +\n   +       +\n    +     +\n     +   +\n      + +\n       +\n      + +\n     +   +\n    +     +\n   +       +\n  +         +\n +           +\n+             +\n";
    ans[8][1] = "+               +\n +             +\n  +           +\n   +         +\n    +       +\n     +     +\n      +   +\n       + +\n        +\n       + +\n      +   +\n     +     +\n    +       +\n   +         +\n  +           +\n +             +\n+               +\n";
    ans[9][1] = "+                 +\n +               +\n  +             +\n   +           +\n    +         +\n     +       +\n      +     +\n       +   +\n        + +\n         +\n        + +\n       +   +\n      +     +\n     +       +\n    +         +\n   +           +\n  +             +\n +               +\n+                 +\n";
    ans[10][1] = "+                   +\n +                 +\n  +               +\n   +             +\n    +           +\n     +         +\n      +       +\n       +     +\n        +   +\n         + +\n          +\n         + +\n        +   +\n       +     +\n      +       +\n     +         +\n    +           +\n   +             +\n  +               +\n +                 +\n+                   +\n";
    // Y
    ans[1][2] = "+ +\n +\n +\n";
    ans[2][2] = "+   +\n + +\n  +\n  +\n  +\n";
    ans[3][2] = "+     +\n +   +\n  + +\n   +\n   +\n   +\n   +\n";
    ans[4][2] = "+       +\n +     +\n  +   +\n   + +\n    +\n    +\n    +\n    +\n    +\n";
    ans[5][2] = "+         +\n +       +\n  +     +\n   +   +\n    + +\n     +\n     +\n     +\n     +\n     +\n     +\n";
    ans[6][2] = "+           +\n +         +\n  +       +\n   +     +\n    +   +\n     + +\n      +\n      +\n      +\n      +\n      +\n      +\n      +\n";
    ans[7][2] = "+             +\n +           +\n  +         +\n   +       +\n    +     +\n     +   +\n      + +\n       +\n       +\n       +\n       +\n       +\n       +\n       +\n       +\n";
    ans[8][2] = "+               +\n +             +\n  +           +\n   +         +\n    +       +\n     +     +\n      +   +\n       + +\n        +\n        +\n        +\n        +\n        +\n        +\n        +\n        +\n        +\n";
    ans[9][2] = "+                 +\n +               +\n  +             +\n   +           +\n    +         +\n     +       +\n      +     +\n       +   +\n        + +\n         +\n         +\n         +\n         +\n         +\n         +\n         +\n         +\n         +\n         +\n";
    ans[10][2] = "+                   +\n +                 +\n  +               +\n   +             +\n    +           +\n     +         +\n      +       +\n       +     +\n        +   +\n         + +\n          +\n          +\n          +\n          +\n          +\n          +\n          +\n          +\n          +\n          +\n          +\n";
    // D
    ans[1][3] = "++ \n+ +\n++\n";
    ans[2][3] = "++++\n+   +\n+   +\n+   +\n++++\n";
    ans[3][3] = "++++++\n+     +\n+     +\n+     +\n+     +\n+     +\n++++++\n";
    ans[4][3] = "++++++++\n+       +\n+       +\n+       +\n+       +\n+       +\n+       +\n+       +\n++++++++\n";
    ans[5][3] = "++++++++++\n+         +\n+         +\n+         +\n+         +\n+         +\n+         +\n+         +\n+         +\n+         +\n++++++++++\n";
    ans[6][3] = "++++++++++++\n+           +\n+           +\n+           +\n+           +\n+           +\n+           +\n+           +\n+           +\n+           +\n+           +\n+           +\n++++++++++++\n";
    ans[7][3] = "++++++++++++++\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n+             +\n++++++++++++++\n";
    ans[8][3] = "++++++++++++++++\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n+               +\n++++++++++++++++\n";
    ans[9][3] = "++++++++++++++++++\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n+                 +\n++++++++++++++++++\n";
    ans[10][3] = "++++++++++++++++++++\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n+                   +\n++++++++++++++++++++\n";
    cout << ans[n][1] << endl
         << ans[n][2] << endl
         << ans[n][3] << endl;
    return 0;
}

模拟版

时间复杂度严格小于 $O(n^2)$ 。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    // X 的上半部分
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            cout << ' ';
        }
        cout << '+';
        for (int j = 1; j < 2 * n - 2 * i; j++) {
            cout << ' ';
        }
        cout << '+' << endl;
    }
    // X 的中间部分
    for (int i = 0; i < n; i++) {
        cout << ' ';
    }
    cout << '+' << endl;
    // X 的下半部分
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            cout << ' ';
        }
        cout << '+';
        for (int j = 1; j < 2 * n - 2 * i; j++) {
            cout << ' ';
        }
        cout << '+' << endl;
    }
    cout << endl;     // 空行
    // Y 的上半部分
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            cout << ' ';
        }
        cout << '+';
        for (int j = 1; j < 2 * n - 2 * i; j++) {
            cout << ' ';
        }
        cout << '+' << endl;
    }
    // Y 的下半部分
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ' ';
        }
        cout << '+' << endl;
    }
    cout << endl;     // 空行
    // D 的第一行
    for (int i = 0; i < n * 2; i++) {
        cout << '+';
    }
    cout << endl;
    // D 的中间部分
    for (int i = 1; i < n * 2; i++) {
        cout << '+';
        for (int i = 1; i < n * 2; i++) {
            cout << ' ';
        }
        cout << '+' << endl;
    }
    // D 的最后一行
    for (int i = 0; i < n * 2; i++) {
        cout << '+';
    }
    cout << endl;
    return 0;
}

#蔚蓝

时间限制：1000ms ，空间限制：256MB

#题面

#题目描述

F 神打开了他的 Celeste，开始了快乐的跑酷。一旁的 L 神看到了，怀疑起 F 神的操作，认为他开了无敌挂和穿墙挂。

现在告诉你 F 神的行动路径和障碍，请你判断 F 神是否一定开了挂。

为了简化题意，人物抽象为点，你只需要判断输入的 $n$ 个判定点是否和输入的 $m$ 个矩形障碍重合（包括在矩形边缘）即可。

所有矩形障碍的边均平行于坐标轴，矩形有可能退化为线或点。

#输入格式

第一行两个整数 $n, m$ ，表示判定点数和障碍数。

接下来 $n$ 行每行两个整数 $x_i, y_i$ ，表示第 $i$ 个判定点的坐标。

接下来行每行四个整数 $lx_i, ly_i, rx_i, ry_i$ ，表示第 $i$ 个矩形障碍的左下角和右上角。

#输出格式

一行一个字符串，若 F 神一定开了挂，输出 Yes ，否则输出 No 。

#输入输出样例

输入样例 #1

1
2
3

1 1
2 2
2 2 4 4

输出样例 #1

Yes

输入样例 #2

输出样例 #2

No

#数据范围与约定

本题采取 Subtask 评测的方式，对于所有数据保证 $1 \leq n, m \leq 1000,\ 1 \leq x_i, y_i, lx_i, ly_i, rx_i, ry_i \leq 10^9,\ x_i \leq rx_i,\ lx_i \leq rx_i,\ ly_i \leq ry_i$ 。

子任务编号	$n, m \leq$	$x_i, y_i, lx_i, ly_i, rx_i, ry_i \leq$	分值
1	$1$	$10$	20
2	$50$	$100$
3	$500$	$1000$
4	$1000$	$10^9$	40

#思路

先暂存所有经过的点，然后每输入一个矩形就遍历之前暂存的所有点，如果重合则直接输出 Yes 并退出程序，否则在程序末尾输出 No 。

#代码

时间复杂度 $O(nm)$

#include <bits/stdc++.h>

using namespace std;

int n, m, lx, ly, rx, ry;
pair<int, int> point[1005];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> point[i].first >> point[i].second;
    }
    for (int i = 0; i < m; i++) {
        cin >> lx >> ly >> rx >> ry;
        for (int i = 0; i < n; i++) {
            if (lx <= point[i].first && point[i].first <= rx && ly <= point[i].second && point[i].second <= ry) {
                cout << "Yes" << endl;
                exit(0);
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

#括号匹配

时间限制：1000ms ，空间限制：256MB

#题面

#题目描述

众所周知，任何一个现代编辑器都有括号匹配功能。当你编辑代码的时候，把光标移到一个括号上，编辑器就会提示你与之对应的括号。小 F 想研究这个功能的原理。

为了简化问题，小 F 打算只研究代码中的大括号。去掉其它字符后，代码中只有 { （左大括号）和 } （右大括号）两种字符，总长度为 $n$ 。

括号匹配的规则是：

{} 是最简单的括号序列，其左右括号互相匹配；
如果 $S$ 是一个括号序列，那么 $\{S\}$ 也是一个括号序列，其左边的左括号和右边的右括号互相匹配；
如果 $A,\ B$ 都是一个括号序列，那么 $AB$ （将 $A$ 和 $B$ 直接拼接）也是一个括号序列。

小 F 现在打开了这份简化后的代码，他的光标正指向第 $p$ 个字符（从 $1$ 开始）。小 F 希望知道与这个字符相匹配的括号是第几个字符。

小 F 研究了三天三夜，还没研究出来。无奈之下，他请你给他写一个程序，完成这个功能。

#输入格式

第一行两个整数 $n,p$ ，表示程序的长度和光标的位置。

第二行一个字符串 $s$ ，表示小 F 的程序。

#输出格式

一行一个正整数，表示与之匹配的光标的位置。

#输入输出样例

输入样例 #1

1 2	`4 3 {{}}`

输出样例 #1

输入样例 #2

1 2	`8 4 {{}{{}}}`

输出样例 #2

#数据范围与约定

本题使用子任务评测方式。你的程序能够得到一个子任务的分数当且仅当你的程序通过了所有满足该子任务限制的数据点。

对于所有数据， $1 \leq \leq 10^5,\ 1 \leq p \leq n,\ |s| = n,\ s_i \in \{\small{\{\}}\normalsize\}$

子任务编号	$n \leq$	分值
1	$2$	10
2	$4$	20
3	$10^5$	70

#思路

使用一个栈存 { 在给定字符串中的位置，当遇到 { 时将位置入栈。

遇到 } 时如果光标与栈顶字符的位置相同则输出当前位置并退出程序，如果光标与当前位置相同则输出栈顶字符的位置并退出程序，均不符合则将栈顶出栈。

#代码

时间复杂度为 $O(n)$

#include <bits/stdc++.h>

using namespace std;

int n, p;
string s;
stack<int> st;

int main() {
    cin >> n >> p >> s;
    s = ' ' + s;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == '{') {           // 如果是 `{` 则入栈
            st.push(i);
        } else if (st.top() == p) {  // 当光标与栈顶字符的位置相同时输出当前位置
            cout << i << endl;
            exit(0);
        } else if (i == p) {         // 当光标与当前位置相同时输出栈顶字符的位置
            cout << st.top() << endl;
            exit(0);
        } else {                     // 否则出栈
            st.pop();
        }
    }
    return 0;
}

#质数

时间限制：1000ms ，空间限制：512MB

#题面

#题目描述

输入一个正整数 $a$ ，请你找出最小的质数 $p$ ，使得 $a^p$ 和 $p^a$ 这两个正整数的（十进制）末位数字相同。如果不存在这样的质数，请输出 $-1$ 。

一组输入中包含多个询问。

#输入格式

第一行一个正整数 $T$ ，表示询问数量。

接下来 $T$ 行每行一个正整数 $a$ 。

#输出格式

对于每组数据输出一行答案。

#输入输出样例

输入样例 #1

2
9
12

输出样例 #1

19
-1

#思路

先预处理出 $10^6$ 内的质数，然后按照题意遍历计算即可，无解输出 -1 。

#代码

#include <bits/stdc++.h>

using namespace std;

int t, a, p, prime[100005];
bool flag, is_prime[1000005];

// 埃氏筛
void eratosthenes(int n) {
    for (int i = 0; i <= n; i++) is_prime[i] = 1;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            prime[p++] = i;
            if (1ll * i * i <= n) {
                for (int j = i * i; j <= n; j += i) {
                    is_prime[j] = 0;
                }
            }
        }
    }
}

// 快速幂
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int main() {
    eratosthenes(1000000);  // 预处理 1e6 内的质数
    cin >> t;
    while (t--) {
        flag = false;
        cin >> a;
        for (int i = 0; i < p; i++) {
            if (binpow(a, prime[i], 10) % 10 == binpow(prime[i], a, 10) % 10) {
                cout << prime[i] << endl;
                flag = true;
                break;
            }
        }
        if (!flag) cout << -1 << endl;
    }
    return 0;
}

#机器人

#题面

#题目描述

一个机器人在数轴上移动，机器人所在的坐标始终为整数（可以是负数，零，或正数）。假设机器人当前在数轴上 $x$ 点，当收到指令 $(d, k)$ 后（其中 $d$ 是整数， $k$ 是正整数），机器人会移动到数轴上 $(x + d)$ 点的位置，并获得 $|2kx + kd|$ 的分数。

机器人初始时在数轴上的原点。现在给定了 $n$ 个指令，机器人需要执行其中每一个指令恰好一次，但是执行指令的先后次序还没有确定。请你合理安排执行这些指令的顺序，使得机器人获得的总分数最大化。你只需要输出最大总分即可。

#输入格式

第一行一个整数 $n$ 表示指令的数量。

接下来 $n$ 行每行两个正整数 $d_i, k_i$ 表示一个指令。

#输出格式

输出一个非负整数，表示最大积分。

#输入输出样例

输入样例 #1

输出样例 #1

#代码

#include <bits/stdc++.h>

using namespace std;

int n;
long long ans, cnt, x;
pair<long long, long long> q[300005];

bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
    return (a.first - b.first) * (a.second + b.second) > (a.first + b.first) * (a.second - b.second);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> q[i].first >> q[i].second;
    }
    sort(q, q + n, cmp);
    for (int i = 0; i < n; i++) {
        cnt += abs(2 * q[i].second * x + q[i].second * q[i].first);
        x += q[i].first;
    }
    ans = max(ans, cnt);
    x = 0;
    cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        cnt += abs(2 * q[i].second * x + q[i].second * q[i].first);
        x += q[i].first;
    }
    ans = max(ans, cnt);
    cout << ans << endl;
    return 0;
}

#后记

本次的比赛相比前两次的比赛来说难度有所降低，其他无感。

这次我 AK 了初级组，也算是意料之中了。