Handstand 2

· · 题解

这是一道我们考试的题（我们的教练太勤快，居然在洛谷茫茫题海中找到了这道藏在角落中的题）。当时我用 O(n^2) 的算法枚举 (A,B) 直接爆掉，所以告诉我们：时间很珍贵。

来，废话不多说，下面步入正题。

第一种方法
首先，题目要求的数字对的两个数字，我们只需要知道它们的首尾就行了。

因此，我们可以把 [1,n] 扫一遍，用一个二维桶 f[i][j] 存储首位为 i，尾位为 &j& 的数量。

最后，我们就可以计算答案，就是二维桶里所有数字的平方和（因为数对没有位置限制，所以这里是平方）。

时间复杂度 O(n)，空间复杂度 O(1)

这里代码就不用展示了，因为代码量少，思路清晰简单。

第二种方法
这里如果听懂了上一种方法的可以跳过这种方法，不需要掌握，了解即可，因为一般这样的代码长，思维量大，出错率高，不建议在正式比赛采用。

在了解以下内容时，确保你已经看过@cqbzljt 的第三种方法。

各位读者可能已经知道，她的方法在考虑 i 的搭档数首位与 x 相等 时，复杂度比较高且技巧性强（从十位开始加的确有点冒险，数据一大就废了）。

这里，考虑这种情况的时候，答案其实可以通过数学方法算出来，因为首尾两端已确定，我们可以算出中间数字从而求出个数。

时间复杂度 O(1)，空间复杂度 O(1)

献上我丑陋的代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define int long long
#define max(a,b) a>b?a:b
int n, L, R, ans, f[15][15], len = 1, i;
int quick(int a, int b)//快速幂
{
    if (b<0)
    {
        return 0;
    }
    if (b==0)
    {
        return 1;
    }
    int mid = quick(a, b/2);
    if (b%2==0)
    {
        return mid*mid;
    }
    else
    {
        return a*mid*mid;
    }
}
signed main()
{
    cin>>n;
    if(n<10){//特判
        cout<<n;
        return 0;
    }
    L = n;
    while (L>=10)
    {
        L/=10;
        len++;
    }
    R = n%10;
    i = (n-quick(10, len-1)*L)/10+1;
    for (int l=1;l<=9;l++)
    {
        for (int r=1;r<=9;r++)
        {
            if (l<L)
            {
                f[l][r] = quick(10, len-1)/9;
            }
            else if (l>L)
            {
                f[l][r] = quick(10, len-2)/9;
            }
            else
            {
                if (r>R)//两种情况
                {
                    f[l][r] = i-1+quick(10, len-2)/9;
                }
                else
                {
                    f[l][r] = i+quick(10, len-2)/9;
                }
            }
            if(l==r)
            {
                f[l][r]++;
            }
        }
    }
    for (int p=1;p<=9;p++)
    {
        for (int k=1;k<=9;k++)
        {
            ans+=f[p][k]*f[k][p];
        }
    }
    cout<<ans;
    return 0;
}