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(" "); 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 "); 41 return 0; 42 } 43 44 printf("No "); 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 ", 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 }