lp1963 NOI2009 变换序列

如果知道这道题是一个二分图匹配，就显得非常简单了。
首先我们对原序列和变换序列各自建一个点。
然后，对于每一组约束条件\(D_{i}\)，我们向所有到\(i\)的距离为\(D_{i}\)的点连一条边。
然后先跑一遍二分图最大匹配。如果全部都能匹配上就说明有解。

但是题目要求字典序输出这组解，怎么办呢？
这么做的意思就是，对于一个尽可能小的数\(i\)，它匹配的数\(T_{i}\)也要尽可能小。
故而，搜索的时候从大往小即可。

#include<iostream>
#include<cstdio>
int n,D[10005];
int vis[10005],dep=0;
int usd[10005];

inline bool dfs(int X){
	int up=(X+D[X]-1)%n+1,dw=(X-D[X]+n-1)%n+1;
	if(up<dw){
		std::swap(up,dw);
	}
//	printf("%d %d\n",up,dw);
	if(!usd[dw]&&vis[dw]!=dep){
		vis[dw]=dep;
		usd[dw]=X;
		return 1;
	}
	if(vis[dw]!=dep){
		vis[dw]=dep;
		if(dfs(usd[dw])){
			usd[dw]=X;
			return 1;
		}
	}
	if(!usd[up]&&vis[up]!=dep){
		vis[up]=dep;
		usd[up]=X;
		return 1;
	}
	if(vis[up]!=dep){
		vis[up]=dep;
		if(dfs(usd[up])){
			usd[up]=X;
			return 1;
		}
	}
	
	return 0;
}
int Ans[10005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&D[i]);
	}
	int ans=0;
	for(int i=n;i>=1;--i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	if(ans<n){
		puts("No Answer");
	}else{
		for(int i=1;i<=n;++i){
			Ans[usd[i]]=i;
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]-1);
		}
	}
}

int main(){
	init();
	return 0;
}