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

训练作业一

众数

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

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(kZ)7k+d\quad(k\in Z),那么 dd 可由开始和结束的星期数确定;由于 LLRR 差值较小,直接遍历 [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[Ld7,Rd7]k\in[\frac{L-d}{7}, \frac{R-d}{7}]

  其中 dd 的值可由比赛开始和结束的星期数计算而得,那么只需要确定在上述区间中有几个整数 kk 即可;由于除法可能产生小数数值,判断的时候需要对区间左端点向上取整,右端点向下取整,再比较左右端点的大小,记 k1=Ld7k_1=\lceil\frac{L-d}{7}\rceilk2=Rd7k_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;
}

可删除的点

  分别统计横坐标大于零和小于零的点的数量,并记为 LLRR,只要 LLRR 不全大于 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+12S = |\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_irir_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=[(B1)x mod (B1)] mod (B1)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[i1,j1],F2[i1,j],F2[i,j1])+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[i1,j1],F1[i1,j],F1[i,j1])+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[i1]+a,min{F[ilen]}+b)F[i] = \min(F[i-1] + a, \min\{F[i-len]\} + b)

解释:

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

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

  此时发现题目的一个 bug 点,题目描述中没有说明 bab\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[i1][j]+1,F[i][j1]+1,F[i1][j1]+(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(nlogn)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_APBP_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[ij])+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,j1]+1F[i, j] = F[i, j-1] + 1

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

  从左边和上一状态转移,即: F[i,j]=max(F[i,j1],F[i1,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),然后若两个数字仅通过加减笔画的方式转换,设它们的段码分别为 AABB,则有:

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,wp)]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 个城市,n1n-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;
}