自动搬运

查看原文

来自洛谷，原作者为

	cjy1024 菜死了 :(

搬运于2025-08-24 23:16:30，当前版本为作者最后更新于2025-08-02 08:15:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12566 [UOI 2023] An Array and Several More Arrays 题解

题目链接

爆搜练习题。

题意简述

给定 $n$ 个数，分成 $k$ 组 $a_{i,j}$，为每组数分配一个权值 $d_i$，使得每组数内的数加上 $d_i$ 后这 $n$ 个数恰好构成一个 $1$ 到 $n$ 的排列。

数据范围

$n \le 10^4$，$1 \le k \le 5$，$a_{i,j} \le n$

题目分析

首先排列内 $1$ 这个元素一定要有一组数来组成，并且组成 $1$ 的数一定是数组内最小的一个数，这样这一组的 $d_i$ 也是已知的，于是可以枚举 $k$ 组数中哪一组数会构成 $1$ 这个元素。

把这个思路扩展一下，首先将每组数由小到大排序，每次枚举当前排列内最小的一个数由哪一个数组来构成，计算出 $d_i$ 后判断是否合法，用一个桶记录排列内每个元素的出现情况即可。

具体实现可以用一个 dfs 枚举，也可以用 next_permutation 函数枚举每组可能的排列。注意用 dfs 的时候所有变量都要回溯。

时间复杂度 $O(nk!)$，根据实现方法的不同可能有 $O(nk^k)$ 的上界，但是跑不满就是了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int> a[10];
int vis[7],ans[7];
int cnt[50005];
bool dfs(int now,int minn){
	if(now > k){
		return true;
	}
	for(int i = 1;i<=k;i++){
		if(!vis[i]){
			vis[i] = 1;
			ans[i] = minn-a[i][0];
			int flag = 1,min2 = minn;
			for(int x:a[i]){
				if(cnt[x+ans[i]] || x+ans[i]>n) flag=0;
				cnt[x+ans[i]]++;
				while(cnt[min2]) min2++;
			}
			if(flag && dfs(now+1,min2)) return true;
			vis[i]=0;
			for(int x:a[i]) cnt[x+ans[i]]--;
			ans[i]=0;
		}
	}
	return false;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i = 1;i<=k;i++){
		int x;scanf("%d",&x);
		for(int j = 1;j<=x;j++){
			int y;scanf("%d",&y);
			a[i].push_back(y);
		}
		sort(a[i].begin(),a[i].end());
	}
	int res = dfs(1,1);
	if(res){
		printf("Yes\n");
		for(int i = 1;i<=k;i++) printf("%d ",ans[i]);
	}else printf("No");
	return 0;
}