CF292C Beautiful IP Addresses 题解
题目介绍
这道题我们读完题后看到题目给的条件：
IP 地址，且去掉分割的点以后的纯数字字符串是回文，那么就叫做美丽的 IP。
暴力方法
是不是听起来很简单，我先介绍一个大多数人都能想到的部分分做法：
枚举出所有 IP 的纯数字字符串，然后判断回文。
是回文那就考虑点的位置。
就是那么简单，但是我们来算一算最坏会运行多少次。
首先，我们要知道，IPv4 地址的每一位都是 0 0 0 ~ 255 255 255。
那么一共就是 26 6 4 266^4 2664 种，通过计算器我们得知这个大小大概是 5 × 1 0 9 5 \times 10^9 5×109。
很明显，这种算法是无法通过的，那我们就要加以优化。
优化
我们想一下：既然我们都要判断回文了，为什么我们不直接构造一个回文呢？
那你可能要问了：“你说得那么简单，那怎么构造回文？而且，就算构造了，你怎么证明你这个算法就是对的？”
如何构造回文？
我们先一起想一想我们是怎么用双指针判断回文的。
是不是像这样一个指头一个指尾，然后同时向中间走？
那我们可不可以反过来，先填充绿色箭头，再填充浅灰色、深灰色、黑色？
最后我们把构造的回文存在一个 vector 变量里面，等会去分割点不就行了么？
哦对了，对于 IP 产生的纯数字字符串长度是 8 8 8 ~ 12 12 12。我的做法会去判断奇偶，如果是奇数就先特殊地添加一位（绿色箭头），偶数则不用。
如何添加分割点？
我们在这里先写一个判断（check）来判断这个串是否是合法，判断的方法其实就只是把这个纯数字串转成数字，进行判断是否 ⩾ 0 \geqslant 0 ⩾0 以及 ⩽ 255 \leqslant 255 ⩽255，方便我们后面进行分割。
我们想一想，我们已经求出了原数字串，已经规定了一共三个点。
那么我们为什么不可以切割出四个数字串，然后用三个点连接起来呢？
思路就是这样，模拟即可。