由一道cf1400
的题引入Problem - C - Codeforces
题目大意是:
给你一个字符串,让你找出一个满足条件的字典序最小的映射字符串
条件:把原字符串s按一定顺序排列成一个圆圈,之后,每个字母在s被按顺时针顺序排列的字符串t替换,由此便获得了t
For example
input
5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy
output
b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz
每一个映射来的字母与原字母有一条单向边,你要确保将所有单向边连接后仅有一条链或一个环,并且不能存在自环和双向边。
key code
int n,m,k;
int a[26],b[26];
string s;
bool check(int z){
int x=a[z],cnt=1;
while(x!=z&&cnt<26&&x!=-1)x=a[x],cnt++;
if(x==-1||cnt==26)return true;
return false;
}
void solve(){
//try it again.
string t;
cin>>n;
cin>>s;t=s;
mem1(a);mem1(b);
up(0,n-1){
if(a[s[o]-'a']!=-1)t[o]=a[s[o]-'a']+'a';
else{
fup(j,0,25){
if(b[j]!=-1||j==s[o]-'a')continue;
a[s[o]-'a']=j;b[j]=s[o]-'a';
if(check(s[o]-'a')){
t[o]=j+'a';
break;
}
else{
a[s[o]-'a']=-1;
b[j]=-1;
}
}
}
}
puts(t);
}
看OI wiki的时候把这道题补了
题意是从左上角开始移动,遇到每一个#就可以改变一次方向,问最少需要多少次改变才能到达右下角,如果不能到达右下角就输出-1
key code
const int N=1010;
int n,m,k,a[N],b[N],p[N];
char now[N][N];
int dist[N][N][4];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
deque<int>q;
void add_front(int x,int y,int dir,int d){
if(dist[x][y][dir]>d){
dist[x][y][dir]=d;
q.pf(x);
q.pf(y);
q.pf(dir);
}
}
void add_back(int x,int y,int dir,int d){
if(dist[x][y][dir]>d){
dist[x][y][dir]=d;
q.pb(dir);
q.pb(y);
q.pb(x);
}
}
void solve(){
//try it again.
cin>>n>>m;
up(0,n-1)cin>>now[o];
fup(i,0,n-1)
fup(j,0,m-1)
fup(k,0,3)
dist[i][j][k]=INF;
add_front(n-1,m-1,3,0);
while(!q.empty()){
int x=q[2];
int y=q[1];
int dir=q[0];
q.pof();
q.pof();
q.pof();
int d=dist[x][y][dir];
int nx=dx[dir]+x;
int ny=dy[dir]+y;
if(nx>=0&&nx<n&&ny>=0&&ny<m)add_front(nx,ny,dir,d);
if(now[x][y]=='#'){
for(int i=0;i<4;i++){
if(i!=dir)add_back(x,y,i,d+1);
}
}
}
if(dist[0][0][3]==INF){puts(-1);return;}
puts(dist[0][0][3]);return;
}
解释一下,这个是双端搜的,用了双端队列
把不改变方向的周围的点存入,再把改变方向的点存入
最后看看终点有没有被更新
原文链接: https://www.cnblogs.com/liangqianxing/p/17050684.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/311761
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!