这东西……勉强能算是个做题记录？有些恶心的模拟题用了非常规的解法，这里就不放代码了

训练作业一

众数

  每组数据均以递增顺序输入，故从左到右扫描输入序列，记录最多连续出现的数。

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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    while (n) {
        int cnt;  // 当前连续出现的数的个数
        int last = -1;

        int grp = 0, record = 0;
        for (int i = 0; i < n; i++) {
            int tmp; cin >> tmp;
            (last != tmp) && (cnt = 0);
            cnt++;

            if (cnt > record) {  // 统计众数
                record = cnt;
                grp = tmp;
            }
            last = tmp;
        }
        cout << grp << endl;
        cin >> n;
    }
    return 0;
}

错误的里程表

  不出现 3 和 8，则原来的十进制降为八进制，那么将 01245679 还原为 01234567 后再作 八进制 → 十进制 转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    char digit[] = {0, 1, 2, 0, 3, 4, 5, 6, 0, 7};  // 将里程表数值映回原八进制数
    while (n--) {
        string str; cin >> str;
        int real = 0;
        for (char ch : str) {
            real = real * 8 + digit[ch-'0'];
        }
        cout << real << endl;
    }
    return 0;
}

拳王阿里

  设比赛的总天数为 7k+d(k∈Z)7k+d\quad(k\in Z)，那么 dd 可由开始和结束的星期数确定；由于 LL、RR 差值较小，直接遍历 [L,R][L, R] 求解

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 <bits/stdc++.h>
using namespace std;

map<string, int> day = {
        {"monday", 1}, {"tuesday", 2}, {"wednesday", 3}, {"thursday", 4},
        {"friday", 5}, {"saturday", 6}, {"sunday", 7}
};

int main() {
    int T; cin >> T;
    while (T--) {
        string begin, end;
        int L, R;
        cin >> begin >> end >> L >> R;

        // 算出相差天数，并通过取模保证值为正
        int d = (day[end] - day[begin] + 8) % 7;
        int ans, count = 0;
        for (int i = L; i <= R; i++) {  // 遍历区间 [L, R] 统计符合条件的天数
            if ((i - d) % 7 == 0) {
                ans = i;
                count++;
            }
        }
        if (count == 0) {
            cout << "impossible" << endl;
        } else if (count >= 2) {
            cout << "many" << endl;
        } else {
            cout << ans << endl;
        }
    }
    return 0;
}
  • 更新：数学解法

  不妨设阿里比赛的总天数为 7k+d∈[L,R]7k+d\in[L, R]，简单整理可得：

k∈[L−d7,R−d7]k\in[\frac{L-d}{7}, \frac{R-d}{7}]

  其中 dd 的值可由比赛开始和结束的星期数计算而得，那么只需要确定在上述区间中有几个整数 kk 即可；由于除法可能产生小数数值，判断的时候需要对区间左端点向上取整，右端点向下取整，再比较左右端点的大小，记 k1=⌈L−d7⌉k_1=\lceil\frac{L-d}{7}\rceil，k2=⌊R−d7⌋k_2=\lfloor\frac{R-d}{7}\rfloor，那么当 k1=k2k_1=k_2 时，有唯一解，k1<k2k_1 < k_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
#include <bits/stdc++.h>
using namespace std;

map<string, int> day = {
        {"monday", 1}, {"tuesday", 2}, {"wednesday", 3}, {"thursday", 4},
        {"friday", 5}, {"saturday", 6}, {"sunday", 7}
};

int main() {
    int T; cin >> T;
    while (T--) {
        string begin, end;
        int L, R;
        cin >> begin >> end >> L >> R;

        int d = (day[end] - day[begin] + 8) % 7 - 7;
        int k1 = (L - d + 6) / 7, k2 = (R - d) / 7;  // 通过先加 7-1 = 6 再整除 7 来上取整
 
        if (k1 == k2) {
            cout << 7*k1 + d << endl;
        } else if (k1 < k2) {
            cout << "many" << endl;
        } else {
            cout << "impossible" << endl;
        }
    }
    return 0;
}

欧洲冠军联赛

  模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import defaultdict

T = int(input())

for i in range(T):
    count = defaultdict(lambda: [0, 0])  # 积分 | 净胜球
    for j in range(12):
        teamA, scoreA, _, scoreB, teamB = input().split()
        scoreA, scoreB = int(scoreA), int(scoreB)

        if scoreA == scoreB:
            count[teamA][0] += 1
            count[teamB][0] += 1
        else:
            count[teamA][0] += 3 if scoreA - scoreB > 0 else 0
            count[teamA][1] += scoreA - scoreB
            count[teamB][0] += 3 if scoreB - scoreA > 0 else 0
            count[teamB][1] += scoreB - scoreA
    tops = []
    for name in count:
        tops.append((name, count[name]))
    tops.sort(key=lambda x: x[1][0]*100 + x[1][1])
    print(tops[-1][0], tops[-2][0])

合法的括号串

  维护一个存放左括号的栈，当遇到右括号时尝试对与其匹配的左括号出栈，若无法完成此操作或最后栈不为空，则认为输入的字符串不合法

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
#include <bits/stdc++.h>
using namespace std;

map<char, char> rev = {{'>', '<'}, {')', '('}, {']', '['}, {'}', '{'}};


void judge(string str) {
    stack<char> st;
    for (char ch : str) {
        if (ch == '<' || ch == '[' || ch == '(' || ch == '{') {  // 左括号直接入栈
            st.push(ch); 
        } else {  // 遇到右括号时判断栈顶元素是否与之匹配
            if (st.empty()) {
                cout << "No" << endl;
                return;
            }
            if (st.top() == rev[ch]) {
                st.pop();
            } else {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << (st.empty() ? "Yes" : "No") << endl;  // 最后记得判断栈是否为空
}


int main() {
    int T; cin >> T;
    while (T--) {
        string str; cin >> str;
        judge(str);
    }
    return 0;
}

世界杯来了

  与第四题大同小异，改改就能用：

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
import re

count = {}
n = int(input())

for i in range(n):
    count[input()] = [0, 0, 0]  # 积分 | 净胜球 | 进球数

for i in range(n*(n-1)//2):
    teamA, teamB, scoreA, scoreB = re.findall('([A-Za-z]+)-([A-Za-z]+) ([0-9]+):([0-9]+)', input())[0]
    scoreA, scoreB = int(scoreA), int(scoreB)

    if scoreA == scoreB:
        count[teamA][0] += 1
        count[teamB][0] += 1
    else:
        count[teamA][0] += 3 if scoreA - scoreB > 0 else 0
        count[teamA][1] += scoreA - scoreB
        count[teamB][0] += 3 if scoreB - scoreA > 0 else 0
        count[teamB][1] += scoreB - scoreA
    count[teamA][2] += scoreA
    count[teamB][2] += scoreB

tops = []
for name in count:
    tops.append((name, count[name]))
tops.sort(key=lambda x: x[1][0]*10000 + x[1][1]*100 + x[1][2])
tops = sorted(tops[n//2:], key=lambda x: x[0])
for item in tops:
    print(item[0])

F1 方程式冠军

  结构体记录每位选手的名字、赢的次数和积分，先通过 map 统计得分情况，最后转入 vector 中排序输出：

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
#include <bits/stdc++.h>
using namespace std;

const int extras[] = {25, 18, 15, 12, 10, 8, 6, 4, 2, 1, 0};

struct Player {
    string name;
    int extra = 0;  // 额外积分
    int rank[100] = {0};

    Player() { }

    Player(const Player& src) {
        name = src.name, extra = src.extra;
        for (int i = 0; i < 100; i++) {
            rank[i] = src.rank[i];
        }
    }
};

int main(){
    int T; cin >> T;
    map<string, Player> score;
    while (T--) {
        int n; cin >> n;
        for (int i = 0; i < n; i++) {
            string name; cin >> name;
            score[name].name = name;
            score[name].extra += extras[min(i, 10)];
            score[name].rank[i]++;
        }
    }
    vector<Player> arr;
    for (auto item : score) {
        arr.push_back(item.second);
    }
    sort(arr.begin(), arr.end(), [] (Player a, Player b) {  // 按初始规则排序
        if (a.extra != b.extra) {
            return a.extra > b.extra;
        }
        for (int i = 0; i < 100; i++) {
            if (a.rank[i] != b.rank[i]) {
                return a.rank[i] > b.rank[i];
            }
        }
        return false;
    });
    cout << arr[0].name << endl;
    sort(arr.begin(), arr.end(), [] (Player a, Player b) {  // 按新规则排序
        if (a.rank[0] != b.rank[0]) {
            return a.rank[0] > b.rank[0];
        }
        if (a.extra != b.extra) {
            return a.extra > b.extra;
        }
        for (int i = 1; i < 100; i++) {
            if (a.rank[i] != b.rank[i]) {
                return a.rank[i] > b.rank[i];
            }
        }
        return false;
    });
    cout << arr[0].name << endl;
    return 0;
}

买房与选房 —— 🈚️

二叉树遍历，从前序、中序到后序

  从前序遍历可以得出当前区间的根节点，再在中序遍历中定位该根节点位置，从而划分出两颗子树，递归求解：

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 <bits/stdc++.h>
using namespace std;

int n;
char pre[100], mid[100];

void dfs(int root, int l, int r) {  // 输出后序遍历
    if (l >= r) {
        return;
    }
    int m = -1;
    for (int i = l; i < r; i++) {  // 在中序遍历中定位根节点
        if (mid[i] == pre[root]) {
            m = i;
            break;
        }
    }
    // 尿分叉搜索
    dfs(root+1, l, m);
    dfs(root+(m-l)+1, m+1, r);
    putchar(pre[root]);
}

int main() {
    cin >> n;
    while (n) {
        for (int i = 0; i < n; i++) {
            cin >> pre[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> mid[i];
        }
        dfs(0, 0, n);  // 左闭合区间
        cout << endl;
        cin >> n;
    }
    return 0;
}

内存管理

  纯模拟题，使用链表完成，审清楚题目、标好注释一般不会错~~（就是可能超时）~~

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
#include <bits/stdc++.h>
using namespace std;

struct block {
    int id, L, R;  // 经典左闭合
    block* next = NULL;

    block(int id_, int L_, int R_) {
        id = id_, L = L_, R = R_;
    }
};

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

    int index = 1;
    block* head = new block(0, -1, 0);
    while (T--) {
        string opt; int arg;
        cin >> opt;
        if (opt == "alloc") {  // 分配内存
            cin >> arg;
            bool flag = false;  // 标记是否分配成功
            for (block* ptr = head; ptr; ptr = ptr->next) {  // 从表头向后查找，每次检查是否能在当前位置之后分配内存
                if (ptr -> next) {  // 在 “中间” 插入块
                    if (ptr->next->L - ptr->R >= arg) {  // 如果空间足够则新建一个块
                        block* tmp = new block(index++, ptr->R, ptr->R + arg);
                        tmp -> next = ptr -> next;
                        ptr -> next = tmp;

                        cout << (tmp -> id) << endl;
                        flag = true;
                        break;
                    }
                } else {  // 在最后追加块
                    if (ptr->R + arg <= m) {  // 否则尝试在最后添加块
                        block* tmp = new block(index++, ptr->R, ptr->R + arg);
                        ptr -> next = tmp;

                        cout << (tmp -> id) << endl;
                        flag = true;
                        break;
                    }
                }
            }
            if (!flag) {
                cout << "NULL" << endl;
            }
        } else if (opt == "erase") {  // 删除块
            cin >> arg;
            bool flag = false;  // 标记是否找到目标块
            for (block* ptr = head; ptr->next; ptr = ptr->next) {
                if (ptr->next->id == arg) {
                    block* tmp = ptr->next;
                    ptr -> next = ptr -> next -> next;
                    delete tmp;
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                cout << "ILLEGAL_ERASE_ARGUMENT" << endl;
            }
        } else if (opt == "defragment") {  // 内存整理
            for (block* ptr = head; ptr->next; ptr = ptr->next) {
                if (ptr->next->L > ptr->R) {  // 有空位则左移
                    int dist = ptr->next->L - ptr->R;
                    ptr -> next -> L -= dist;
                    ptr -> next -> R -= dist;
                }
            }
        }
    }
    return 0;
}

平均方差

  没啥难度，直接计算即可，注意输出时要强制转 int 而不能 printf("%.0lf", S/n - 0.5);，否则会出现输出 -0 的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

double sum, arr[10000];


int main() {  // 这题就不用标注释了吧……
    int n; cin >> n;
    while (n) {
        sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
            sum += arr[i];
        }

        double avg = sum / n, S = 0;
        for (int i = 0; i < n; i++) {
            S += (arr[i]-avg)*(arr[i]-avg);
        }
        cout << (int)(S / n) << endl;
        cin >> n;
    }
    return 0;
}

IP 地址

  使用位运算是最快的解法，具体位运算的使用参考汉明距离一章

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
#include <bits/stdc++.h>
using namespace std;

// 正整数的负在计算机中表现为二进制先取反再加一，与 n 作与运算后即可得到该数最低位的 1
int count(int n) {  
    int ans = 0;
    while (n) {
        n ^= (n & -n);
        ans++;
    }
    return ans;
}

int main() {
    int n; cin >> n;
    while (n--) {
        int arr[4];
        scanf("%d.%d.%d.%d", &arr[0], &arr[1], &arr[2], &arr[3]);
        int sum = 0;
        for (int i = 0; i < 4; i++) {
            sum += count(arr[i]);
        }
        cout << sum << endl;
    }
    return 0;
}

开关与灯

  将输入矩阵纵向相加，得到「每个灯所对应的开关数」数组，然后使用一重循环，判断上述数组减去单个开关后，新的「每个灯对应的开关数」数组中是否存在 0，如果存在，则说明该开关不可去除，否则输出 Yes 并返回

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 <bits/stdc++.h>
using namespace std;

int arr[2000] = {0};
bool button[2000][2000] = {0};

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {  // 读入
        string str; cin >> str;
        for (int j = 0; j < m; j++) {
            if (str[j] == '1') {
                button[i][j] = 1;  // 记录每个开关的情况
                arr[j] += 1;  // 同时统计每个灯对应的开关数
            }
        }
    }
    for (int i = 0; i < n; i++) {  // 依次判断
        bool flag = true;
        for (int j = 0; j < m; j++) {
            if (arr[j] <= button[i][j]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

可删除的点

  分别统计横坐标大于零和小于零的点的数量，并记为 LL、RR，只要 LL、RR 不全大于 1 则有解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

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

    int L = 0, R = 0;
    for (int i = 0; i < n; i++) {
        int x, _;
        cin >> x >> _;
        x > 0 ? R++ : L++;
    }
    printf((L <= 1 || R <= 1) ? "Yes" : "No");
    return 0;
}

字符串反转3

  最初的实现方式，直接用了 Python 现成的语法特性和内置函数：

1
2
3
4
5
n = int(input())

for i in range(n):
    print(' '.join(map(lambda x: x[::-1], input().split())))

  提交之后有一个点报超时，猜测可能存在卡常，遂改用 C++ 实现。维护一个字符栈，每次读入一个字符，如果不是空格或回车，则直接入栈；否则边出栈边输出，直到将整个栈清空，然后如果是回车，则退出循环

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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; cin >> T;
    getchar();  // 读掉换行符
    while (T--) {
        stack<char> st; char ch;
        while (true) {
            ch = getchar();  // 读一个字符
            if (ch == '\n' || ch == ' ') {  // 如果是空格或回车则反转输出
                while (!st.empty()) {
                    putchar(st.top());
                    st.pop();
                }
                putchar(' ');
                if (ch == '\n') {
                    putchar('\n');
                    break;
                }
            } else {  // 否则直接入栈
                st.push(ch);
            }
        }
    }
    return 0;
}

n， 还是n

  STL 真好用，直接暴搜就能过（话说一百万真的不会超时嘛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

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

    string n_str = to_string(n);
    for (int i = 1; i <= m; i++) {
        if (i % n == 0) {
            cout << i << " ";
        } else if (~to_string(i).find(n_str)) {  
            // find 找不到时会返回 -1，整数中只有 -1 经过按位取反（~）结果为 0
            cout << i << " ";
        }
    }
    return 0;
}

字符串排序

  虽然 n, m 都不大，但是保险起见，还是用一下缓存优化（防止 cmp 函数每次都计算无序度导致超时），外加 STL 中的 stable_sort（稳定排序）即可 AC

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
#include <bits/stdc++.h>
using namespace std;

int n, m;

struct pack {
    string str;
    int chaos = 0;

    void init() {
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (str[j] < str[i]) {
                    chaos += 1;
                }
            }
        }
    }

    bool operator < (const pack& other) const {  
        // 定义小于号，sort 默认按字典序排序，这里改为按「无序度」
        return chaos < other.chaos;
    }

    bool operator == (const pack& other) const {  // 定义等于号
        return str == other.str;
    }
} arr[100];

int main() {
    cin >> n >> m;
    for (int i = 0; i < m ; i++) {
        cin >> arr[i].str;
        arr[i].init();
    }
    stable_sort(arr, arr+m);  // STL 中的稳定排序，不会改变相同元素的顺序
    for (int i = 0; i < m; i++) {
        cout << arr[i].str << endl;
    }
    return 0;
}

三角形的面积

  简单计算几何，下面给出计算公式（可计算任意多边形）：

S=∣OPi→×OPi+1→2∣S = |\frac{\overrightarrow{OP_i}\times\overrightarrow{OP_{i+1}}}{2}|

其中 PiP_i 为该多边形第 ii 个顶点的坐标 (i∈[0,n),Pn=P0)(i\in[0, n), P_n = P_0)，直接套用公式算出答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

double P[3][2];  // 每个点的坐标

int main() {
    while (true) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 2; j++) {
                scanf("%lf", &P[i][j]);
            }
        }
        if (!(P[0][0] || P[0][1] || P[1][0] || P[1][1] || P[2][0] || P[2][1])) {
            break;
        }
        double sum = 0;
        for (int i = 0; i < 3; i++) {
            sum += P[i][0] * P[(i+1)%3][1] - P[(i+1)%3][0] * P[i][1];  // 算叉乘
        }
        printf("%.6lf\n", abs(sum / 2));
    }
    return 0;
}

  或者直接对三角形的两条边做叉乘：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main() {
    while (true) {
        double x1, y1, x2, y2, x3, y3;
        scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
        if (!(x1 || y1 || x2 || y2 || x3 || y3)) {
            break;
        }
        double sum = (x2-x1) * (y3-y1) - (x3-x1) * (y2-y1);  // 三角形任意两边作向量叉乘
        printf("%.6lf\n", abs(sum) / 2);
    }
    return 0;
}

循环数

  根据循环数的性质判断，循环数乘上它自己的 位数+1 会得到一串 9 【Wiki 传送门】，另外特判一个 0 即可：

1
2
3
4
5
6
7
8
9
10
num = input()

if int(num):
    if set(str(int(num) * (len(num)+1))) == {'9'}:
        print('Yes')
    else:
        print('No')
else:
    print('Yes')

电能消耗

  lil_i、rir_i 均不大于 1440，无需使用数学计算加速，直接暴力模拟每分钟的电量消耗即可。此外题目描述有误，汤姆使用电脑的时间周期应为左闭合区间 [l1,r1)[l_1, r_1)、[l2,r2)[l_2, r_2)、……、[ln,rn)[l_n, r_n)

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
#include <bits/stdc++.h>
using namespace std;

bool work[2000] = {0};  // 标记每分钟电脑的使用情况

int main() {
    int n, p1, p2, p3, t1, t2;
    cin >> n >> p1 >> p2 >> p3 >> t1 >> t2;

    int L, R;
    for (int i = 0; i < n; i++) {
        int l, r; cin >> l >> r;
        (i == 0) && (L = l);
        (i == n-1) && (R = r);
        for (int j = l; j < r; j++) {
            work[j] = 1;
        }
    }

    int sum = 0, idle;
    for (int i = L; i < R; i++) {
        if (work[i]) {
            idle = 0;
            sum += p1;
        } else {
            if (idle >= t1 + t2) {  // 进入睡眠模式
                sum += p3;
            } else if (idle >= t1) {  // 屏幕保护程序启动
                sum += p2;
            } else {  // 标准模式
                sum += p1;
            }
            idle++;
        }
    }
    cout << sum << endl;
    return 0;
}

计算校验码

  根据题目最后的 Tips，不难发现无论输入的 N 是几进制数，都不会对各位数字之和产生影响，不妨设各位数字之和为 xx，校验码为 mm，可得：

m=[(B−1)−x mod (B−1)] mod (B−1)m = [(B-1) - x \text{ mod } (B-1) ]\text{ mod }(B-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
#include <bits/stdc++.h>
using namespace std;

int sum_count(string str) {
    int sum = 0;
    for (char ch : str) {
        if ('0' <= ch && ch <= '9') {
            sum += ch - '0';
        } else {
            sum += 10 + ch - 'a';
        }
    }
    return sum;
}

int main() {
    int T; cin >> T;
    const string digits = "0123456789abcdef";
    while (T--) {
        int B;
        string N;
        cin >> B >> N;

        int m = ((B-1) - sum_count(N) % (B-1)) % (B-1);
        cout << digits[m] << endl;
    }
    return 0;
}

训练作业二

字符串反转2

  依旧先试 Python 硬怼，这一次没有超时：

1
2
3
4
5
try:
    while True:
        print(' '.join(input().split()[::-1]))
except EOFError:
    pass

487-3279

  每次输入电话号码后先格式化，然后使用 STL 中的 map 统计频次，最后选取频次大于 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
32
33
34
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    map<string, int> count;
    while (n--) {
        string str, wrap;
        cin >> str;
        for (char ch : str) {
            if ('A' <= ch && ch <= 'Z') {
                (ch >= 'Q') && ch--;
                wrap += (ch-'A')/3 + '2';
            } else if ('0' <= ch && ch <= '9') {
                wrap += ch;
            }
        }
        count[wrap] += 1;
    }
    for (auto item : count) {
        if (item.second > 1) {
            for (int i = 0; i < 3; i++) {  // 分段输出
                putchar(item.first[i]);
            }
            putchar('-');
            for (int i = 3; i < 7; i++) {
                putchar(item.first[i]);
            }
            cout << " " << item.second << endl;
        }
    }
    return 0;
}

缺席考试的是谁？

  对所有名字作一次异或运算，最后剩下的即为缺席学生的姓名，很神奇吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    while (n) {
        char name[64] = {0};
        for (int i = 0; i < 2*n-1; i++) {
            char tmp[64];
            scanf("%s", tmp);
            for (int j = 0; tmp[j]; j++) {
                name[j] ^= tmp[j];
            }
        }
        printf("%s\n", name);
        cin >> n;
    }
    return 0;
}

电话号码

  使用字典树存储电话号码的逆，可以很方便的去除重复的电话号码，对所有朋友分别建一棵字典树，存入逆序的电话号码后直接排序输出即可（注意题目要求是先按长度，再按数字大小排序）。

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
#include <bits/stdc++.h>
using namespace std;

struct Trie {  // 字典树
    char ch = '\0';
    Trie* next[10] = {0};

    void insert(const string& str, int pos=0) {  // 递归插入
        if (pos < str.size()) {
            int index = str[pos] - '0';
            if (!next[index]) {
                next[index] = new Trie;
                next[index] -> ch = str[pos];
            }
            next[index] -> insert(str, pos+1);
        }
    }

    void count(vector<string>& arr, string str="") {  // 将字典树中的所有单词放入 arr 中
        bool flag = false;
        for (int i = 0; i < 10; i++) {
            if (next[i]) {
                flag = true;
                // 这里的三目运算符用于去除根节点的空字符
                next[i] -> count(arr, ch ? ch + str : str);   
            }
        }
        if (!flag) {
            arr.push_back(ch+str);
        }
    }
};

map<string, Trie> book;

int main() {
    int T; cin >> T;
    while (T--) {
        string name; int n;
        cin >> name >> n;
        for (int i = 0; i < n; i++) {
            string phone; cin >> phone;
            // 反转后插入字符串
            reverse(phone.begin(), phone.end());
            book[name].insert(phone);
        }
    }
    cout << book.size() << endl;
    for (auto record : book) {  // map 中默认 key 按从小到大排序，这里不需要额外的排序过程
        vector<string> arr;
        record.second.count(arr);
        sort(arr.begin(), arr.end(), [] (const string& a, const string& b) {  // 按题目要求对号码排序
            if (a.size() < b.size()) return true;
            return atoi(a.c_str()) < atoi(b.c_str());
        });
        cout << record.first << " " << arr.size() << " ";
        for (auto name : arr) {
            cout << name << " ";
        }
        cout << endl;
    }
    return 0;
}

点球大战

  模拟即可

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 <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    while (n) {
        char result[10][2] = {0};
        for (int i = 0; i < n; i++) {  // 统计结果
            string str;
            do {
                cin >> str;
            } while(str != "no" && str != "good");
            if (str == "no") {
                result[i >> 1][i & 1] = 'X';
                cin >> str;
            } else {
                result[i >> 1][i & 1] = 'O';
            }
        }

        for (int i = 0; i < (n + 1)/2; i++) {  // 输出场次
            cout << (i + 1) << " ";
        }
        cout << "Score" << endl;

        for (int i = 0; i < 2; i++) {  // 打印
            int cnt = 0;
            for (int j = 0; j < (n + 1)/2; j++) {
                if (result[j][i]) {
                    cnt += result[j][i] == 'O';
                    cout << result[j][i] << " ";
                } else {
                    cout << "- ";
                }

            }
            cout << cnt << endl;
        }
        cin >> n;
    }
    return 0;
}

飞行棋

  模拟题，一个比较方便的技巧是将棋盘直接初始化为应该跳转到的格

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
#include <bits/stdc++.h>
using namespace std;

struct Random {  // 骰子类
    int a, b, f;
    Random(int a_, int b_, int c_) {
        a = a_, b = b_, f = c_;
    }
    int operator() () {
        f = (a*f + b) % 6 + 1;
        return f;
    }
};

int main() {
    int n, a, b, c;
    while (cin >> n >> a >> b >> c) {
        int gmap[200] = {0};  // 生成「游戏地图」
        for (int i = 0; i < n; i++) {
            string str; cin >> str;
            if (str[0] == 'N') {
                gmap[i] = i;
            } else {
                gmap[i] = atoi(str.substr(1, string::npos).c_str());
            }
        }
        auto dice = Random(a, b, c);  // 生成一个骰子
        int pos[2] = {0};  // 两人的位置
        for (int i = 0, i_ = 0; ; i_++, i = i_ & 1) {
            pos[i] += dice();  // 摇骰子
            while (pos[i] >= n || pos[i] < 0) {  // 处理坐标超范围的情况
                (pos[i] >= n) && (pos[i] = 2*(n-1)-pos[i]);
                (pos[i] < 0) && (pos[i] = -pos[i]);
            }
            // 跳转（如果该格子为 N 就是原地跳转，上面生成地图的部分有相关代码）
            pos[i] = gmap[pos[i]];  
            if (pos[i] == n-1) {  // 如果有人赢了则结束游戏
                printf("%s\n", i & 1 ? "Yueyue" : "Lele");
                break;
            }
            if (pos[i] == pos[!i]) {  // 处理相遇时踢回起点的情况
                pos[!i] = 0;
            }
        }
    }
    return 0;
}

棋盘

  动态规划题，用 map[][] 存储输入数据，数组 F1[i][j] 表示以 [i, j] 为右下角的最大黑色网格（主对角线为黑色）大小，类似地 F2[i][j] 表示最大白色网格的大小，那么可以导出递推式：

F1[i,0]=F1[0,j]=F2[i,0]=F2[0,j]=0F_1[i, 0] = F_1[0, j] = F_2[i, 0] = F_2[0, j] = 0

F1[i,j]={min⁡(F1[i−1,j−1],F2[i−1,j],F2[i,j−1])+10,(map[i][j]=0)F_1[i, j] = \begin{cases} \min(F_1[i-1, j-1], F_2[i-1, j], F_2[i, j-1]) + 1 \\ 0, (map[i][j] = 0) \end{cases}

F2[i][j]={min⁡(F2[i−1,j−1],F1[i−1,j],F1[i,j−1])+10,(map[i][j]=0)F_2[i][j] = \begin{cases} \min(F_2[i-1, j-1], F_1[i-1, j], F_1[i, j-1]) + 1 \\ 0, (map[i][j] = 0) \end{cases} 

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
#include <bits/stdc++.h>
using namespace std;

bool gmap[2001][2001] = {0};
int F1[2001][2001] = {0},  // 黑色 - 1
    F2[2001][2001] = {0};  // 白色 - 0

int main() {
    int n; cin >> n; getchar();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            gmap[i][j] = getchar() - '0';
        }
        getchar();
    }
    int max_size = 0;
    // 按状态转移方程做动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (gmap[i][j]) {  // 黑色
                F1[i][j] = min(F1[i-1][j-1], min(F2[i-1][j], F2[i][j-1])) + 1;
                F2[i][j] = 0;
            } else {
                F2[i][j] = min(F2[i-1][j-1], min(F1[i-1][j], F1[i][j-1])) + 1;
                F1[i][j] = 0;
            }
            max_size = max(max_size, F1[i][j]);
        }
    }
    // 此时已经知道最大的棋盘大小，最后用双重循环统计数量
    int count = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (F1[i][j] == max_size) {
                count++;
            }
        }
    }
    cout << max_size << " " << count << endl;
    return 0;
}

Engine-字符串

  模拟题，直接 Python 过了

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
class Paper(object):
    def __init__(self):
        self.title = input()
        self.keys = set(s.lower() for s in self.title.split())
        self.refers = int(input())


def query(keywords):
    return lambda p: all(word in p.keys for word in keywords)


def main():
    n = int(input())
    while n:
        papers = []
        for i in range(n):
            papers.append(Paper())
        m = int(input())
        for i in range(m):
            title = input()
            keywords = [word.lower() for word in title.split()]

            for p in sorted(filter(query(keywords), papers), key=lambda x: -x.refers):
                print(p.title)
            print('***')
        print('---')
        n = int(input())


if __name__ == '__main__':
    main()

字符串压缩

  动态规划题，如果用数组 F1[i]F_1[i] 表示以第 ii 个字符结尾的子串所需的最小钱币数，那么不难想到下面的递推式：

F[i]=min⁡(F[i−1]+a,min⁡{F[i−len]}+b)F[i] = \min(F[i-1] + a, \min\{F[i-len]\} + b)

解释：

  •  如果添加第 ii 个字符后不能构成前面字符串的子串，则花费 a 金币将其直接编码

  •  如果添加第 ii 个字符后，新串的最后 lenlen 位为前面的子串，则可以先编码前面的 i−leni-len 个字符，再花费 bb 金币编码最后的 lenlen 位字符

  此时发现题目的一个 bug 点，题目描述中没有说明 b≤ab\leq a，那么如果 b>ab > a，就没有办法证明取最长公共后缀的最优子结构性质，于是没法在 O(n2)O(n^2) 的时间内解决问题，导致超时（也许是我太菜了没想到）

  由于我太懒了，不想慢慢研究最长公共后缀的 DP（O(n2)O(n^2) 解法），这里放一个传送门，然后我将使用 O(n3)O(n^3) 的暴力方法求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, a, b;
    string str;
    cin >> n >> a >> b >> str;
    vector<int> F(n);
    F[0] = a;
    for (int i = 1; i < n; i++) {
        F[i] = F[i-1] + a;
        for (int j = 1; j*2 <= i+1; j++) {
            // 右值引用避免字符串复制开销
            string&& L = str.substr(0, i+1-j);
            string&& R = str.substr(i+1-j, j);
            if (L.find(R) != string::npos) {
                F[i] = min(F[i], F[i-j] + b);
            }
        }
    }
    cout << F[str.size() - 1] << endl;
    return 0;
}

拼写检查

  经典动态规划问题——编辑距离，稍微做些优化直接搬上来用就行了，它的状态转移方程为：

F[0,i]=F[i,0]=iF[0, i] = F[i, 0] = i

F[i,j]=min⁡(F[i−1][j]+1,F[i][j−1]+1,F[i−1][j−1]+(a[i]!=b[j]))F[i, j] = \min(F[i-1][j] + 1, F[i][j-1] + 1, F[i-1][j-1] + (a[i] != b[j]))

  其中 F[i,j]F[i,j] 表示字符串 a 的前 i 个字符组成的子串和字符串 b+1 的前 j+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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

bool canfix(string src, string dst) {  // 计算字符串编辑距离
    int F[20][20] = {0};
    int s_len = src.size(), d_len = dst.size();
    for (int i = 0; i < 20; i++) {
        F[i][0] = F[0][i] = i;
    }
    for (int i = 0; i < s_len; i++) {
        for (int j = 0; j < d_len; j++) {
            F[i+1][j+1] = min(F[i][j], min(F[i][j+1], F[i+1][j])) + 1;
            if (src[i] == dst[j]) {
                F[i+1][j+1] = min(F[i+1][j+1], F[i][j]);
            }
        }
    }
    return F[s_len][d_len] <= 1;
}

vector<string> dict;

int main() {
    string word; cin >> word;
    while (word != "#") {
        dict.push_back(word);
        cin >> word;
    }
    cin >> word;
    while (word != "#") {
        if (find(dict.begin(), dict.end(), word) != dict.end()) {  // 如果字典中有则认为正确
            cout << word << " is correct" << endl;
        } else {  // 否则尝试纠错
            cout << word << ": ";
            for (string str : dict) {
                if (canfix(word, str)) {  // 编辑距离为 1 则输出该替换
                    cout << str << " ";
                }
            }
            cout << endl;
        }
        cin >> word;
    }
    return 0;
}

  • 更新：BK 树解法（最后一个排序做得比较随意，懒得慢慢改树了）
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
#include <bits/stdc++.h>
using namespace std;

int edt(const string& src, const string& dst) {  // 计算字符串编辑距离
    int F[20][20] = {0};
    int s_len = src.size(), d_len = dst.size();
    for (int i = 0; i < 20; i++) {
        F[i][0] = F[0][i] = i;
    }
    for (int i = 0; i < s_len; i++) {
        for (int j = 0; j < d_len; j++) {
            F[i+1][j+1] = min(F[i][j], min(F[i][j+1], F[i+1][j])) + 1;
            if (src[i] == dst[j]) {
                F[i+1][j+1] = min(F[i+1][j+1], F[i][j]);
            }
        }
    }
    return F[s_len][d_len];
}

struct bk_tree {
    string word;
    map<int, bk_tree> child;

    void insert(const string& str) {
        int ed_root = edt(word, str);  // 计算到根节点的编辑距离
        if (child.find(ed_root) == child.end()) {
            child[ed_root] = {str};
        } else {
            child[ed_root].insert(str);
        }
    }

    void query(const string& str, vector<string>& res) {  // 查询
        int ed_root = edt(word, str);
        if (ed_root <= 1) res.push_back(word);
        for (auto item : child) {
            if (item.first >= ed_root - 1 && ed_root <= ed_root + 1) {
                item.second.query(str, res);
            }
        }
    }
};

int main() {
    string str; cin >> str;
    bk_tree dict = {"#:#:#"};
    set<string> cnt;
    map<string, int> weight; int index = 0;
    while (str != "#") {
        dict.insert(str), cnt.insert(str);
        weight[str] = index++;
        cin >> str;
    }
    cin >> str;
    while (str != "#") {
        if (cnt.find(str) != cnt.end()) {
            cout << str << " is correct" << endl;
        } else {
            cout << str << ": ";
            vector<string> arr;
            dict.query(str, arr);
            sort(arr.begin(), arr.end(), [&weight] (const string& a, const string& b) {
                return weight[a] < weight[b];
            });
            for (auto fix : arr) {
                cout << fix << " ";
            }
            cout << endl;
        }
        cin >> str;
    }
    return 0;
}

最小的 K 个数

  按题目提示做即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

set<int> data;

int main() {
    int n, k;
    cin >> n >> k;
    while (n--) {
        int tmp; cin >> tmp;
        data.insert(tmp);
    }
    for (auto it = data.begin(); k-- && it != data.end(); it++) {
        cout << *it << " ";
    }
    return 0;
}

绩点计算

  按题目意思算即可

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
#include <bits/stdc++.h>
using namespace std;

float mark2point(int mark) {
    if (mark >= 90) return 4.0;
    if (mark >= 85) return 3.7;
    if (mark >= 82) return 3.3;
    if (mark >= 78) return 3.0;
    if (mark >= 75) return 2.7;
    if (mark >= 72) return 2.3;
    if (mark >= 68) return 2.0;
    if (mark >= 64) return 1.5;
    if (mark >= 60) return 1.0;
    return 0;
}

int main() {
    int n; cin >> n;
    int weight[1000];
    float sum_weight = 0, sum_mp = 0;
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
        sum_weight += weight[i];
    }
    for (int i = 0; i < n; i++) {
        int mark; cin >> mark;
        sum_mp += weight[i] * mark2point(mark);
    }
    printf("%.2f", sum_mp / sum_weight);
    return 0;
}

xxx定律

  直接模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    while (n) {
        int step = 0;
        while (n != 1) {
            if (n & 1) {
                n = 3*n + 1;
            }
            n >>= 1;
            step++;
        }
        cout << step << endl;
        cin >> n;
    }
    return 0;
}

数的距离差

  对题中距离差定义简单整理，可知 x 是数组中与 max+min2\frac{max+min}{2} 最接近的那个数，这里直接 O(nlog⁡n)O(n\log n) 求解：

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

int main() {
    int n; cin >> n;
    vector<int> arr;
    for (int i = 0; i < n; i++) {
        int tmp; cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    float m = (float) (arr[0] + arr[arr.size()-1]) / 2;
    for (auto it = arr.rbegin(); it != arr.rend(); it++) {
        if (*it <= m) {
            cout << *it << endl;
            break;
        }
    }
    return 0;
}

亲和数

  直接暴力：

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
#include <bits/stdc++.h>
using namespace std;

int factor_sum(int n) {
    int sum = 0;
    for (int i = 1; i*2 <= n; i++) {
        if (n % i == 0) {
            sum += i;
        }
    }
    return sum;
}

int main() {
    int A, B;
    while (cin >> A >> B) {
        if (factor_sum(B) == A && factor_sum(A) == B) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

金币

  暴力计算即可，但要注意将之前的计算结果保存下来，防止重复计算导致超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int now = 0;
vector<int> arr = {0};
void update(int n) {  // 向后算到至少第 n 天
    while (arr.size() <= n) {
        now += 1;
        for (int i = 0; i < now; i++) {
            arr.push_back(*arr.rbegin() + now);
        }
    }
}

int main() {
    int n;
    while (cin >> n) {
        update(n);
        cout << n << " " << arr[n] << endl;
    }
    return 0;
}

小 A 的计算器

  不必写进制转换，直接在数组上做加法，逆序存储（个位在最前）可以大幅优化进位效率

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 <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    while (n--) {
        string a, b;
        cin >> a >> b;
        int len_a = a.size(), len_b = b.size();

        int ans[1000] = {0};
        for (int i = 0; i < len_a; i++) {
            ans[i] += a[len_a-i-1] - 'a';
        }
        for (int i = 0; i < len_b; i++) {
            ans[i] += b[len_b-i-1] - 'a';
        }
        stack<char> st;  // 反转后输出
        for (int i = 0; ans[i]; i++) {
            if (ans[i] >= 26) {
                ans[i+1] += ans[i] / 26;
                ans[i] %= 26;
            }
            st.push(ans[i] + 'a');
        }
        while (!st.empty()) {
            putchar(st.top());
            st.pop();
        }
        cout << endl;
    }
    return 0;
}

小丑排序

  从头开始，每次走两步并输出，碰到数组尾端后返回，继续输出之前没输出过的名字：

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 <bits/stdc++.h>
using namespace std;

int main() {
    string arr[20];
    int n, T = 1; cin >> n;
    while (n) {
        cout << "set-" << T++ << endl;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int vst[20] = {0};
        for (int i = 0; i < n; i += 2) {
            cout << arr[i] << endl;
            vst[i] = 1;
        }
        for (int i = n-1; i > 0; i--) {
            if (!vst[i]) {
                cout << arr[i] << endl;
            }
        }
        cin >> n;
    }
    return 0;
}

数圈

  先求出中心坐标，然后向外旋转填数，最后整体输出

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 <bits/stdc++.h>
using namespace std;

int arr[11][11] = {0};
int ways[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}, dir = 3;

void fill(int n) {
    int x, y, cnt = 1;
    x = y = (n-1)/2;
    for (int i = 1; ; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < i; k++) {
                arr[x][y] = cnt++;
                if (cnt > n * n) {
                    return;
                }
                x +=  ways[dir][0], y += ways[dir][1];
            }
            dir = (dir + 1) % 4;
        }
    }
}

int main() {
    int n; cin >> n;
    fill(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

锤子剪刀布

  直接模拟并记录比赛结果，这题代码写得比较长，但应该逻辑都挺清晰

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
#include <bits/stdc++.h>
using namespace std;

inline char read() {
    char ch = getchar();
    while (ch < 'A' || ch > 'Z') {
        ch = getchar();
    }
    return ch;
}

int win_A[3] = {0}, win_B[3] = {0};

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        char A = read(), B = read();
        if (A == 'B' && B == 'C') {
            win_A[0]++;
        } else if (A == 'C' && B == 'J') {
            win_A[1]++;
        } else if (A == 'J' && B == 'B') {
            win_A[2]++;
        }
        if (B == 'B' && A == 'C') {
            win_B[0]++;
        } else if (B == 'C' && A == 'J') {
            win_B[1]++;
        } else if (B == 'J' && A == 'B') {
            win_B[2]++;
        }
    }
    int sum_A = win_A[0] + win_A[1] + win_A[2];
    int sum_B = win_B[0] + win_B[1] + win_B[2];
    printf("%d %d %d\n", sum_A, n-sum_A-sum_B, sum_B);
    printf("%d %d %d\n", sum_B, n-sum_A-sum_B, sum_A);
    char most_A, most_B;
    int max_A = -1, max_B = -1;
    for (int i = 0; i < 3; i++) {
        if (win_A[i] > max_A) {
            max_A = win_A[i];
            most_A = "BCJ"[i];
        }
        if (win_B[i] > max_B) {
            max_B = win_B[i];
            most_B = "BCJ"[i];
        }
    }
    cout << most_A << " " << most_B;
    return 0;
}

新型冠状病毒（COVID19）传播

  想要直接计算出所有的感染者难度过大，那么不妨反向思考，找出不可能被感染的人，然后用总人数减去，同样也可以得到最终答案

  不难发现，以下两类人一定会被感染：

  • 开始时跑在感染者后面，且速度大于感染者

  • 开始时跑在感染者前面，且速度小于感染者

  当这两类人被感染之后，又成为新的感染者，随着时间的推进，已经被感染的人又会去感染其他人；有没有新的人被感染，是根据当前已经被感染的人的最大和最小速度决定的，随之可以注意到，以下两类人永远不会被感染：

  • 开始时跑在感染者前面，且比感染者和他后面所有人跑得都快

  • 开始时跑在感染者后面，且比感染者和他前面所有人跑的都慢

  通过一次循环统计出最大和最小速度，然后再用一重循环统计不可能感染的人数即可：

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 <bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;

int main() {
    // 输入部分
    int n, k;
    cin >> n >> k; k--;
    vector<int> s(n), v(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    int v_min = inf, v_max = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] <= s[k]) {  // 感染者和他后面的人中的最大速度
            v_max = max(v_max, v[i]);
        }
        if (s[i] >= s[k]) {  // 感染者和他前面的人中的最小速度
            v_min = min(v_min, v[i]);
        }
    }

    int impossible = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] > s[k] && v[i] >= v_max) {  // 跑在前面，且比最快的感染者跑得还快
            impossible++;
        }
        if (s[i] < s[k] && v[i] <= v_min) {  // 跑在后面，且比最慢的感染者跑得还慢
            impossible++;
        }
    }

    cout << (n - impossible) << endl;
    return 0;
}

训练作业三

部分 A + B

  先按字符串读入，然后遍历取出 PAP_A 和 PBP_B，最后相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
    string sA, dA, sB, dB;
    cin >> sA >> dA >> sB >> dB;
    int A = 0, B = 0;
    for (char ch : sA) {
        if (ch == dA[0]) {
            A = A * 10 + ch - '0';
        }
    }
    for (char ch : sB) {
        if (ch == dB[0]) {
            B = B * 10 + ch - '0';
        }
    }
    cout << A + B << endl;
    return 0;
}

导弹防御系统

  经典动态规划问题，定义 F[i]F[i] 表示必须拦截第 ii 颗导弹的前提下最多能拦截的导弹数，易得状态转移方程：

F[i]=max⁡(1,max⁡(F[i−j])+1),(arr[j]>=arr[i]))F[i] = \max(1, \max(F[i-j]) + 1), (arr[j] >= arr[i]))

  初始化数组 F[] 为 1，然后按上述方程演算：

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

int main() {
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    vector<int> F(n, 1);  // F[i] 表示在必须拦截第 i 枚导弹的情况下所能取到的最大长度
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] >= arr[i]) {
                F[i] = max(F[i], F[j] + 1);
            }
        }
    }
    cout << *max_element(F.begin(), F.end()) << endl;
    return 0;
}

魔咒词典

  字符串处理的题当然要用 Python 啦，使用正则表达式从输入字符串提取出魔咒和功能说明，然后正反向均建立映射，查询时输出即可（其实 C++ 也有正则表达式相关的库澳）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import re

book = {}

while True:
    line = input()
    if line == '@END@':
        break
    word, func = re.findall(r'(\[.*]) (.*)', line)[0]
    book[word] = func
    book[func] = word[1:-1]

n = int(input())
for i in range(n):
    line = input()
    if line in book:
        print(book[line])
    else:
        print('what?')


打牌

  首先统计每种牌的数量，然后每次输入一行对手的出牌，如果不是顺子（长度 < 5），则按普通规则，否则按顺子规则判断，具体实现看下面代码中的注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
raw = input()
my_cards = [raw.count(str(x)) for x in range(1, 10)]  # 统计每种牌的数量

try:  #: T3-4
    while True:
        line = input()
        first, length, ans = line[0], len(line), []
        if length < 5:  # 不是顺子时的规则
            for i in range(int(first), 9):
                if my_cards[i] >= length:  # 如果数量足够则判断能压过
                    ans.append(str(i+1) * length)
        else:
            for i in range(int(first), 5):  # 顺子最多以 5 开头
                if all(my_cards[i:i+5]):  # 判断是否能出顺子
                    ans.append(str(i * 11111 + 12345))
        if ans:
            print('YES', ' '.join(ans))
        else:
            print('NO')
except EOFError:
    pass

最大报销额

  题目描述不清不楚的，不想写了

带通配符的数

  递归求解，主要逻辑有三条（其实就是整数比较大小的规则）：

  • 如果 WW 的某一位与 XX 的相同，那么他们的大小由后面的位决定

  • 如果 WW 的某一位比 XX 的小，那么后面无论怎么取都不可能使 W>XW > X

  • 如果 WW 的某一位比 XX 的大，那么后面的所有「?」都可以随意取值（0 ~ 9）

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
#include <bits/stdc++.h>
using namespace std;

int dfs(const string& str, const string& raw, int index=0) {  // 返回可能的情况数
    if (index > str.size()) {  // 边界条件
        return 0;
    }
    if (str[index] == '?') {
        int sum = 0, cnt = 1;
        for (int i = index + 1; i < str.size(); i++) {
            (str[i] == '?') && (cnt *= 10);
        }
        sum += cnt * ('9' - raw[index]);
        sum += dfs(str, raw, index + 1);
        return sum;
    } else {
        if (str[index] == raw[index]) {
            return dfs(str, raw, index + 1);
        }
        if (str[index] > raw[index]) {
            int cnt = 1;
            for (int i = index + 1; i < str.size(); i++) {
                (str[i] == '?') && (cnt *= 10);
            }
            return cnt;  // str[index] < raw[index]
        }
        return 0;
    }
}

int main() {
    string str, raw;
    while (cin >> str >> raw) {
        cout << dfs(str, raw) << endl;
    }
    return 0;
}

愚人节的礼物

  遍历字符串，遇左括号计数器 +1，右括号 -1，礼物 B 出现时计数器的值即为层数：

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
#include <bits/stdc++.h>
using namespace std;

void unpack(string str) {
    int cnt = 0;
    for (char ch : str) {
        if (ch == '(') {
            cnt += 1;
        } else if (ch == ')') {
            cnt -= 1;
        } else {
            cout << cnt << endl;
            return;
        }
    }
}

int main() {
    string str;
    while (cin >> str) {
        unpack(str);
    }
    return 0;
}

ab 串

  这是一道动态规划题（虽然不知道为啥算法标签是前缀和，可能有更妙的方法？）。将 dp 过程中查找的字符串分为 3 个状态，状态 A 为只有 a 的串（aa……a），状态 B 为 a 和 b 的串（aa……aabb……bb），状态 C 为题目要求的串（aaa……aabb……bbaa……aaa）。

  设 F[i,j]F[i, j] 表示在状态 i 下，前 j 个字符中所能取到的最大长度，那么对于状态 A，从 0 到 j 位中字符 'a' 的个数即为其值；而对于状态 B 和 C，分两种情况讨论：

  • 第 j 个字符为对应状态的最后一个字符（状态 B 为 'b'，状态 C 为 'a'）：

  直接从左边转移，即 F[i,j]=F[i,j−1]+1F[i, j] = F[i, j-1] + 1

  • 第 j 个字符与状态最后一个字符不同：

  从左边和上一状态转移，即： F[i,j]=max⁡(F[i,j−1],F[i−1,j])F[i, j] = \max(F[i, j-1], F[i-1, j])

  依照上述三条规则，将数组 F[][] 推演到 F[2][len] 即可得到答案：

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
#include <bits/stdc++.h>
using namespace std;

int F[3][5001] = {0};

int main() {
    string str; cin >> str;
    int length = str.size();

    for (int i = 1; i <= length; i++) {  // 状态 A
        F[0][i] = F[0][i-1] + (str[i-1] == 'a');
    }

    for (int i = 1; i <= length; i++) {  // 状态 B
        if (str[i-1] == 'b') {
            F[1][i] = F[1][i-1] + 1;
        } else {
            F[1][i] = max(F[1][i-1], F[0][i]);
        }
    }

    for (int i = 1; i <= length; i++) {  // 状态 C
        if (str[i-1] == 'a') {
            F[2][i] = F[2][i-1] + 1;
        } else {
            F[2][i] = max(F[2][i-1], F[1][i]);
        }
    }

    cout << F[2][length] << endl;
    return 0;
}

占座位

  与 1-10 的内存管理几乎如出一辙，直接拿来改改交了

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
#include <bits/stdc++.h>
using namespace std;

struct block {
    int id, L, R;  // 经典左闭合
    block* next = NULL;

    block(int id_, int L_, int R_) {
        id = id_, L = L_, R = R_;
    }
};

int main() {
    int n, _, T;
    cin >> n >> _ >> T;

    block* head = new block(0, -1, 0);
    set<int> record;
    while (T--) {
        string opt; int id;
        cin >> opt >> id;
        if (opt == "in") {
            int arg; cin >> arg;
            if (record.find(id) != record.end()) {  // 判断是否已经占过座位
                cout << "no" << endl;
                continue;
            }
            record.insert(id);  // 打上标记
            bool flag = false;  // 标记是否分配成功
            for (block* ptr = head; ptr; ptr = ptr->next) {  // 从表头向后查找，每次检查是否能在当前位置之后分配座位
                if (ptr -> next) {  // 在 “中间” 插入块
                    if (ptr->next->L - ptr->R >= arg) {  // 如果空间足够则新建一个块
                        block* tmp = new block(id, ptr->R, ptr->R + arg);
                        tmp -> next = ptr -> next;
                        ptr -> next = tmp;

                        cout << "yes" << endl;
                        flag = true;
                        break;
                    }
                } else {  // 在最后追加块
                    if (ptr->R + arg <= n*n) {  // 否则尝试在最后添加块
                        block* tmp = new block(id, ptr->R, ptr->R + arg);
                        ptr -> next = tmp;

                        cout << "yes" << endl;
                        flag = true;
                        break;
                    }
                }
            }
            if (!flag) {
                record.erase(id);  // 一个也不要了
                cout << "no" << endl;
            }
        } else if (opt == "out") {  // 删除块
            bool flag = false;  // 标记是否找到目标块
            for (block* ptr = head; ptr->next; ptr = ptr->next) {
                if (ptr->next->id == id) {
                    block* tmp = ptr->next;
                    ptr -> next = ptr -> next -> next;
                    delete tmp;
                    flag = true;
                    record.erase(id);  // 删除标记
                    break;
                }
            }
            if (flag) {
                cout << "yes" << endl;
            } else {
                cout << "no" << endl;
            }
        }
    }
    return 0;
}

Maya 历法

  字符串题怎么能不用 Python 呢？先根据 Haab 历法的日期算出从世界的开始到现在的总天数，然后再转为 Tzolkin 历法的日期输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import re

Haab = [  # Haab 历法的月份
    'pop', 'no', 'zip', 'zotz', 'tzec', 'xul', 'yoxkin', 'mol', 'chen', 'yax',
    'zac', 'ceh', 'mac', 'kankin', 'muan', 'pax', 'koyab', 'cumhu', 'uayet'
]

Tzolkin = [  # Tzolkin 历法的名字
    'imix', 'ik', 'akbal', 'kan', 'chicchan', 'cimi', 'manik', 'lamat', 'muluk', 'ok',
    'chuen', 'eb', 'ben', 'ix', 'mem', 'cib', 'caban', 'eznab', 'canac', 'ahau'
]

n = int(input())

for _ in range(n):
    day, month, year = re.search(r'(\d+)\.([a-z]+) (\d+)', input()).groups()
    total = int(year)*365 + 20*Haab.index(month) + int(day)

    day, month, year = total % 13 + 1, Tzolkin[total % 20], total // 260
    print(day, month, year)

数码管

  使用一个七位二进制数表示字符在数码管中的形状（对应位点亮为 1，否则为 0），然后若两个数字仅通过加减笔画的方式转换，设它们的段码分别为 AA、BB，则有：

A\text{ | }B = \max(A, B) \qquad A\text{ & }B = \min(A, B)

  依此性质编写代码：

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
#include <bits/stdc++.h>
using namespace std;

// 按七段显示器模式编码
const int digits[] = {
    0b1110111, 0b0100100, 0b1011101, 0b1101101, 0b0101110,
    0b1101011, 0b1111011, 0b0100101, 0b1111111, 0b1101111
};

int main() {
    while (true) {
        int now; cin >> now;
        if (!~now) break;

        bool flag = true;
        for (int i = 1; i < 10; i++) {
            int tmp; cin >> tmp;
            if ((digits[now] & digits[tmp]) != min(digits[now], digits[tmp]) ||
                    (digits[now] | digits[tmp]) != max(digits[now], digits[tmp])) {
                flag = false;
            }
            now = tmp;
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
    return 0;
}

多项式加法

  用 map 处理次数和系数的对应关系，注意输出的时候排除掉相加后正好为 0 的项即可：

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

int main() {
    int x, c;
    map<int, int, greater<int>> ans;
    for (int i = 0; i < 2; i++) {  // 有两组数据
        cin >> x >> c;
        while (x | c) {  // 不全为 0 则继续读
            ans[x] += c;
            cin >> x >> c;
        }
    }
    for (auto item : ans) {
        if (item.second) {  // 如果相加后为 0 则不输出
            cout << item.first << " " << item.second << endl;
        }
    }
    return 0;
}

数字统计

  直接用 map 计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main() {
    string str; cin >> str;
    map<char, int> cnt;
    for (char ch : str) {
        cnt[ch]++;
    }
    for (auto item : cnt) {
        cout << item.first << ":" << item.second << endl;
    }
    return 0;
}

A 除以 B

  不会吧不会还有人不知道 Python 的 int 没有上限吧（

1
2
a, b = map(int, input().split())
print(a // b, a % b)

公交系统

  假设原来车上有 xx 个人，在某站有 pp 个人上车，车厢容量为 ww；不难推出：

x∈[max⁡(0,−p),min(w,w−p)]x \in [\max(0, -p), min(w, w-p)]

  按此规则，将上车的人数序列从左到右依次累加，每次将加和 sum 作为上面的 p 值更新上下限：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {  //: T3-15
    int n, w; cin >> n >> w;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int sum = 0, L = 0, R = w;
    for (int x : arr) {
        sum += x;
        L = max(L, max(0, -sum));
        R = min(R, min(w, w-sum));
    }
    cout << max(R-L+1, 0) << endl;
    return 0;
}

成绩大排队

  结构体排序……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

struct Student {
    string name, id;
    int mark;
};

int main() {  //: T3-16
    int n; cin >> n;
    vector<Student> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i].name >> arr[i].id >> arr[i].mark;
    }
    sort(arr.begin(), arr.end(), [] (const Student& a, const Student& b) {
        return a.mark > b.mark;
    });
    cout << arr[0].name << " " << arr[0].id << endl;
    cout << arr[n-1].name << " " << arr[n-1].id << endl;
    return 0;
}

字符串数字置换

  用 stringstream 做缓冲，构造出目标字符串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

string num[] = {"(Zero)", "(One)", "(Two)", "(Three)", "(Four)", "(Five)", "(Six)", "(Seven)", "(Eight)", "(Nine)"};

int main() {
    string str; getline(cin, str);
    stringstream out;
    vector<int> repl(10);
    for (char ch : str) {
        if ('0' <= ch && ch <= '9') {
            out << num[ch - '0'];
            repl[ch - '0']++;
        } else {
            out << ch;
        }
    }
    cout << out.str() << endl;
    for (int i = 0; i < 10; i++) {
        cout << repl[i] << " ";
    }
    return 0;
}

写出来吧

  Python 直接怼

1
2
3
4
5
pinyin = ["ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"]

total = sum(int(ch) for ch in input())
print(' '.join(pinyin[int(i)] for i in str(total)))

到底买不买

  分别统计商家提供的和小红需要的珠子数量，依次比对即可

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 <bits/stdc++.h>
using namespace std;

int main() {  //: T3-19
    string str[2];
    map<char, int> material, target;

    cin >> str[0];  // 统计摊主提供的珠子数量
    for (char ch : str[0]) {
        material[ch] += 1;
    }
    cin >> str[1];  // 统计需要的珠子数量
    for (char ch : str[1]) {
        target[ch] += 1;
    }

    int diff = 0, flag = true;
    for (auto item : target) {
        if (item.second > material[item.first]) {
            diff += item.second - material[item.first];
            flag = false;
        }
    }
    if (flag) {
        cout << "Yes " << (str[0].size() - str[1].size()) << endl;
    } else {
        cout << "No " << diff;
    }
    return 0;
}

挖掘机技术哪家强

  依题意使用 map 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int main() {  //: T3-20
    int n; cin >> n;
    map<int, int> count;
    while (n--) {
        int id, mark;
        cin >> id >> mark;
        count[id] += mark;
    }
    int winner, score = -1;
    for (auto item : count) {
        if (item.second > score) {
            winner = item.first;
            score = item.second;
        }
    }
    cout << winner << " " << score;
    return 0;
}

Web 导航

  模拟题，直接按题意写

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 <bits/stdc++.h>
using namespace std;

int main() {  //: T3-21
    stack<string> front, back;
    string url = "http://www.game.org/";
    while (true) {  // 死循环起手
        string opt; cin >> opt;
        if (opt == "VISIT") {
            back.push(url);
            stack<string>().swap(front);  // 清空前向堆栈
            cin >> url;
        } else if (opt == "BACK") {
            if (back.empty()) {
                cout << "Ignored" << endl;
                continue;
            }
            front.push(url);
            url = back.top(), back.pop();
        } else if (opt == "FORWARD") {
            if (front.empty()) {
                cout << "Ignored" << endl;
                continue;
            }
            back.push(url);
            url = front.top(), front.pop();
        } else if (opt == "QUIT") {  // 设置退出条件
            break;
        }
        cout << url << endl;
    }
    return 0;
}

训练作业四

在霍格沃茨找零钱

1
2
3
4
5
6
7
8
9
10
11
import re

gp, sp, kp, ga, sa, ka = map(int, re.findall(r'(\d+)\.(\d+)\.(\d+) (\d+)\.(\d+)\.(\d+)', input())[0])
diff = (17*29*ga + 29*sa + ka) - (17*29*gp + 29*sp + kp)
if diff < 0:
    pre = '-'
    diff = -diff
else:
    pre = ''
print(f'{pre}{diff // (17*29)}.{diff % (17*29) // 29}.{diff % 29}')

最简单的计算机

  先建立好 5 个变量 M1、M2、R1、R2、R3，然后依题意模拟：

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
#include <bits/stdc++.h>
using namespace std;

int main() {  //: T4-2
    int M1, M2, R1, R2, R3;
    while (cin >> M1 >> M2) {
        R1 = R2 = R3 = 0;
        string cmd; cin >> cmd;
        for (char ch : cmd) {
            switch (ch) {
                case 'A': {
                    R1 = M1;
                    break;
                }
                case 'B': {
                    R2 = M2;
                    break;
                }
                case 'C': {
                    M1 = R3;
                    break;
                }
                case 'D': {
                    M2 = R3;
                    break;
                }
                case 'E': {
                    R3 = R1 + R2;
                    break;
                }
                case 'F': {
                    R3 = R1 - R2;
                    break;
                }
            }
        }
        printf("%d,%d\n", M1, M2);
    }
    return 0;
}

相同生日

  很适合用 map 的一道题，将月和日组合进一个 int 中即可自动按日期顺序排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int main() {  //: T4-3
    int n; cin >> n;
    map<int, vector<string>> record;
    while (n--) {
        string id;
        int month, date;
        cin >> id >> month >> date;
        record[(month << 8) | date].push_back(id);
    }
    for (auto item : record) {
        printf("%d %d ", item.first >> 8, item.first & 0xff);
        for (string str : item.second) {
            cout << str << " ";
        }
        cout << endl;
    }
    return 0;
}

日历问题

  为什么不用神奇的 Python 呢？（狗头）

1
2
3
4
5
6
7
8
9
10
11
12
13
import calendar
from datetime import datetime
from datetime import timedelta


start = datetime(2000, 1, 1)

delta = int(input())
while delta != -1:  #: T4-4
    future = start + timedelta(days=delta)
    print(future.date(), calendar.day_name[future.weekday()])
    delta = int(input())

小希的数表

  暂时没想到 O(n2)O(n^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
#include<bits/stdc++.h>
using namespace std;

int main() {  //: T4-6
    int n; cin >> n;

    vector<vector<int>> arr;
    for (int i = 1; i <= n; i++) {
        vector<int> line(i);
        for (int j = 0; j < i; j++) {
            cin >> line[j];
        }
        arr.push_back(line);
    }

    vector<vector<int>> from(n, vector<int>(n));
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            if (arr[i+1][j] < arr[i+1][j+1]) {  // 记录来源
                from[i][j] = 1;
            }
            arr[i][j] += max(arr[i+1][j], arr[i+1][j+1]);
        }
    }
    cout << arr[0][0] << endl;

    int index = 0;
    for (int i = 0; i < n - 1; i++) {
        int next = index + from[i][index];
        cout << (arr[i][index] - arr[i+1][next]) << " ";
        index = next;
    }
    cout << arr[n-1][index] << endl;

    return 0;
}

斯诺克台球 —— 🈚️

最少钱币数

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<bits/stdc++.h>
#define inf 1e9
using namespace std;

int main() {  //: T4-8
    int money;
    while (cin >> money, money) {
        int K; cin >> K;
        vector<int> val(K);
        for (int i = 0; i < K; i++) {
            cin >> val[i];
        }
        sort(val.begin(), val.end());
        
        /*
         * F[i] 表示凑成 i 元所需要的最少钱币数
         * F[0] = 0;
         * F[i] = min({{ F[i-val[j]] + 1 }})
         */
        vector<int> F(money + 1, inf);
        F[0] = 0;
        for (int i = 1; i <= money; i++) {
            for (int x : val) {
                if (i - x < 0) continue;
                F[i] = min(F[i], F[i - x] + 1);
            }
        }
        if (F[money] >= inf) {
            cout << "Impossible" << endl;
        } else {
            cout << F[money] << endl;
        }
    }
    return 0;
}

相等的多项式

  把 x=−1,0,1x = -1, 0, 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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;


int pi(int x, const vector<int>& arr) {
    int ans = 1;
    for (int n : arr) {
        ans *= (x + n);
    }
    return ans;
}


int sigma(int x, const vector<int>& arr) {
    int ans = 1;
    for (int n : arr) {
        ans = ans * x + n;
    }
    return ans;
}


int main() {  //: T4-9
    int n;
    while (cin >> n, n) {
        vector<int> A(n), B(n);
        for (int i = 0; i < n; i++) {
            cin >> A[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> B[i];
        }

        bool flag = true;
        for (int x = -1; x <= 1; x++) {
            if (pi(x, A) != sigma(x, B)) {
                flag = false;
                break;
            }
        }
        cout << (flag ? "Y" : "N") << endl;
    }
    return 0;
}

选美比赛

蛇行矩阵

  将输出矩阵顺时针旋转 45°，不难发现规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int maxn = 102;

int main() {  //: T4-11
    int n; cin >> n;
    int arr[maxn][maxn] = {0}, cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            arr[i][j] = ++cnt;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; i + j < n; j++) {
            cout << arr[i+j][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

疫情期间

  动态规划，F[i][j] 表示第 i+1 天进行了活动 j，前 i+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
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

int main() {  //: T4-12
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    /* F[i][j] 表示第 i+1 天进行了活动 j，前 i+1 天的最少休息天数
     * 00-休息 | 01-编程 | 10-健身 | 11-皆可
     */
    vector<vector<int>> F(n + 1, vector<int>(3, n));
    // Init
    for (int i : {1, 2}) {
        (arr[0] & i) && (F[0][i] = 0);
    }
    F[0][0] = 1;

    for (int i = 1; i < n; i++) {
        for (int j : {1, 2}) {  // 编程 | 健身
            if (arr[i] & j) {
                F[i][j] = min(F[i - 1][0], F[i - 1][j ^ 3]);
            }
        }

        // 休息 (min_element 返回迭代器)
        F[i][0] = *min_element(F[i - 1].begin(), F[i - 1].end()) + 1;
    }

    cout << *min_element(F[n - 1].begin(), F[n - 1].end()) << endl;
    return 0;
}

7，还是 7

组个最小数

字频统计

逆序数

最小钱币数

身份证校验

最长连续递增子序列

恺撒 Caesar 密码

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

int main() {  //: T4-20
    string str, _;
    while (cin >> _, _ != "ENDOFINPUT") {
        getchar();
        getline(cin, str);
        for (int i = 0; i < str.size(); i++) {
            if (str[i] < 'A' || str[i] > 'Z') {
                continue;
            }
            int ord = str[i] - 'A';
            ord = (ord + 21) % 26;
            str[i] = 'A' + ord;
        }
        cout << str << endl;
        cin >> _;
    }
    return 0;
}

回文串

训练作业五

Dijkstra？

  算法以传统 dijkstra 为基础，但在优先队列中以 pair<int, string> 代替原本的 int 形式存储当前距离最短的未探索节点。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100002;

struct Edge {
    int to, val;
};

int n, m;
vector<vector<Edge>> head(maxn);
vector<int> from(maxn);  // 记录每个点的「来源」

void dijkstra() {
    struct Node {
        int dst;
        pair<int, string> val;
        bool operator< (const Node& other) const {
            return val < other.val;
        }
    };
    priority_queue<Node> task;
    vector<pair<int, string>> dis(maxn, {0x7fffffff, ""});
    task.push({1, {0, "1"}}); dis[1] = {0, "1"};
    while (!task.empty()) {
        Node top = task.top(); task.pop();  // 取出距离最短的点
        if (top.val > dis[top.dst]) continue;
        for (Edge edg : head[top.dst]) {
            pair<int, string> nxt = {top.val.first + edg.val, top.val.second + (char)(edg.to + '0')};
            if (nxt < dis[edg.to]) {
                from[edg.to] = top.dst;  // 更新来源
                dis[edg.to] = nxt;
                task.push({edg.to, nxt});
            }
        }
    }
}

int output(int index) {
    if (from[index] == 0) {
        printf("%d ", index);
        return 0;
    }
    output(from[index]);
    printf("%d ", index);
    return 0;
}

int main() {  //: T5-1
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int src, dst, val;
        cin >> src >> dst >> val;
        head[src].push_back({dst, val});  // 无向图需要建双向边
        head[dst].push_back({src, val});
    }
    dijkstra();

    // 如果走不到则节点 n 的「来源」为 0
    from[n] ? output(n) : printf("-1");  
    return 0;
}

0-1 串

  使用前缀和数组，能将求某个区间中 0 或 1 的数量的操作优化到 O(1)O(1)，接下来暴力遍历所有区间 [L,R][L, R] 求解即可

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 <bits/stdc++.h>
using namespace std;git

int main() {  //: T5-2
    int n; cin >> n;
    vector<int> sum(n+1);  // 前缀和数组
    for (int i = 1; i <= n; i++) {
        cin >> sum[i];
        sum[i] += sum[i-1];
    }

    int max_z = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            /**
             * 「翻转」选定区间后 1 的总数
             * = 原来 1 的总数 + 翻转区间中 0 的数量 - 翻转区间中 1 的数量
             * = 总和 + (区间长 - 区间求和) - 区间求和
             */
             max_z = max(max_z, sum[n] + (j-i+1) - 2*(sum[j]-sum[i-1]));
        }
    }

    cout << max_z << endl;
    return 0;
}

良心树

  简单观察可以发现，删除一个节点时，并不会改变其父节点和所有儿子的「可删除」状态（即可删除节点的数量不会因为删除一个节点而增加或减少），那么先按照输入数据建树，建树后通过一次深度优先遍历找出所有待删除的节点，排序后输出即可 AC

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
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int id, flag;
    vector<int> child;
    bool operator< (const Node& other) const {
        return id > other.id;
    }
};

int n;
vector<Node> arr;

bool judge(int index) {
    if (!arr[index].flag) return false;
    for (int ptr : arr[index].child) {
        if (!arr[ptr].flag) {
            return false;
        }
    }
    return true;
}

int main() {  //: T5-3
    cin >> n;
    arr = vector<Node>(n+1);
    for (int i = 1; i <= n; i++) {  // 读入 & 建树
        int p, c; cin >> p >> c;
        arr[i].id = i, arr[i].flag = c;
        if (~p) arr[p].child.push_back(i);
    }

    priority_queue<Node> task;
    // 遍历整棵树判断节点是否可以删除
    for (int i = 1; i <= n; i++) {
        if (judge(i)) task.push(arr[i]);
    }

    if (task.empty()) {
        cout << "-1" << endl;
        return 0;
    }
    while (!task.empty()) {
        cout << task.top().id << " ";
        task.pop();
    }
    return 0;
}

最昂贵的旅行

  从「nn 个城市，n−1n-1 条边，没有环」可以推出该国所有城市间道路为树形结构，将编号为 00 的城市作为根，执行一次 dfs 找出最「远」的城市即可

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 <bits/stdc++.h>
using namespace std;

struct Edge {
    int to, val;
};

int n;
vector<vector<Edge>> head;
vector<bool> vst;

int dfs(int src, int cost=0) {
    vst[src] = true;
    int max_len = cost;
    for (Edge nxt : head[src]) {
        if (!vst[nxt.to]) {
            max_len = max(max_len, dfs(nxt.to, cost + nxt.val));
        }
    }
    return max_len;
}

int main() {  //: T5-4
    cin >> n;
    head = vector<vector<Edge>>(n);
    for (int i = 0; i < n-1; i++) {
        int src, dst, val;
        cin >> src >> dst >> val;
        head[src].push_back({dst, val});
        head[dst].push_back({src, val});
    }
    vst = vector<bool>(n);
    cout << dfs(0) << endl;
    return 0;
}

猫与餐厅的故事

  对于非叶子节点，统计其路径上连续有猫的节点数量，如果大于 mm 则返回 0；对于叶子节点，直接返回 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
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100002;

int n, m;
vector<int> cat(maxn);
vector<vector<int>> head(maxn);

int dfs(int now, int cnt, int par) {  // cnt: 之前 连续的有猫的节点数
    if (cnt + cat[now] > m) return 0;  // 如果连续有猫的数量大于 m 就不走了
    if (head[now].size() <= 1) return 1;
    int sum = 0;
    for (int nxt : head[now]) {
        if (nxt != par) {
            sum += dfs(nxt, cat[now] ? cnt + 1 : 0, now);
        }
    }
    return sum;
}

int main() {  //: T5-5
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> cat[i];
    }
    for (int i = 0; i < n-1; i++) {
        int src, dst;
        cin >> src >> dst;
        head[src].push_back(dst);
        head[dst].push_back(src);
    }
    cout << dfs(1, 0, 0) << endl;
    return 0;
}

旅行的期望值

  建树，递归。对于某个节点，其期望值为「其所有孩子节点的期望值取平均 + 1」，对于叶子节点，期望值为 0

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 <bits/stdc++.h>
using namespace std;

const int maxn = 100002;

int n;
vector<vector<int>> head(maxn);

double dfs(int src, int par) {
    if (head[src].size() <= 1 && src != 1) return 0;
    double sum = 0;  // 孩子节点的期望之和
    int child = 0;  // 孩子节点个数
    for (int nxt : head[src]) {
        if (nxt == par) continue;
        (sum += dfs(nxt, src));
        child += 1;
    }
    return sum / child + 1;
}

int main() {  //: T5-6
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int src, dst; cin >> src >> dst;
        head[src].push_back(dst);
        head[dst].push_back(src);
    }
    printf("%.7lf", dfs(1, 0));
    return 0;
}

有效的 BFS

  模拟 bfs 的过程，每次都试图选择输入中给出的节点，如果存在某时刻无法选择，则说明输入不是一个有效的 bfs 序（说白了就是直接模拟）

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100002;

inline int read() {
    int x; cin >> x;
    return x;
}

int n;
vector<set<int>> head(maxn);
vector<int> parent(maxn);  // 标记父节点

void dfs(int now, int par) {
    parent[now] = par;
    for (int nxt : head[now]) {
        if (nxt == par) continue;
        dfs(nxt, now);
    }
}

bool bfs() {  // 直接模拟 bfs
    queue<int> task;
    task.push(read());
    while (!task.empty()) {
        int now = task.front(); task.pop();
        for (int nxt : head[now]) {
            if (nxt == parent[now]) continue;
            int except = read();
            if (head[now].find(except) == head[now].end()) {
                return false;
            }
            task.push(except);
        }
    }
    return true;
}

int main() {  //: T5-7
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int src, dst;
        cin >> src >> dst;
        head[src].insert(dst);
        head[dst].insert(src);
    }
    dfs(1, 0);
    printf(bfs() ? "Yes" : "No");
    return 0;
}

数组跳远

  从后向前倒推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int main() {  //: T5-8
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int ans = 0;
        vector<int> sum(n);
        for (int i = n-1; i >= 0; i--) {
            sum[i] = arr[i];
            if (i + arr[i] < n) {
                sum[i] += sum[i + arr[i]];
            }
            ans = max(ans, sum[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

踩点上课

  将「不使用折跃门而能互相到达的块」称为一个连通区域，考虑以下两种情况：

  • 起点和终点在不同连通块内

  1. 对起点和终点所在的连通块分别做 BFS，找出「路径长 + 折跃代价」最小的折跃门

  2. 将上述两次 BFS 的结果相加即为答案，如果没有这样的折跃门，输出 -1

  • 起点和终点在同一连通块内

  1. 与在不同连通块时相同

  2. 计算从起点直接走到终点的代价（即不使用折跃门）

  3. 在第 1 步和第 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define inf (1LL << 60)
using namespace std;
typedef long long LL;

const int ways[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int n, m, w;
vector<vector<int>> gmap;
vector<vector<LL>> dst;
LL direct = inf;

void init() {
    scanf("%d %d %d", &n, &m, &w);
    gmap = vector<vector<int>> (n + 2, vector<int>(m + 2, -1));
    dst = vector<vector<LL>>(n + 2, vector<LL>(m + 2, inf));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &gmap[i][j]);
        }
    }
}

LL bfs(int x0, int y0) {
    struct pos {
        int x, y;;
    };
    LL min_cost = inf;
    queue<pos> task;
    task.push({x0, y0}); dst[x0][y0] = 0;
    while (!task.empty()) {
        auto now = task.front(); task.pop();
        int x = now.x, y = now.y;
        if (gmap[x][y] && gmap[x][y] + dst[x][y] < min_cost) {
            min_cost = gmap[x][y] + dst[x][y];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + ways[i][0], ny = y + ways[i][1];
            if (~gmap[nx][ny] &&  dst[x][y] + w < dst[nx][ny]) {
                dst[nx][ny] = dst[x][y] + w;
                task.push({nx, ny});
            }
        }
    }
    return min_cost;
}

int main() {  //: T5-9
    init();
    LL path = 0;
    path += bfs(1, 1);
    direct = dst[n][m];
    path += bfs(n, m);
    LL ans = min(path, direct);
    if (ans >= inf) {
        printf("-1");
    } else {
        printf("%lld", ans);
    }
    return 0;
}

树的优化

  参考「最大子段和」算法，进行第一次 dfs，统计从根节点开始的每一条路径上的最大子段和，找出所有「导致瑕疵」的节点；再进行第二次 dfs，统计数中不包含「导致瑕疵」节点的最大部分，即为删除后剩下节点的数量；最后与 n 作减法输出即可

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100002;

struct Edge {
    int dst, val;
};

int n;
vector<vector<Edge>> head(maxn);
vector<int> arr(maxn);  // 顶点上的数字
vector<bool> flag(maxn);  // 标记该节点是否有瑕疵

void find_all_bad(int now, int par, int sum) {  // 找出所有有瑕疵的节点
    flag[now] = sum > arr[now];
    for (Edge nxt : head[now]) {
        if (nxt.dst == par) continue;
        find_all_bad(nxt.dst, now, max(sum + nxt.val, nxt.val));  // 参考「最大子段和」算法
    }
}

int count_not_bad(int now, int par) {  // 统计剩余没有瑕疵的节点
    if (flag[now]) return 0;
    int sum = 0;
    for (Edge nxt : head[now]) {
        if (nxt.dst == par) continue;
        sum += count_not_bad(nxt.dst, now);
    }
    return sum + 1;  // 最后加上自己
}

int main() {  //: T5-10
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i < n; i++) {
        int src = i + 1, dst, val;
        cin >> dst >> val;
        head[src].push_back({dst, val});
        head[dst].push_back({src, val});
    }
    find_all_bad(1, 0, 0);
    cout << (n - count_not_bad(1, 0)) << endl;
    return 0;
}