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

cjy1024 · 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 的排列。

数据范围

题目分析

首先排列内 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;
}