前言

题目链接

来一点不一样的方法。

正解：动态规划 / 打表数据暴力分析

考试半小时想出方法，最后输在了两个细节上。

写一篇题解以此纪念。

打表暴力程序

最开始打的暴力对拍，没想到最后只能交这个上去了。

思路：两层循环枚举两个数，判断是否符合要求。

Code（第一种）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ans;
bool check(int x,int y){
    int c=x%10,d=y%10;
    while(x>=10) x/=10;
    while(y>=10) y/=10;
    if(x==d&&y==c) return 1;
    else return 0;
}
int main(){
    //freopen("out1.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        if(!i%10) continue;
        for(int j=1;j<=n;j++){
            if(check(i,j)) {//printf("%d %d\n",i,j);
            ans++;} 
        }
    }
    printf("%lld",ans);
    return 0;
}

动态规划

这个方法很简单啊！！！

$dp_{i,j}$ 代表以 $i$ 开头以 $j$ 结尾的不超过 $n$ 的数的个数。

求一个数字首位的函数：

1
2
3
4
int one(int m){
    while(m>=10) m/=10;
    return m;
}

因为要保证 $1\le m\le 9$，所以 $dp$ 开 $10\times 10$ 即可。

最后 $9\times 9$ 的循环枚举满足题意的数量。

因为要求两个数的开头结尾互相对应，所以若一个数以 $i$ 开头，以 $j$ 结尾，那么它就有 $dp_{j,i}$ 个数对。而这样的数一共有 $dp_{i,j}$ 个，根据小学学的可能性总数需要用乘法，可以看出前面是 $i\ldots j$ 数字的数对个数为 $dp_{i,j}\times dp_{j,i}$。答案累加就可以了。

Code（第二种）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,ans,dp[10][10];
int one(int m){
    while(m>=10) m/=10;
    return m;
}
int main(){
    scanf("%d",&n);
    if(n<10){
        printf("%d",n);
        return 0;
    }
    for(int i=1;i<=n;i++) dp[one(i)][i%10]++;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            ans+=dp[i][j]*dp[j][i];
        }
    }
    printf("%d",ans);
    return 0;
}

数据分析

考试想到的方法。

方法与 @CQBZJJH 相同，但是我们俩都是考试的时候想出来的，我只是调代码比他慢啊 awa！！1 这个不要 face 的人竟然说版权是他的，IEE。

我来说说这个思路是怎么出来的。

首先第一层循环肯定是枚举 $1\sim n$，看每个数字有多少个数字对。

用第一个程序打表 $2020$，可以得到如下的输出：Link

等等好像复制不完诶，不过没关系这点够了。

然后我们先通览全篇，然后仔细观察一下 $1\sim 9$ 的数字对。

发现如下规律：

设 $x$ 为 $n$ 的首位，$k$ 为 $n$ 的位数。

分析：对于每个数 $i$，因为它的数字对的那个搭档的首尾两个数字已经定下来了，所以，中间夹着的数字就可以分析出：中间没有数字的情况，中间有一个数字的情况，中间有两个数字的情况……也就是说，如果没有 $n$ 的限制，那么这个数有的数字对的数量计算公式就是：$10^0+10^1+10^2+\ldots$。

但是这道题当中是有 $n$ 的限制的（不然这道题还有什么意义呢），所以就要分析下列三种情况讨论：

1. 若 $i \bmod 10<x$，即 $i$ 的搭档数首位小于 $x$。

非常简单的情况，这个时候，中间数字数量可以从 $0$ 取到 $k-2$，而且不管怎么取它的搭档数都不会超过 $n$ 的，因为它的首位小于 $x$，而且位数不会大于 $k$。

所以直接：

$ans←ans+10^{k-2}$

即可。

2. 若 $i \bmod 10>x$，即 $i$ 的搭档数首位大于 $x$。

也是非常简单的情况，这个时候，只要此搭档数的位数等于 $k$，就一定会大于 $n$，此点显然易证，就不需要我多哔哔了吧？所以中间掐头去尾的数字的数量可以从 $0$ 取到 $k-3$，所以可以：

$ans←ans+10^{k-3}$。

3. 若 $i \bmod 10=x$，即 $i$ 的搭档数首位与 $x$ 相等。

这个情况就比较复杂了。@CQBZJJH 奆佬用了很巧妙的方法推出了简洁的式子，但是我太蒟蒻了，不会那些花里胡哨的东西，所以就有了一个朴素的第二层循环 qwq。

我的想法就是这样的：既然你这个数无法确定位数为 $k$ 的时候到底是否大于 $n$，那么你就一点一点枚举呗！定义第二层循环 $j$ 为中间的数字（$j÷10$ 一定是一个 $k-2$ 位数，位数不够前面补 $0$），其中 $j$ 一定是 $10$ 的倍数（因为要保留最后一位，从倒数第二位开始改），每次枚举时这个 $i$ 的搭档数就是：

$x\times 10^{k-1}+j+\operatorname{one}(i)$

其中 $\operatorname{one}(i)$ 是指求 $i$ 的首位的函数（前面有）。

可以看出，只要这个数小于 $n$，那循环就可以继续下去；但是如果这个数超出了 $n$，因为 $j$ 只会越来越大，不可能后面还有满足的，直接退出循环即可。

最后说一下 $j$ 的枚举范围：$0\sim 10^{k-1}-1$（不能加到首位上去）。

一个小优化

适用于第三种方法，因为这个方法时间复杂度比较大，所以想到了这个。

试想一下：如果一个数的首位是相同的，那么它的数对的数量就相当于它末尾这个一位数的数对数量。所以，$1\sim 9$ 可以与上面分开枚举，枚举 $i$ 时把答案加在 $b_i$ 里面，最后 $ans←ans+b_i$ 即可。

（注意一定要考虑和自己组成数对即一位数的情况，所以最后 $b_i$ 需要 $+1$！！！ 考试就栽在这个细节上了。）

其实想到了这个之后，就离想到上述的动态规划简单做法不远了……考试没想到有点可惜 qaq。

Code （第三种）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k=1,x,a[10],b[10];
ll ans,t;
int one(int m){
    while(m>=10) m/=10;
    return m;
}
int buxian(int m){
    int s=0;
    for(int i=0;i<=m;i++) s+=pow(10,i);
    return s;
}
int main(){
    scanf("%d",&n);
    if(n<10){
        printf("%d",n);
        return 0;
    }
    //求n的位数
    a[1]=n;
    x=one(n);
    int u=n;
    while(u){
        u/=10;
        a[++k]=u;
    } 
    k--;
    //求数 
    for(int i=1;i<=9;i++){
        if(i<x) b[i]+=buxian(k-2);
        else if(i==x){
            b[i]+=buxian(k-3);
            int y=pow(10,k-1);
            for(int j=0;j<=y;j+=10){
                if(x*y+j+one(i)<=n) b[i]++;
                else continue;
            }
        }else b[i]+=buxian(k-3);
    }
    for(int i=1;i<=9;i++) b[i]++,ans+=b[i];
    for(int i=11;i<=n;i++){
        if(!(i%10)) continue;
        t=i%10;
        if(one(i)==t){
            ans+=b[t];
            continue;
        }
        if(t<x){
            ans+=buxian(k-2);
            continue;
        }
        if(t==x){
            ans+=buxian(k-3);
            int y=pow(10,k-1);
            for(int j=0;j<=y;j+=10){
                if(x*y+j+one(i)<=n) ans++;
                else continue;
            }
            continue;
        }
        //t>x
        ans+=buxian(k-3);
    }
    //for(int i=1;i<=9;i++) printf("%d ",b[i]);
    printf("%lld\n",ans);
    return 0;
}

时间复杂度的话……大概 $O\big(9+\frac{1}{10}\times (n-9)^2+\frac{4}{5}\times (n-9)\big)$？？反正能过，极限数据大概 $1.5$ 秒跑完。

说句闲话

1.

其实第三种方法根本不需要第二层循环，因为对于中间的那个数来说其实就是每次加一，我们还不如直接看中间那个数是多少，然后判断一下刚好卡着那个数行不行就可以了。这样直接把第二层循环给弄掉。

2.

还有更玄学厉害的，我们机房的一群大佬说可以把方法二和方法三结合起来，这样复杂度就是 $O(81)$​，直接常数级别了，详见 zqw 大佬的题解链接：点这里。

写在最后

送给大家一句来自初三教练的名言：

你思维的深度决定你代码的长度。

这道题体现得淋漓尽致啊。