题解：AT_abc382_d [ABC382D] Keep Distance

liyancen · 2024-12-02 16:56:44 · 题解

题解报告

题目翻译

可以理解为我们要输出 n 个数，其中两两差距必须大于等于 10。

解题思路

首先这道题的第一个数肯定要从1开始，这是没有问题的对吧。

然后我们又发现最大的 n 只有 12，那么我们完全可以打暴力来枚举所有的情况（注：这里要按照字典序枚举），也就是说，只要我们能够使每次所枚举的值都是有意义的就可以了。

那么怎么做呢？

这是非常简单的，我们只需要确定一个数的上下边界就可以了。

设一个数为 x，他的上一个数为 last，当前为第 k 个数，我们不难发现：

那么我们完全就可以直接 dfs 来枚举，并且使每次的值都是满足上述条件的就可以了。

注：这里不能直接存储下来，因为会爆空间，所以我们可以 dfs 两次，第一次求 cnt，第二次来枚举。

#include <bits/stdc++.h>
using namespace std;

int n,m;
int v[20]={-9};//注意一下初值的问题
long long cnt;

void dfs1(int x){
    if (x==n+1){
        cnt++;
        return;
    }
    for (int i=v[x-1]+10;i<=m-(n-x)*10;i++){
        v[x]=i;
        dfs1(x+1);
    }
    return;
}

void dfs2(int x){
    if (x==n+1){
        for (int i=1;i<=n;i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for (int i=v[x-1]+10;i<=m-(n-x)*10;i++){
        v[x]=i;
        dfs2(x+1);
    }
    return;
}

int main() {
    cin>>n>>m;
    dfs1(1);
    cout<<cnt<<endl;
    dfs2(1);
    return 0;
}