前言
洛谷题解，懂？（
来一点不一样的方法。
正解：动态规划 / 打表数据暴力分析
考试半小时想出方法，最后输在了两个细节上。
写一篇题解以此纪念。
打表暴力程序
最开始打的暴力对拍，没想到最后只能交这个上去了。
思路：两层循环枚举两个数，判断是否符合要求。
Code（第一种）
#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\) 的数的个数。
求一个数字首位的函数：
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（第二种）
#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 （第三种）
#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;
}
时间复杂度的话……大概 \(Θ\big(9+\frac{1}{10}\times (n-9)^2+\frac{4}{5}\times (n-9)\big)\)？？反正能过，极限数据大概 \(1.5\) 秒跑完。
写在最后
送给大家一句来自初三教练的名言：
你思维的深度决定你代码的长度。
这道题体现得淋漓尽致啊。