AT4828 [ABC152D] Handstand 2 题解
PosVII
2021-06-23 13:58:03
**前言**
------------
赛时想到正解，打了一个小时还错了……我的方法和其他人的不太一样，思考难度蓝题（提高+/省选-）吧。
**思路**
------------
我们把这道题看作一个递推。那么每次 $n$ 加一时，我们可以多做出 $([1,n-1],n)+(n,[1,n-1])+(n,n)$ 个选择。
因为 $(x,y)=(y,x)$ 那么我们可以化简式子得：
每次 $n$ 加一时，我们可以多做出 $2\times([1,n-1],n)+(n,n)$ 个选择。
但是，这么搜索只能得 $48$ 分，所以我们要对这个式子进行优化。
**优化**
------------
每一次的 $n$ 是一定的，那么对于 $(n,x)$ 可行的 $x$ 来说，它的首位和末位被确定了，所以对于 $x$ 而言，它要满足如下表的形式。
设 $n$ 的首位和末位为 $h$ 和 $b$，而 $n$ 和 $x$ 的长度为 $lenn$ 和 $lenx$
当 $lenx=lenn$ 且 $b<h$ 时：
$x=\overline{bm(lenm=lenx-2)h}$ ，$(n,x)=10^{lenx-2}$
当 $lenx=lenn$ 且 $b=h$ 时：
$x=\overline{bm(lenm=lenx-2,m\leq \frac{(n \mod 10^{lenn})}{10})h}$ ，$(n,x)=\frac{(n \mod 10^{lenn})}{10}$
当 $lenx<lenn$ 且 $lenx\geq 3$ 时：
$x=\overline{bm(lenm=lenx-2)h}$ ，$(n,x)=10^{lenx-2}$
当 $lenx\geq 3$ 且 $b=h$ 时：
$x=\overline{bh}$ ，$(n,x)=1$
这下所有的情况都列出来了，我们可以发现 $3 \geq lenx \geq lenn-1$ 时，$(n,x)$ 可以直接求出，那么其它的情况也可以特判得到。
当然，记得将每一次得到的 $(n,x)$ 的数量乘二，因为有 $(x,n)$，同时也要判重减一，因为有 $(n,n)$。
最后，如果 $b=0$ 时，$x$ 是不存在的！
**code**
------------
```
#include<bits/stdc++.h>
using namespace std;
long long sum=9,n,las,len;
long long l[10]={1,10,100,1000,10000,100000,1000000};
long long suml[10]={1,11,111,1111,11111,111111,1111111};
int main() {
// freopen("handstand.in","r",stdin);
// freopen("handstand2.out","w",stdout);
cin>>n;
if(n<=9) {
cout<<n;
return 0;
}
for(int i=10;i<=n;i++) {
las=0;
if(l[len]<=i) len++;
if(i/l[len-1]>i%10&&i%10!=0) {
las+=suml[len-2];
}
else if(len>=3&&i%10!=0) las+=suml[len-3];
las*=2;
if(i/l[len-1]==i%10) {
las+=((i%l[len-1])/10+1)*2+1;
}
sum+=las;
}
cout<<sum;
return 0;
}
```
**总结**
------------
此题比较简单，但是一旦错了真的要你调半天。