题目描述
Cuber QQ 和 Cuber CC 在无聊时喜欢通过写数字来检验他们两的默契程度。
假设 Cuber QQ 写的数是 $X$，Cuber CC 写的数是Y。
当 $X$ 的最高位等于 $Y$ 的个位，且 $Y$ 的最高位等于 $X$ 的个位时，我们称 $(X,Y)$ 是一对“默契数”（这里顺序没有关系，即对于不同的 $X$ 和 $Y$ ，$(X,Y)$ 和 $(Y,X)$ 是不同的）。
现在他们两想知道，对于所有的 $1\le X,Y\le N$ ，有多少对默契数 $(X，Y)$ 呢？
输入格式
一行一个正整数 $N$ 。
输出格式
一行一个整数表示答案。
样例
输入
11输出
12解释
合法的 $12$ 对默契数为：$(1,1),(1,11),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(11,1),(11,11)$ 。
数据范围
对于40%的数据，满足 $N\le 10$
对于70%的数据，满足 $N\le 2000$
对于100%的数据，满足 $N\le 200000$
枚举 \(X\)，那么我们现在需要知道有多少个数的最高位为 \(X\) 的最低位，最低位为 \(X\) 的最高位。跑个数位 dp 。
#include<bits/stdc++.h>
using namespace std;
const int pw[]={1,10,100,1000,10000,100000};
int n,x,y,dp[6][2][6];
long long ans;
int dfs(int t,int k,int z)
{
if(!~t)
return 1;
if(~dp[t][k][z])
return dp[t][k][z];
int p=1,q=9;
if(t==z)
p=q=y;
else if(t>z)
p=q=0;
else if(!t)
p=q=x;
else
p=0;
if(!k)
q=min(q,n/pw[t]%10);
// printf("%d %d %d %d %d\n",t,k,z,p,q);
int ret=0;
for(int i=p;i<=q;i++)
ret+=dfs(t-1,k|(i<n/pw[t]%10),z);
// printf("%d %d %d %d\n",t,k,z,ret);
return dp[t][k][z]=ret;
}
int main()
{
scanf("%d",&n);
for(int i=1,t;i<=n;i++)
{
memset(dp,-1,sizeof(dp));
t=i;
while(t)
x=t%10,t/=10;
y=i%10;
if(x==y)
++ans;
// printf("%d %d\n",x,y);
if(x&&y)
for(int j=1;j<=5;j++)
ans+=dfs(5,0,j);
// printf("%lld\n",ans);
}
printf("%lld",ans);
}