A. Fox And Snake
代码可能有点挫，但能够快速A掉就够了。
#include <cstdio> int main()
{
//freopen("in.txt", "r", stdin); int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i)
{
if(i % == || i % == ) for(int j = ; j < m; ++j) printf("#");
else if(i % == )
{
for(int j = ; j < m; ++j) printf(".");
printf("#");
}
else
{
printf("#");
for(int j = ; j < m; ++j) printf(".");
}
printf("\n");
} return ;
}
代码君
B. Fox And Two Dots (DFS)
题意：
一个n×m的矩阵，给每个格子上都染上色。问是否能找到一条长度不小于4的相同颜色的回路。
分析：
在DFS的时候我们可以记录每个格子递归时的深度，如果下一个格子曾经走过而且与当前格子深度相差大于1，说明找到回路。
代码中的小错误还真不容易发现，归根结底还是自己对DFS理解得不够深刻。
#include <cstdio> const int maxn = + ;
int n, m;
int vis[maxn][maxn];
char map[maxn][maxn];
int dx[] = {, , , -};
int dy[] = {, , -, }; bool dfs(int x, int y, int d, char color)
{
vis[x][y] = d;
for(int i = ; i < ; ++i)
{
int xx = x + dx[i];
int yy = y + dy[i];
if(xx>=&&xx<n&&yy>=&&yy<m && map[xx][yy] == color)
{
if(vis[xx][yy] && vis[x][y] - vis[xx][yy] > ) return true;
else if(!vis[xx][yy])
//return dfs(xx, yy, d+1, color);
if(dfs(xx, yy, d+, color)) return true;
}
}
return false;
} int main()
{
//freopen("in.txt", "r", stdin); scanf("%d%d", &n, &m);
for(int i = ; i < n; ++i)
scanf("%s", map[i]); for(int i = ; i < n; ++i)
for(int j = ; j < m; ++j) if(!vis[i][j])
if(dfs(i, j, , map[i][j]))
{
printf("Yes\n");
return ;
} printf("No\n"); return ;
}
代码君
C. Fox And Names (拓扑排序)
题意：
要求重排26个英文字母，使得所给出的n个名字满足从小到大的字典序。
分析：
根据字典序的比较规则，可以得到一些字母之间的小于关系。然后通过拓扑排序扩展成一个全序关系输出即可。
#include <cstdio>
#include <cstring>
#include <algorithm> const int maxn = + ;
int n, len[maxn], t, c[maxn];
char names[maxn][maxn], ans[];
bool G[][]; bool dfs(int u)
{
c[u] = -;
for(int v = ; v < ; ++v) if(G[u][v])
{
if(c[v] < ) return false;
else if(!c[v] && !dfs(v)) return false;
}
c[u] = ; ans[--t] = u + 'a';
return true;
} bool topo()
{
t = ;
memset(c, , sizeof(c));
for(int u = ; u < ; ++u) if(!c[u]) if(!dfs(u)) return false;
return true;
} int main()
{
//freopen("in.txt", "r", stdin); scanf("%d", &n);
for(int i = ; i < n; ++i) { scanf("%s", names[i]); len[i] = strlen(names[i]); }
for(int i = ; i < n; ++i)
{
int l1 = len[i];
for(int j = i+; j < n; ++j)
{
int l2 = len[j];
int p = ;
while(names[i][p] == names[j][p] && p < l1 && p < l2) p++;
if(p == l1) continue;
else if(p == l2)
{//bbba无论怎样都不会比bb字典序小
puts("Impossible");
return ;
}
else
{
char c1 = names[i][p], c2 = names[j][p];
G[c1-'a'][c2-'a'] = true;
}
}
} if(topo()) printf("%s\n", ans);
else puts("Impossible"); return ;
}
代码君
D. Fox And Jumping (GCD + DP)
题意：
有一排无限多的格子，编号从负无穷到正无穷。有n张卡片，第i个卡片的花费为ci，购买这张卡片后可以向前或者向后跳li个格子，使用次数不限。
问是否能用通过购买这些卡片跳到任意格子，如果可以最小花费是多少。
分析：
如果有某种方法能够向前或者向后走一步，则可以到达任意格子。
考虑两张卡片的情况，l1x + l2y = g，根据数论知识有正整数g的最小值是gcd(l1, l2)
把问题转化成了：用最小的花费选取若干个数使得他们的GCD = 1
第一个想法就是DP，但是数据太大，于是用map来解决这个问题。
还有就是学习一下map的新用法，貌似是C++11里的标准，确实好用。
#include <bits/stdc++.h>
using namespace std; typedef pair<int, int> pii;
const int maxn = + ;
int n, l[maxn], c[maxn];
map<int, int> d; int main()
{
//freopen("in.txt", "r", stdin); scanf("%d", &n);
for(int i = ; i < n; ++i) scanf("%d", &l[i]);
for(int i = ; i < n; ++i) scanf("%d", &c[i]);
d[] = ;
for(int i = ; i < n; ++i)
for(pii p: d)
{ //遍历整个map
int g = __gcd(p.first, l[i]);
if(!d.count(g) || d[g] > p.second + c[i]) d[g] = p.second + c[i];
} if(!d.count()) puts("-1");
else printf("%d", d[]); return ;
}
代码君