题解：CF1767D Playoff

CashCollectFactory · 2024-11-19 22:05:03 · 题解

启发式打表题解看这里

首先，我们根据题意写一个暴力程序，用于打表。考虑到 next_permutation() 函数在此时会导致程序统计大量的重复答案，当 n 超过 4 时就无法在可以忍受时间内算出所有答案，我们采用 random_shuffle() 这个随机打乱函数，这样效率就大大提升啦！具体代码实现如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[300005]; //大于2^18即可 
set<int> st; //一个用于去重的set 
int main(){
    int n;
    string s;
    cin>>n>>s;
    int m=1<<n;
    for(int i=1;i<=m;i++) a[i]=i; //创造初始排列 
    do{
        random_shuffle(a+1,a+1+m); //随机打乱一下 
        vector<int> v,tem;
        for(int i=1;i<=m;i++) v.push_back(a[i]);
        for(int i=0;i<n;i++){
            int sz=v.size();
            for(int j=0;j<sz;j+=2){
                if(s[i]=='1') tem.push_back(max(v[j],v[j+1]));
                else tem.push_back(min(v[j],v[j+1]));
            }
            v=tem;
            tem.clear();
        }//暴力统计此时的最终能力值 
        if(st.count(v[0])==0) cout<<v[0]<<" "; //将可能的答案输出 
        st.insert(v[0]);
    }while(1);//死循环，一直找
    return 0;
}

当 n=3 时，最终打表结果：

初步发现，结果与 0 和 1 的位置无关，仅与 0 和 1 的数目有关。

当 n=4 时，最终打表结果：

首先观察到，设 s 里面 1 的个数为 cnt，则结果的第一个数永远是 2^{cnt}。

然后，我们不难发现结果具有严格的对称性，即从上到下增加的数的个数和从下到上对称位置增加的数的个数是相同的，由此可以推算出最后一个数为 2^n-2^{n-cnt}+1。

最终结果仅需输出这两个边界之间的数即可，具体实现参考下方代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s;
    cin>>n>>s;
    int cnt=0;
    for(int i=0;i<n;i++) if(s[i]=='1') cnt++;
    int l=(1<<cnt);//左边界 
    cnt=n-cnt;
    int r=(1<<n)-(1<<cnt)+1; //右边界 
    for(int i=l;i<=r;i++) cout<<i<<" ";
    return 0;
}