题解 CF688B 【Lovely Palindromes】
Mars_Dingdang
2020-10-05 10:10:24
数据范围看似吓人,其实找规律即可。
## 题目大意
给你一个数 $n$,求第 $n$ 小的偶数位回文数。
## 大体思路
### 构造
首先,我们来找一找规律。给出前十个偶位回文数为 $11,22,33,44,55,66,77,88,99,1001$。很快,我们可以发现,第 $i$ 个偶位的回文数就是将 $i$ 正序输出,然后再倒序输出即可。
### 对于其正确性的证明
令 $k$ 位数 $i=\sum_{i=0}^{k-1} 10^i\times a_i$,则将其倒序反转后所得的 $k$ 位数 $i'=\sum_{i=0}^{k-1}10^k\times a_{k-i-1}$,显然满足回文数的性质。
![](https://cdn.luogu.com.cn/upload/image_hosting/oks3phca.png)
由于是偶位回文数,故不存在形如 $131,757$ 类似的中间数,因此将第 $n$ 个偶位回文数从中间“劈开”,得到两个新数 $i,i'$。按上述构造方式,$i_n=i_{n-1}+1$。若 $i_n<i_{n-1}+1$,由整数的离散性可得 $i_n\le i_{n-1}$,必然存在 $i_j=i_n(i\le j<n)$;若 $i_n>i_{n-1}+1$,则存在 $i_j=i_{n-1}+1$ 使得第 $n$ 与第 $n-1$ 个偶位回文数之间还存在另一个偶位回文数,显然不成立,舍。
![](https://cdn.luogu.com.cn/upload/image_hosting/qjr3wncv.png)
因此上述构造方法充分且必要。
## 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
cin>>s;
cout<<s;//正序输出
reverse(s.begin(),s.end());
cout<<s;//倒序输出
return 0;
}
```
### 后记
STL 使用技巧:倒叙。
这里介绍两个函数。在头文件 `cstring` 中,存在函数 `strrev()` 用于将字符串倒叙,如:
```cpp
char s[]="Mars";
cout<<s;//输出 Mars
strrev(s);
cout<<s;//输出 sraM
```
在头文件 `string` 中包含 `reverse()` 函数,用法:`reverse(begin_pos,end_pos)`,与 STL 中的 string 搭配通常用 `reverse(s.begin(),s.end())`,如:
```cpp
string s="AKIOI";
cout<<s;//输出 AKIOI
reverse(s.begin(),s.end());
cout<<s;//输出 IOIKA
```