Codeforces Round #290 (Div. 2)

这次比赛做的比上次好多了,pretest过了三道,除了A题脑残CE了一次,B、C都是一次过了的。系统测试C题WA了,最后是出了2道,上了140分,又变成蓝名
了。

510A - Fox And Snake:

输出蛇形图案,简单题,一开始头文件搞错了,CE了一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
bool p=1;
for(int i=1;i<=n;++i){
if(i&1){
for(int j=0;j<m;++j)
cout<<"#";
}
else{
if(!p) cout<<"#";
for(int j=0;j<m-1;++j)
cout<<".";
if(p) cout<<"#";
p=!p;
}
cout<<endl;
}
return 0;
}

510B - Fox And Two Dots:

再给出的图案中,判断有没有环。DFS判环解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=55;
char g[maxn][maxn];
int vis[maxn][maxn];
int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int dfs(int x,int y,int px,int py,int t){
vis[x][y]=t;
for(int i=0;i<4;++i){
if(vis[x+go[i][0]][y+go[i][1]]){
if(vis[x+go[i][0]][y+go[i][1]]==t&&(x+go[i][0]!=px||y+go[i][1]!=py))//成环。
return 1;
else continue;
}
if(g[x+go[i][0]][y+go[i][1]]&&g[x+go[i][0]][y+go[i][1]]==g[x][y])
if(dfs(x+go[i][0],y+go[i][1],x,y,t)) return 1;
}
return 0;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i){
cin.get();
for(int j=1;j<=m;++j)
cin>>g[i][j];
}
int t=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
if(!vis[i][j])
if(dfs(i,j,-1,-1,++t)){
cout<<"Yes"<<endl;
return 0;
}
}
cout<<"No"<<endl;
return 0;
}

510C - Fox And Names:

输入按字典序排好的名字,输出一个字母表使排序成立。

拓扑排序的题,照着书上的代码敲的过了pretest,忽略了一种很坑的情况。当后面的串是前面的前缀时,怎么改字母表都是没有用的,只能是“Impossible”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int g[30][30];
int topo[30],c[30],t;
string s[110];
bool dfs(int u){
c[u]=-1;
for(int v=0;v<26;++v)
if(g[u][v]){
if(c[v]<0) return false;
else if(!c[v]&&!dfs(v)) return false;
}
c[u]=1;
topo[--t]=u;
return true;
}
bool toposort(){//拓扑排序。
t=26;
memset(c,0,sizeof(c));
for(int u=0;u<26;++u)
if(!c[u]) if(!dfs(u)) return false;
return true;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;++i)
cin>>s[i];
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
int p=0,ok=1;
while(s[i][p]==s[j][p]){
p++;
if(s[i].length()==p||s[j].length()==p){
if(s[i].length()>s[j].length()){//一开始忽略的情况。
cout<<"Impossible"<<endl;
return 0;
}
ok=0;
break;
}
}
if(ok) g[s[i][p]-'a'][s[j][p]-'a']=1;
}
}
if(toposort())
for(int i=0;i<26;++i)
cout<<(char)(topo[i]+'a');
else cout<<"Impossible";
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。