[ARC153A] AABCDDEFE 题解

U_star · 2023-01-20 15:14:29 · 题解

题目大意：一个九位数，如果它满足以下条件，则称它为一个美丽的数：

最高位不为 0；
亿位上的数字等于千万位上的数字；
万位上的数字等于千位上的数字；
百位上的数字等于各位上的数字。

现在给定了 N，求第 N 个美丽数。

一种可行的方法，是对这个数的亿位、百万位、十万位、万位、百位、十位进行枚举，虽然是六次方级的暴力，但是由于常数较小，时间复杂度可以通过。

#include<bits/stdc++.h>
using namespace std;
int sum=0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=9;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                for(int l=0;l<=9;l++)
                    for(int m=0;m<=9;m++)
                        for(int o=0;o<=9;o++)
                            if(++sum==n)
                            cout<<i<<i<<j<<k<<l<<l<<m<<o<<m;
    return 0;
}

~~暴力 yyds！~~

其实此题还有更快的做法。

我们观察上一份代码，发现它一共循环了 9\times 10^5 次，每次都必然产生一个美丽数，也就是说美丽数恰好共有 9\times 10^5 个。

这是一种巧合吗？并不是。我们冷静下来一思考，发现由于亿位上的数字等于千万位上的数字，所以在亿位上的数字固定的情况下，千万位的数字必然不会变化，因此我们可以抛开千万位上的数字，千位、个位数字也是同理，抛开这三个数字后，它就变成了一个六位数。

因此问题转化成了：给定了一个正整数 N，求第 N 个六位数，将其十万位、千位、百位重复输出一次。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    string s=to_string(n+99999);
    cout<<s[0]<<s[0]<<s[1]<<s[2]<<s[3]<<s[3]<<s[4]<<s[5]<<s[4];
    return 0; 
}