首页 > 代码库 > CodeForces Round #290 Div.2
CodeForces Round #290 Div.2
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 else18 {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 else51 {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 }
CodeForces Round #290 Div.2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。