题解：P13956 [ICPC 2023 Nanjing R] 等价重写

\color{blue}{\texttt{[Analysis]}}

思路参考了官方题解。

赋值操作的特点是最终的结果只和最后一次赋值操作有关。

构造这么一张有向图

G

：边

i \to j

存在当且仅当

i<j

，且操作

p_{i}

和

p_{j}

同时对某个位置

t

进行了重赋值，且 $j$ 是最后一次对 $t$ 进行了赋值的操作。

满足了这三个条件，则在原来的操作顺序下，

t

位置最终一定是

j

而不是

i

。因此在合法的答案中，

j

也必须在

i

的后面，不然

t

位置的值就改变了。

G

的任意一个拓扑序均是合法的答案（除

1,2,\dots,n

外）。

当然我们不能显式的把图

G

建立，因为那样图可能很大，且不方便寻找满足条件的拓扑序。

因为只要输出一个合法方案就行，我们考虑限制一下我们的操作。不妨考虑只能交换相邻的两个操作。

定理：如果存在合法的方案，则一定存在一种方案，它只交换了相邻的两个操作。

证明：

如果不存在这样的方案，则代表原图存在所有的 $(i-1) \to i$ 的边（ $2 \leq i \leq n,i \in \mathbb{N}$ ）。

那么原图的拓扑序就只有 $1 \to 2\to 3 \to 4 \to \dots \to n$ 这一种，不存在其它的合法方案。

因此，如果存在合法方案，一定存在一种方案，只交换了相邻的两个操作。

因此只需要对相邻的两个操作进行判断即可。

\color{blue}{\text{Code}}

CPP

const int N=1e5+100;

int p[N],n,m,ans[N],lst[N];
vector<int> pos[N];

void init(int n,int m){
	for(int i=1;i<=n;i++) ans[i]=i;
	for(int i=1;i<=n;i++) pos[i].clear();
	for(int i=1;i<=m;i++) lst[i]=0;
}

int OZDY(){
	n=read();m=read();
	
	init(n,m);
	
	for(int i=1;i<=n;i++){
		p[i]=read();
		for(int j=1;j<=p[i];j++){
			int u=read();
			pos[i].push_back(u);
			lst[u]=i;
		}
		
		sort(pos[i].begin(),pos[i].end());
	}
	
	bool Flag=false;
	
	for(int i=2;i<=n;i++){
		bool flag=true;
		
		for(int u:pos[i]){
			auto tmp=lower_bound(pos[i-1].begin(),pos[i-1].end(),u);
			if (tmp!=pos[i-1].end()&&(*tmp==u)&&i==lst[u]){
				flag=false;break;
			}
		}
		
		if (flag){
			Flag=true;
			swap(ans[i],ans[i-1]);
			break;
		}
	}
	
	if (Flag){
		printf("Yes\n");
		for(int i=1;i<=n;i++)
			printf("%d%c",ans[i],(i==n?'\n':' '));
	}
	else printf("No\n");
	
	return Flag;
}

int main(){
	int T=read();
	while (T--) OZDY();
	
	return 0;
}

题解：P13956 [ICPC 2023 Nanjing R] 等价重写

文章操作

相关推荐

评论

题解：P13956 [ICPC 2023 Nanjing R] 等价重写