#include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { int cnt = 0; for( int i = 1; i <= n; i++ ) { if( i % 2 ) { for( int j = 1; j <= m; j++ ) { printf("#"); } } else { if( cnt % 2 == 0 ) { for( int j = 1 ;j < m; j++ ) printf("."); printf("#"); } else { printf("#"); for( int j = 2; j <= m; j++ ) printf("."); } cnt++; } puts(""); } } return 0; }
B - Fox And Two Dots问给出的n*m的字符矩阵里面有没有大于等于2*2的由相同字符组成的小字符矩阵,由并查集判断下饥渴
#include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair <int, int> PLL; int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; const int N = 3000; char mat[55][55]; bool vis[N][N]; struct E { int u, v; }edge[N * N]; int father[N]; int find (int x) { if (father[x] == -1) { return x; } return father[x] = find (father[x]); } int main () { int n, m; while (~scanf("%d%d", &n, &m)) { memset (vis, 0, sizeof(vis)); int ret = 0; memset (father, -1, sizeof (father)); for (int i = 0; i < n; ++i) { scanf("%s", mat[i]); } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int cnt = i * m + j; for (int k = 0; k < 4; ++k) { int x = i + dir[k][0]; int y = j + dir[k][1]; if (x < 0 || x >= n || y < 0 || y >= m) { continue; } if (vis[cnt][x * m + y]) { continue; } if (mat[x][y] != mat[i][j]) { continue; } vis[cnt][x * m + y] = vis[x * m + y][cnt] = 1; edge[ret].u = cnt; edge[ret++].v = x * m + y; // printf("%d %d\n", cnt, x * m + y); } } } bool flag = false; for (int i = 0; i < ret; ++i) { int u = find (edge[i].u); int v = find (edge[i].v); if (u != v) { father[u] = v; } else { flag = true; break; } } if (flag) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }
C - Fox And Names给出n个字符串,问有没有可能有这样一种26个字母间重新排序,比如(acb....xyz,(c的字典小比b小)),使得n个字符串以字典序排下来,若有多种可能随意输出一种。
拓扑排序即可,其实就是改变26个的相对权重大小(字典序大小),使得重新“定义”过的字符串满足相对的字典序。首先在“矛盾”的字符之间建边,最简单的情况下比如有3个字符串为“aio...” ,“cio...” ,“bio...”,那么可见这里的b 和 c就是矛盾的,在重新排列的26个字母中“ acb ..”就可以满足上面的例子。接下来就是跑一遍topo,确定下矛盾的字母间的相对子断续大小即可
#include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 #define pi acos(-1.0) #define eps 1e-8 typedef long long ll; const int inf = 0x3f3f3f3f; int n; char a[105][105]; int deg[30]; int len[105]; vector <int> v[105], ans; queue <int> q; void init() { while( !q.empty() ) q.pop(); for( int i = 0; i < n; ++i ) v[i].clear(); memset( deg, 0, sizeof( deg ) ); ans.clear(); } bool judge( int x, int y ) { for( int i = 0; i < len[x] && i < len[y]; ++i ) { if( a[x][i] != a[y][i] ) { deg[ a[y][i] - 'a' ] ++; v[ a[x][i] - 'a' ].push_back( a[y][i] - 'a' ); return 1; } } if( len[x] > len[y] ) return 0; else return 1; } bool topo( ) { for( int i = 0; i < 26; i++ ) if( !deg[i] ) { ans.push_back( i ); q.push( i ); } while( !q.empty() ) { int now = q.front(); q.pop(); for( int i = 0; i < v[now].size(); ++i ) { int nxt = v[now][i]; --deg[nxt]; if( deg[nxt] == 0 ) { q.push(nxt); ans.push_back( nxt ); } } } return ans.size() == 26; } int main() { while( ~scanf( "%d", &n ) ) { init(); for( int i = 1; i <= n; i++ ) { scanf("%s", a[i]); len[i] = strlen( a[i] ); } bool OK = 1; for( int i = 1; i <= n; ++i ) { for( int j = i + 1; j <= n; ++j ) { if( !judge( i, j ) ) OK = 0; } } if( OK && topo() ) { for( int i = 0; i < 26; i++ ) printf("%c", ans[i] + 'a'); puts(""); } else puts("Impossible"); } return 0; }