题解：P17062 [JRKSJ R10 热身赛] Captain

· · 题解

题解：P17062 [JRKSJ R10 热身赛] Captain

题目大意

将 1\sim n 不重不漏划分为 k 个集合（骰子），每个集合大小为骰子面数；同时投掷全部 k 颗骰子，各人从自己骰子等概率随机掷出一个数，要求每个人掷出的数是全局最大值的概率相等。输出任意一种划分方案，无解输出 N0。

解题思路

这题主要还是思维上的难度，尤其是样例给的非常误导人，本蒟蒻也是陷入其中许久，但跳出样例，自己找出一组解后，就豁然开朗了。

首先，容易想到 n 这个数无论放在那个骰子上，只要摇到就它就必胜，同时要使这个骰子的获胜概率为 \dfrac{1}{k}，那么自然想到给 n 配上 k-1 个摇到必败的数，也就是 1\sim k-1 了。接下来 n-1 成了剩下数中最大的数，此时计算出它摇到时获胜的概率为 \dfrac{k-1}{k}，使这个骰子的获胜概率也为 \dfrac{1}{k}，就要给他配上剩下数中最小的 k-2 个了，也就是 k\sim 2k-3，接下来是相同的操作，对于 n-i+1 所配上的数是此时最小的 k-i 个数了。最后一个骰子就是将剩下还未被选择过的数全部放上去。

在知道了整套流程之后，我们就可以判断 NO 的情况了。为了使每个骰子都至少有一面，那么总面数就是 \dfrac{k \times (k+1)}{2} 了，所以如果 n 小于了 \dfrac{k \times (k+1)}{2}，就直接输出 NO 即可，其他情况按刚才所述流程进行就解决了。

::::success

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int k,n,ans;
bool vis[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>k>>n;
    if(n<(k+1)*k/2){
        cout<<"NO\n";
        return 0;
    }
    int t=1,last=1;
    while(t<k){
        cout<<k-t+1<<' ';
        vis[n-t+1]=1;
        for(int i=0;i<k-t;i++,last++){
            cout<<last<<' ';
            vis[last]=1;
        }
        cout<<n-t+1<<' '<<'\n';
        t++;
    }
    cout<<n-k*(k+1)/2+1<<' ';
    for(int i=last;i<=n-k+1;i++) cout<<i<<' ';
    return 0;
}

::::

小结与反思

这种构造题目，题目所给出的样例经常与正解不一样，导致题目极具误导性，所以不要拘泥于样例的方案中也是一种很好的解题技巧。