CCF 有趣的数

Dear 丶 2021-06-24 14:36 505阅读 0赞

## **一、题目** \#\# ##

问题描述  
　　我们把一个数称为有趣的，当且仅当：  
　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。  
　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。  
　　3. 最高位数字不为0。  
　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。  
　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。  
输入格式  
　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。  
输出格式  
　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。  
样例输入  
4  
样例输出  
3

## **二、代码** ##

*错误版*

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    int n,total=0;
    
    bool verify(vector<int> &con, int pos, int num){
        bool flag = true;
        switch(num){
            case 0:
                for(int i = pos+1; i<n; i++){
                    if(con[i]==1)
                        flag = false;
                }
                break;
            case 1:
                for(int i = 0; i<pos; i++){
                    if(con[i]==0)
                        flag = false;
                }
                break;
            case 2:
                for(int i = pos+1; i<n; i++){
                    if(con[i]==3)
                        flag = false;
                }
                break;
            case 3:
                for(int i = 0; i<pos; i++){
                    if(con[i]==2)
                        flag = false;
                }
                break;
        }
        return flag;
    }
    
    int bicycle(vector<int> &con, int pos){
    
        while(pos<n-1 && con[pos]!=4){
            pos++;
        }
    cout<<pos<<endl;
        if(pos>n-1 && con[n-1]!=0){
            total++;
            return 0;
        }
    
        if(pos>n-1){
            return 0;
        }
    
    
        bool is = verify(con, pos, 3);
        if(is){
            con[pos] = 3;
            bicycle(con, pos+1);
        }
    
        is = verify(con, pos, 2);
        if(is){
            con[pos] = 2;
            bicycle(con, pos+1);
        }
    
        is = verify(con, pos, 1);
        if(is){
            con[pos] = 1;
            bicycle(con, pos+1);
        }
    
        is = verify(con, pos, 0);
        if(is){
            con[pos] = 0;
            bicycle(con, pos+1);
        }
    
        return 0;
    }
    
    int main(){
    
        cin>>n;
        //vector<int> org(n,4);
        //vector<int> con(n);
    
        //根据规则生成首个0,1,2,3后再递归填充空余部分。
        for(int i=0; i<n-1; i++){
            //con.assign(org.begin(),org.end());
            vector<int> con(n,4);
            con[i] = 3;
            for(int j=0; j<n-1; j++){
    
                if(con[j]!=4) continue;
                con[j] = 1;
                for(int m=i+1; m<n; m++){
    
                    if(con[m]!=4) continue;
                    con[m] = 2;
                    for(int o=j+1; o<n; o++){
    
                        if(con[o]!=4) continue;
                        con[o] = 0;
                        bicycle(con, 4);
                        con[o] = 4;
    
                    }
                    con[m] = 4;
                }
                con[j] = 4;
            }
            con[i] = 4;
        }
    
        cout<<total%1000000007;
        return 0;
    }

*100分版*  
原理：动态规划  
假设我们从高位一直到低位对每个位进行赋值，那么我们会发现根据赋值情况，我们可以根据已经使用的数字（0，1，2，3）将数据分为6种状态：  
1、首先我们从最高位开始，由于0，2分别需在1，3前面而0又不能放置在最高位，最高位只能是2，因此我们得到第一种状态，即前n-1位都是为**2**的情况。  
2、现在我们再放置一个数，目前有0，1，3没用，由于0必须在1前面，所以我们在放置1是必须先放置0。此时我们可以放置0或者3，基于此，我们得到两种状态，一种是前n-1为只有**2、0**；另一种前n-1位只有**2、3**。  
3、现在我们再放置一个数，对于已经放置2和0的状态，我们可以放置1或3，则又得到两种状态，分别是**2、0、1**和**2、0、3**；对于已经放置2和3的状态，我们只能放置0（0必须优先放于1前面）。得到状态**2、3、0（此状态和2、0、3相同）**  
4、最后一种所有0，1，2，3都被使用**0、1、2、3**  
我们最后的结果就是n位的最后一种状态：**0、1、2、3**  
总状态如下：  
　　0－－用了2，剩0，1，3  
　　1－－用了0，2，剩1，3  
　　2－－用了2，3，剩0，1  
　　3－－用了0，1，2，剩3  
　　4－－用了0，2，3，剩1  
　　5－－全部用了  
我们知道后面的状态一般是由前面状态转化而来。比如：  
第５种状态全不用了可以由第５中状态自身维持或第３种状态或第４种状态转化而来，转化如下：假设从n-1到n位  
第５中状态自身维持：可以在n位放置1或3（维持自身状态不变只能放置1或3，因为前面已经有1，3所以再放0，2就会违反规则）  
第３种状态：可以在n位放置3  
第４种状态：可以在n位放置1  
得到如下公式：  
states\[i\]\[5\] = (states\[j\]\[3\] + states\[j\]\[4\] + states\[j\]\[5\] \* 2) % mod;  
同理与其他。

#include <iostream>
    #include <vector>
    
    using namespace std;
    
     int main(){
         long long mod = 1000000007;
         int n;
         cin>>n;
         vector<vector<long long> > states(n+1,vector<long long>(6));
         for(int i=0; i<6; i++)
             states[0][i]=0;
         for(int i=1;i<=n;i++)
         {
            int j = i-1;
            states[i][0] = 1;
            states[i][1] = (states[j][0] + states[j][1] * 2) % mod;
            states[i][2] = (states[j][0] + states[j][2]) % mod;
            states[i][3] = (states[j][1] + states[j][3] * 2) % mod;
            states[i][4] = (states[j][1] + states[j][2] + states[j][4] * 2) % mod;
            states[i][5] = (states[j][3] + states[j][4] + states[j][5] * 2) % mod;
         }
         cout<<states[n][5]<<endl;
         return 0;
     }