Codeforces Beta Round #8 E. Beads （数位dp）

迷南。 2022-06-17 12:22 148阅读 0赞

#### 题目链接： ####

#### [点击打开题目][Link 1] ####

#### 题意： ####

#### 将所有二进制串（只允许前导 0）中，同时满足字典序不小于其逆序串，取反串和逆序取反串（三种都要满足）的串提出来，按字典序排序，求第m个。 2<=n<=50，1<=m<=1016。 ####

#### 题解： ####

#### 显然满足题意的二进制串的首位必须是0。考虑一位一位地确定答案串。假设已经确定了答案串的前k位，我们假设第k\+1位是0，则要设法统计出满足条件的串的个数s。那么如果s<m，则答案串第k\+1位为1，同时m=m−s；否则答案串第k\+1位为0。于是问题转化为，统计所有长度为n的，前缀为prefix的二进制串中，满足题目要求的串的个数。这是一类与数位有关的统计问题，于是很容易想到数位dp。那么考虑dp\[i\]\[j\]\[rev\]\[inv\]表示，当前已经确定了前i位和末j位，rev表示前i位与末j位的逆序是否相等，inv表示前i位与末j位的逆序取反后是否相等。状态转移比较显然，我们枚举第i\+1位和第n−i位的取值，如果它满足prefix的限制，且新的串没有违反题目要求（可以利用rev和inv和取值判断）， 那么更新rev和inv的状态，并累加到对应的新状态上。 ####

#### 注意： ####

#### 如果n为奇数，那么dp到正中间一位的时候，这一位会同时作为前i位和末j<script type="math/tex" id="MathJax-Element-35">j</script>位的组成部分，需要特判。 ####

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int n, a[52];  
    ll k;  
    bool vis[55][55][2][2];  
    ll dp[55][55][2][2]; 
    ll ans;
    ll dfs(int l,int r,int rev,int inv)
    {
        if(l>r)return 1;
        if(vis[l][r][rev][inv]==true)return dp[l][r][rev][inv];
        vis[l][r][rev][inv] =true;
        ll &ans=dp[l][r][rev][inv];
        ans = 0;
        for(int i=0;i<2;i++)
        {  
            if(a[l] == -1 || a[l] == i)
            {  
                for(int j = 0; j < 2; j++)
                {  
                    if(a[r] == -1 || a[r] == j)
                    {  
                        if(l < r || i == j) //特判n为奇数的时候，走到最中间的一位  
                        { 
                            if(rev || i <= j)
                            {  
                                if(inv || i <= 1 - j)
                                {  
                                    ans = ans + dfs(l + 1, r - 1, rev || i < j , inv || i < 1 - j);  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }
        return ans; 
    }
    int main()
    {
        memset(a,-1,sizeof(a));
        cin>>n>>k;
        k++;
        a[0]=0;
        if(dfs(0,n-1,0,0)<k){
            return 0*puts("-1");
        }
        for(int i=1;i<n;i++)
        {
            a[i]=0;
            memset(vis,0,sizeof(vis));
            ll cur=dfs(0,n-1,0,0);
            if(cur<k)
            {
                k -= cur;
                a[i]=1;
            }
        }
        for(int i=0;i<n;i++)
        {
            cout<<a[i];
        }
        return 0;
    }

[Link 1]: http://codeforces.com/contest/8/problem/E