Posts

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 (!defeated[a]) { ++current_opponent; if (opponent[a][i % opponent[a].size()] == 'R') R = true; else if (opponent[a][i % opponent[a].size()] == 'P') P = true; else S = true; } } if (current_opponent == 0) break; char result = Decide(R, P, S); if (result == 'X') { res = "IMPOSSIBLE"; break; } res += result; for (int a = 0; a < A; ++a) { if (!defeated[a] && Defeate(result, opponent[a][i % opponent[a].size()])) defeated[a] = true; } ++i; } printf("Case #%d: %s\n", t, res.c_str()); } int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; ++t) solve(t); return 0; } Power Arrangers (11pts, 21pts) // TODO ...

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最多，类似于背包问题。 ...

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 (!visited[r][c] && r != i && c != j && r + c != i + j && r - c != i - j && BackTracking(t + 1, r, c, visited, res)) return true; } } visited[i][j] = false; return false; } 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) { bool rev = false; cin >> m >> n; if (m > n) { rev = true; swap(n, m); } vector<vector<bool>> visited(m, vector<bool>(n, false)); vector<vector<int>> res(m * n, vector<int>()); printf("Case #%d: ", case_number); if (BackTracking(0, 0, 0, visited, res)) { printf("POSSIBLE\n"); for (int i = 0; i < m * n; ++i) if (!rev) printf("%d %d\n", res[i][0] + 1, res[i][1] + 1); else printf("%d %d\n", res[i][1] + 1, res[i][0] + 1); } else printf("IMPOSSIBLE\n"); } return 0; } Alien Rhyme (10pts, 27pts) 找到后缀相同的一对单词，后缀的长度可以自己定义，其他单词的后缀不能与这一对相同，使得这样的单词对最多。 ...

Code Jam 2019 Qualification Round Foregone Solution (6pts, 10pts, 1pts) 将一个带有数字4的数拆分为两个不带数字4的数。 Solution: Construction 输入的数一定带有数字4，对于每一位上的数字4，我们可以将其拆分为2+2（或1+3）的两个数。输入数据最大是10的100次方，所以我们可以将其作为字符串处理。 时间复杂度：O(n) 空间复杂度：O(1) // C++ #include <iostream> #include <cmath> #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 T; cin >> T; for (int t = 1; t <= T; ++t) { string N; cin >> N; string a, b; for (auto c:N) { a += c == '4' ? '2' : c; b += c == '4' ? '2' : '0'; } while (a[0] == '0') a.erase(a.begin()); while (b[0] == '0') b.erase(b.begin()); cout << "Case #" << t << ": " << a << " " << b << endl; } } You Can Go Your Own Way (5pts, 9pts, 10pts) 在n*n的矩阵里从(0,0)走到(n-1,n-1)，只能向右或向下走。矩阵里有一条已有的路径，不能与该路径有重合。最常规的做法是DFS/BFS，时间复杂度为O(n^2)。 ...