A.
http://codeforces.com/problemset/problem/510/A
签到题，画图形：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
int n,m;
void draw1()
{
for(int i=1;i<=m;i++)
cout<<"#";
cout<<endl;
}
void draw2()
{
for(int i=1;i<=m-1;i++)
cout<<".";
cout<<"#"<<endl;
}
void draw3()
{
cout<<"#";
for(int i=1;i<=m-1;i++)
cout<<".";
cout<<endl;
}
int main()
{
while(rd2(n,m)!=EOF)
{
for(int i=1;i<=n/2+1;i++)
{
draw1();
if(i==n/2+1)
break;
if(i&1)
draw2();
else
draw3();
}
}
return 0;
}http://codeforces.com/problemset/problem/510/B
给定由26个大写字母组成的n*m的矩阵，问能不能找到环（相邻的相同字母连起来看能否找到一个环，相同字母的个数>=4，环最小是一个正方形）
DFS搜索，一开始想的是用DFs搜索，搜索到已经访问过的节点时，就结束，说明找到了，但存在一个问题，就是 1—>2->1这种情况，那无论如何都可以找到已经访问的节点，但这种情况个数只有2，不符合题意为。后来用step[x][y]表示第一次到达某点走的步数（第一个点为第一步）,那么判断当第二次再到达该点时的步数 s,判断是否s-step+1>=4，如果可以，说明有环。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,-1,1};
int n,m;
bool ok;
char mp[60][60];
bool vis[60][60];
int step[60][60];
int sx,sy;
int hash[30];
void DFS(int x,int y,int cnt)
{
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(vis[x][y]&&cnt-step[x][y]+1>=4)
{
ok=1;
break;
}
// cout<<"sss"<<nx<<" "<<ny<<" "<<cnt<<endl;
if(nx==sx&&ny==sy&&cnt>=4)
{
ok=1;
break;
}
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&mp[nx][ny]==mp[x][y])
{
vis[nx][ny]=1;
step[nx][ny]=step[x][y]+1;
DFS(nx,ny,cnt+1);
if(ok)
return;
step[nx][ny]=step[x][y]-1;
vis[nx][ny]=0;
}
}
}
int main()
{
while(rd2(n,m)!=EOF)
{
ok=0;
memset(hash,0,sizeof(hash));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
hash[mp[i][j]-'A']++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(hash[mp[i][j]-'A']>=4)
{
// bfs(i,j);
sx=i,sy=j;
memset(vis,0,sizeof(vis));
step[sx][sy]=1;
vis[sx][sy]=1;
DFS(i,j,1);
}
if(ok)
break;
}
if(ok)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
using namespace std;
int n,m;
char mp[52][52];
bool vis[55][55];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
bool ok;
void DFS(int x,int y,int prex,int prey)
{
vis[x][y]=1;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx==prex&&ny==prey)//不能回走，向右走一步，不能在向左走一步
continue;
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]==mp[x][y])
{
if(vis[nx][ny])
{
ok=1;
return;
}
DFS(nx,ny,x,y);
}
}
}
int main()
{
while(cin>>n>>m)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
memset(vis,0,sizeof(vis));
ok=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!vis[i][j])
DFS(i,j,0,0);
if(ok)
{
cout<<"Yes"<<endl;
return 0;
}
}
cout<<"No"<<endl;
}
return 0;
}http://codeforces.com/problemset/problem/510/C
一般的字典序是a,b,c,d,e,f.......z，给定n个字符串，判断是否能修改字典序的顺序来使得这n个字符串是按字典序排列的.如果可以，那么输出修改以后的字典序（26个字母），否则输出Impossible。
不好理解，拿样例说明.
3个字符串
rivest
shamir
adleman
很明显，这三个字符串不是按字典序排列的，因为a在字典序中排在r和s的前面，那么我们就修改a的优先级，把其放在s的后面，那么新的26个小写字母的字典序就变为了
bcdefghijklmnopqrsatuvwxzy，正好是我们所要输出的.
输出impossible的情况：
1.后面的一个字符串是前面的前缀.
比如 abb 和 a ,这样 Impossible。
2.所要改变的字母字典序有环。
比如 d c a d ,那么要修改为 d的字典序在c前面,d->c , c->a ,a->d ，成环，不可以。
所以可以用拓扑排序来做。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=30;
int mp[maxn][maxn];//存图
int indegree[maxn];//保存每个点的入读
string str[103];
int n;
bool flag;//判断是否存在环,1表示无环，0表示有环
bool ok;
string ans;
void topo()
{
ans="";
memset(indegree,0,sizeof(indegree));
memset(mp,0,sizeof(mp));
flag=1;
for(int i=1;i<=n;i++)
cin>>str[i];
char a,b;
for(int i=2;i<=n;i++)
{
int len1=str[i-1].length();
int len2=str[i].length();
for(int k=0;k<len1&&k<len2;k++)
{
if(str[i-1][k]!=str[i][k])
{
a=str[i-1][k];
b=str[i][k];
break;
}
if(k<len1&&k==len2-1)
flag=0;
}
if(!flag)
return;
if(!mp[a-'a'][b-'a'])
{
indegree[b-'a']++;
mp[a-'a'][b-'a']=1;
}
}
flag=1;
int i,j;
for(i=0;i<26;i++)//找n次
{
bool is=0;
for(j=0;j<26;j++)//找入度为0的点
{
if(indegree[j]==0)
{
is=1;
ans.push_back('a'+j);
indegree[j]--;
for(int k=0;k<26;k++)//与其相连的边
if(mp[j][k])
indegree[k]--;
break;
}
}
if(is==0)//该次查找找不到入度为0的点
{
flag=0;
break;
}
}
}
int main()
{
while(rd(n)!=EOF)
{
topo();
if(!flag)
cout<<"Impossible"<<endl;
else
{
cout<<ans<<endl;
}
}
return 0;
}
Codeforces Round #290 (Div. 2)
原文：http://blog.csdn.net/sr_19930829/article/details/43449917