Kick Start

Kick Start 2019 Round C Wiggle Walk (6pts, 12pts) 在一个R * C的矩阵里面移动，遇到已经走过的格子直接跳过。数据保证移动时不会超出给定的矩阵。 Solution: Simulation 用一个visited数组记录已经走过的格子，遇到走过的格子则直接跳过往后遍历。讲道理这个方法时间复杂度是过不了Hidden Test Set的，但是我也不知道为什么就过了。 时间复杂度：O(n^2) 空间复杂度：O(n^2) // C++ #include <iostream> #include <cmath> #include <cstdio> #include <math.h> #include <limits> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; vector<vector<bool>> visited(50001, vector<bool>(50001, false)); void Forward(char &p, int &r, int &c) { if (p == 'E') { while (visited[r][c + 1]) ++c; visited[r][++c] = true; } else if (p == 'W') { while (visited[r][c - 1]) --c; visited[r][--c] = true; } else if (p == 'N') { while (visited[r - 1][c]) --r; visited[--r][c] = true; } else if (p == 'S') { while (visited[r + 1][c]) ++r; visited[++r][c] = true; } } void solve(const int &t) { int n, R, C, r, c; string str; scanf("%d %d %d %d %d", &n, &R, &C, &r, &c); cin >> str; visited = vector<vector<bool>>(50001, vector<bool>(50001, false)); visited[r][c] = true; for (int i = 0; i < n; ++i) Forward(str[i], r, c); printf("Case #%d: %d %d\n", t, r, c); } int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; ++t) solve(t); return 0; } Circuit Board (14pts, 20pts) 在矩阵里找到每一行最大值与最小值不超过K的最大子矩阵。 ...

Kick Start 2019 Round B Building Palindromes (5pts, 12pts) 判断给定区间内的子字符串是否是回文串。 Solution: Prefix Sum 判断字符串是否是回文串只需要判断字符串里个数为奇数的字符的数量是否小于等于1，但如果每次都遍历一遍给定的区间肯定会超时，所以我们需要对给定的原始字符串进行预处理，计算出每一个位置的前缀和（从下标为0到下标为i - 1的位置的字符的总数）。这样在查询的时候就只有O(1)的时间复杂度了。 时间复杂度：O(N) 空间复杂度：O(N) // C++ #include <iostream> #include <cmath> #include <cstdio> #include <math.h> #include <limits> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; int main() { int total_test_case_number; cin >> total_test_case_number; for (int case_number = 1; case_number <= total_test_case_number; ++case_number) { int N, Q, m, n, total = 0; cin >> N >> Q; string words; cin >> words; vector<vector<int>> odds(N + 1, vector<int>(26)); for (int i = 1; i <= N; ++i) { for (int j = 0; j < 26; ++j) odds[i][j] = odds[i - 1][j]; ++odds[i][words[i - 1] - 'A']; } for (int q = 0; q < Q; ++q) { cin >> m >> n; int odd = 0; for (int j = 0; j < 26; ++j) odd += ((odds[n][j] - odds[m - 1][j]) % 2 != 0); total += odd <= 1; } printf("Case #%d: %d\n", case_number, total); } return 0; } Energy Stones (17pts, 24pts) 在所有物品消耗完之前吃掉，使得能够获得的energy最多，类似于背包问题。 ...

Kick Start 2019 Round A Training (7pts, 13pts) 一共有N个人，从中选P个人，计算这P个人中 skill rating 的最大值与其他人的 skill rating 的差值之和。 $$ \sum_{i}^{j} max(rating) - rating[i] $$ Solution: Sort + Prefix Sum 先对数组排序，然后在长度为N的有序数组中遍历长为P的所有连续子数组，计算子数组中的最大值与其他值的差值之和。 $$ \sum_{i}^{j - 1} rating[j] - rating[i] $$ 如果直接遍历长为P的子数组会浪费很多时间，可以将上面的公式简化为如下。 $$ \sum_{i}^{j - 1} rating[j] - rating[i] = rating[j] * (j - 1 - i) - \sum_{i}^{j - 1} rating[i] $$ 为了避免重复计算 $$ \sum_{i}^{j - 1} rating[i] $$，可以用一个长为N+1的数组将原始数组的前缀和保存下来，这样每次直接计算 prefix[j] - prefix[i] 就能得到 $$ \sum_{i}^{j - 1} rating[i] $$ 了，时间复杂度是O(N)。 ...