poj3208 Apocalypse Someday 题解报告

谁借莪１个温暖的怀抱￠ 2021-11-02 09:40 212阅读 0赞

[题目传送门][Link 1]

**【题目大意】**

包含连续的至少三个6的数称为“beastly number”，将这些数从小到大排序，求第n个数。

**【思路分析】**

**(注：以下加粗的“数”都代表“beastly number”)**  
设f\[i\]\[3\]表示由i位数字构成的**数**的个数，f\[i\]\[j\](0≤j≤2)表示由i位数字构成的、开头已经有j个连续的6但不是**数**的个数。注意，在计算f时允许前导0存在。  
考虑第i位(最高位)是什么数字，容易得到转移方程：

$f\[i\]\[0\]=9\*(f\[i-1\]\[0\]+f\[i-1\]\[1\]+f\[i-1\]\[2\])$  
$f\[i\]\[1\]=f\[i-1\]\[0\]$  
$f\[i\]\[2\]=f\[i-1\]\[1\]$  
$f\[i\]\[3\]=f\[i-1\]\[2\]+10\*f\[i-1\]\[3\]$

经过这样的DP预处理之后，我们先通过f\[i\]\[3\]确定第n小的**数**的位数。然后按照“试填法”的思想，从左到右依次考虑每一位，同时记录当前末尾已经有几个连续的6。  
从小到大枚举当前这一位填入的数字，通过预处理出来的f数组可以直接计算出后面几位有多少种填法可以得到**数**，与n比较即可得出答案。

**【代码实现】**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<algorithm>
     3 #define rg register
     4 #define ll long long
     5 #define go(i,a,b) for(rg ll i=a;i<=b;i++)
     6 #define back(i,a,b) for(rg ll i=a;i>=b;i--)
     7 using namespace std;
     8 ll f[21][4];
     9 int T,n,m;
    10 void ready(){
    11     f[0][0]=1;
    12     go(i,0,19){
    13         go(j,0,2){
    14             f[i+1][j+1]+=f[i][j];
    15             f[i+1][0]+=f[i][j]*9;
    16         }
    17         f[i+1][3]+=f[i][3]*10;
    18     }
    19     return;
    20 }
    21 int main(){
    22     ready();
    23     scanf("%d",&T);
    24     while(T--){
    25         scanf("%d",&n);
    26         for(m=3;f[m][3]<n;m++);//计算位数m
    27         for(rg int i=m,k=0;i;i--){
    28         //试填第i位,末尾已经有k个6
    29             go(j,0,9){
         //枚举填在第i位的数j
    30                 ll mid=f[i-1][3];
    31                 //求后面的i-1位有几种填法使得整个数满足要求
    32                 if(j==6||k==3)
    33                     go(l,max(3-k-(j==6),0),2)
    34                         mid+=f[i-1][l];
    35                 if(mid<n) n-=mid;
    36                 //如果mid比n小,说明第n个满足要求的数的第i位应该比j大
    37                 else{
    38                     if(k<3){
    39                         if(j==6) k++;
    40                         else k=0;
    41                     }
    42                     printf("%lld",j);break;
    43                 }
    44             }
    45         }
    46         puts("");
    47     }
    48     return 0;
    49 }

代码戳这里

转载于:https://www.cnblogs.com/THWZF/p/10991037.html

[Link 1]: http://poj.org/problem?id=3208
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/a45db16ef2e140b791478db209e70097.png