图论及类似

由一道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);
}

Problem - B - Codeforces

看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;
	
}

解释一下，这个是双端搜的，用了双端队列

把不改变方向的周围的点存入，再把改变方向的点存入

最后看看终点有没有被更新