A. Fox And Snake
代碼可能有點挫，但能夠快速A掉就夠了。
1 #include <cstdio> 2 3 int main() 4 { 5 //freopen("in.txt", "r", stdin); 6 7 int n, m; 8 scanf("%d%d", &n, &m); 9 for(int i = 1; i <= n; ++i) 10 { 11 if(i % 4 == 1 || i % 4 == 3) for(int j = 0; j < m; ++j) printf("#"); 12 else if(i % 4 == 2) 13 { 14 for(int j = 1; j < m; ++j) printf("."); 15 printf("#"); 16 } 17 else 18 { 19 printf("#"); 20 for(int j = 1; j < m; ++j) printf("."); 21 } 22 printf("\n"); 23 } 24 25 return 0; 26 }
?
B. Fox And Two Dots (DFS)
題意：
一個n×m的矩陣，給每個格子上都染上色。問是否能找到一條長度不小于4的相同顏色的回路。
分析：
在DFS的時候我們可以記錄每個格子遞歸時的深度，如果下一個格子曾經走過而且與當前格子深度相差大于1，說明找到回路。
代碼中的小錯誤還真不容易發現，歸根結底還是自己對DFS理解得不夠深刻。
1 #include <cstdio> 2 3 const int maxn = 50 + 5; 4 int n, m; 5 int vis[maxn][maxn]; 6 char map[maxn][maxn]; 7 int dx[] = {0, 1, 0, -1}; 8 int dy[] = {1, 0, -1, 0}; 9 10 bool dfs(int x, int y, int d, char color) 11 { 12 vis[x][y] = d; 13 for(int i = 0; i < 4; ++i) 14 { 15 int xx = x + dx[i]; 16 int yy = y + dy[i]; 17 if(xx>=0&&xx<n&&yy>=0&&yy<m && map[xx][yy] == color) 18 { 19 if(vis[xx][yy] && vis[x][y] - vis[xx][yy] > 1) return true; 20 else if(!vis[xx][yy]) 21 //return dfs(xx, yy, d+1, color); 22 if(dfs(xx, yy, d+1, color)) return true; 23 } 24 } 25 return false; 26 } 27 28 int main() 29 { 30 //freopen("in.txt", "r", stdin); 31 32 scanf("%d%d", &n, &m); 33 for(int i = 0; i < n; ++i) 34 scanf("%s", map[i]); 35 36 for(int i = 0; i < n; ++i) 37 for(int j = 0; j < m; ++j) if(!vis[i][j]) 38 if(dfs(i, j, 1, map[i][j])) 39 { 40 printf("Yes\n"); 41 return 0; 42 } 43 44 printf("No\n"); 45 46 return 0; 47 }
?
C. Fox And Names (拓撲排序)
題意：
要求重排26個英文字母，使得所給出的n個名字滿足從小到大的字典序。
分析：
根據字典序的比較規則，可以得到一些字母之間的小于關系。然后通過拓撲排序擴展成一個全序關系輸出即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 const int maxn = 100 + 10; 6 int n, len[maxn], t, c[maxn]; 7 char names[maxn][maxn], ans[30]; 8 bool G[26][26]; 9 10 bool dfs(int u) 11 { 12 c[u] = -1; 13 for(int v = 0; v < 26; ++v) if(G[u][v]) 14 { 15 if(c[v] < 0) return false; 16 else if(!c[v] && !dfs(v)) return false; 17 } 18 c[u] = 1; ans[--t] = u + 'a'; 19 return true; 20 } 21 22 bool topo() 23 { 24 t = 26; 25 memset(c, 0, sizeof(c)); 26 for(int u = 0; u < 26; ++u) if(!c[u]) if(!dfs(u)) return false; 27 return true; 28 } 29 30 int main() 31 { 32 //freopen("in.txt", "r", stdin); 33 34 scanf("%d", &n); 35 for(int i = 0; i < n; ++i) { scanf("%s", names[i]); len[i] = strlen(names[i]); } 36 for(int i = 0; i < n; ++i) 37 { 38 int l1 = len[i]; 39 for(int j = i+1; j < n; ++j) 40 { 41 int l2 = len[j]; 42 int p = 0; 43 while(names[i][p] == names[j][p] && p < l1 && p < l2) p++; 44 if(p == l1) continue; 45 else if(p == l2) 46 {//bbba無論怎樣都不會比bb字典序小 47 puts("Impossible"); 48 return 0; 49 } 50 else 51 { 52 char c1 = names[i][p], c2 = names[j][p]; 53 G[c1-'a'][c2-'a'] = true; 54 } 55 } 56 } 57 58 if(topo()) printf("%s\n", ans); 59 else puts("Impossible"); 60 61 return 0; 62 }
?
D. Fox And Jumping (GCD + DP)
題意：
有一排無限多的格子，編號從負無窮到正無窮。有n張卡片，第i個卡片的花費為ci，購買這張卡片后可以向前或者向后跳li個格子，使用次數不限。
問是否能用通過購買這些卡片跳到任意格子，如果可以最小花費是多少。
分析：
如果有某種方法能夠向前或者向后走一步，則可以到達任意格子。
考慮兩張卡片的情況，l1x + l2y = g，根據數論知識有正整數g的最小值是gcd(l1, l2)
把問題轉化成了：用最小的花費選取若干個數使得他們的GCD = 1
第一個想法就是DP，但是數據太大，于是用map來解決這個問題。
還有就是學習一下map的新用法，貌似是C++11里的標準，確實好用。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef pair<int, int> pii; 5 const int maxn = 300 + 10; 6 int n, l[maxn], c[maxn]; 7 map<int, int> d; 8 9 int main() 10 { 11 //freopen("in.txt", "r", stdin); 12 13 scanf("%d", &n); 14 for(int i = 0; i < n; ++i) scanf("%d", &l[i]); 15 for(int i = 0; i < n; ++i) scanf("%d", &c[i]); 16 d[0] = 0; 17 for(int i = 0; i < n; ++i) 18 for(pii p: d) 19 { //遍歷整個map 20 int g = __gcd(p.first, l[i]); 21 if(!d.count(g) || d[g] > p.second + c[i]) d[g] = p.second + c[i]; 22 } 23 24 if(!d.count(1)) puts("-1"); 25 else printf("%d", d[1]); 26 27 return 0; 28 }
?
