Code Jam

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

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)。 ...