题解 CF688B 【Lovely Palindromes】

Mars_Dingdang

2020-10-05 10:10:24

Solution

数据范围看似吓人,其实找规律即可。 ## 题目大意 给你一个数 $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 ```