[题解]2023CCPC黑龙江省赛 - Ethernet

Intro

• 来源：E.Ethernet - Codeforces
• 题意：给定 $n(1\le n\le 10)$ 个数组成的排列，其中前 $m(0\le m\le n)$ 个数(即$1$~$m$) 在排列中位置随机，对于剩余 $n-m$ 个数，设当前填充数字为$i(n-m\le i\le n)$：
  • 若第 $i$ 位未被填充，则填充数字$i$；
  • 否则， $i$ 将被随机填充到先前未被填充的位上。
• 关键词：搜索，思维(签到)

题解

下面给出两种解法：

DFS

注意到 $n=10$，显而易见这是一道DFS板子题，不需要任何剪枝技巧，复杂度$O(n!)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,yes;
vector<bool>v(11);
void dfs(int x){//x:当前处理数字if(x==n){//插满cnt++;if(!v[n]) yes++;}else if(x>m){//乱插结束if(!v[x]){v[x]=1;dfs(x+1);v[x]=0;}else{//乱插for(int i=1;i<=n;i++)if(!v[i]){v[i]=1;dfs(x+1);v[i]=0;}}}else{for(int i=1;i<=n;i++)if(!v[i]){v[i]=1;dfs(x+1);v[i]=0;}}
}
void solve(){cin>>n>>m;dfs(1);printf("%.10lf",yes/(double)cnt);
}
signed main(){// ios::sync_with_stdio(0),cin.tie(0);int t=1;while(t--) solve();return 0;
}

结论

手玩几个样例，不难发现：
若$n=m$，则答案为$\frac{1}{m}$；否则答案为$\frac{1}{m+1}$。

#include<bits/stdc++.h>
using namespace std;
int n,k;
void solve(){if(n==k) printf("%.10lf",1/(double)k);else printf("%.10lf",1/(double)(k+1));
}
signed main(){scanf("%lld %lld",&n,&k);solve();return 0;
}