Posts

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的最大子矩阵。...

Object Detection Object detection deals with detecting instances of objects of a certain class, such as humans, animals, etc, in digital images and videos. Object detection has applications in many areas of computer vision, including image retrieval, face detection, video surveillance, and self-driving, etc. Current detection systems repurpose classifiers to perform detection. To detect an object, these systems take a classifier for that object and evaluate it at various locations and scales in a test image....

Code Jam 2019 Round 1C Robot Programming Strategy (10pts, 18pts) 已知所有人石头剪刀布的出招顺序，每一轮同时和所有人比赛，找到必胜的策略。 Solution: Eliminiating 每一轮遍历当前轮次所有人的出招，如果同时有三种情况（R, P, S）则没有必胜策略，直接输出IMPOSSIBLE；否则返回胜利或打平的策略。 对于已经打败过的对手没有必要再考虑其之后的出招，所以用一个defeated数组保存已经打败过的对手以便直接跳过。因为当前轮次有可能超过对手的出招顺序长度，所以要用i % size获取对手当前的出招。 时间复杂度：O(A ^ 2) 空间复杂度：O(A) #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; char Decide(const char &R, const char &P, const char &S) { if (R && P && S) return 'X'; if (R && P) return 'P'; if (R && S) return 'R'; if (P && S) return 'S'; if (R) return 'P'; if (P) return 'S'; return 'R'; } bool Defeate(const char &current, const char &opponent) { return (current == 'R' && opponent == 'S') || (current == 'S' && opponent == 'P') || (current == 'P' && opponent == 'R'); } void solve(const int &t) { int A; scanf("%d", &A); int i = 0; vector<string> opponent(A); vector<bool> defeated(A, false); bool R, P, S; string res; for (int a = 0; a < A; ++a) cin >> opponent[a]; while (true) { int current_opponent = 0; R = false, P = false, S = false; for (int a = 0; a < A; ++a) { if (!...

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 !...

Code Jam 2019 Round 1A Pylons (8pts, 23pts) 在m*n的网格里移动，每次移动后的位置不能与之前的位置在同一行/列/对角线上。 Solution: BackTracking 类似于八皇后问题，不过每次的限制条件只和上一个位置有关，可以用回溯解决。 时间复杂度：O(m^2 * n^2) 空间复杂度：O(m * 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 m, n; bool BackTracking(int t, int i, int j, vector<vector<bool>> &visited, vector<vector<int>> &res) { visited[i][j] = true; res[t] = {i, j}; if (t + 1 == m * n) return true; for (int x = 0; x < m; ++x) { for (int y = 0; y < n; ++y) { int r = (x + i) % m, c = (y + j) % n; if (!...