CF292C Beautiful IP Addresses 题解

news/2025/2/23 19:40:59

题目介绍

这道题我们读完题后看到题目给的条件:

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,方便我们后面进行分割。

我们想一想,我们已经求出了原数字串,已经规定了一共三个点。

那么我们为什么不可以切割出四个数字串,然后用三个点连接起来呢?

思路就是这样,模拟即可。


http://www.niftyadmin.cn/n/5860106.html

相关文章

如何有效区分网络安全威胁?

常见的网络安全威胁有很多,其中包括窃听、重传、伪造、篡改、非授权访问、拒绝服务攻击等。而这些威胁又被分为很多种类型,那么网络安全中威胁如何区分?以下是具体内容介绍。 1、从威胁的来源进行区分 内部威胁:80%的计算机犯罪都和系统安全…

Redis Windows 设置密码

安装目录下找到redis.windows-service.conf 搜索requirepass ,设置为requirepass 123456 重启服务 测试

selenium webdriver/chrome driver集合整理130/131/132/133/134/135

版本 download link120120下載121 121下載122 122下載 123123下載124124下載125125下載126 126系列版本下载: 126.0.6478.63下载 126.0.6478.61下载 126.0.6478.55下载 126.0.6478.126下载 126.0.6…

HTML/CSS中并集选择器

1.作用:选中多个选择器对应的元素,又称:分组选择器 所谓并集就是或者的含义. 2.语法:选择器1,选择器2,选择器3,......选择器n 多个选择器通过,连接,此处,的含义就是:或. .rich,.beauty{color: blue;} 3.注意事项 1.并集选择器,我们一般竖着写 2.任何形式的选择器,都可以作为并…

学习数据结构(10)栈和队列下+二叉树(堆)上

1.关于栈和队列的算法题 (1)用队列实现栈 解法一:(参考代码) 题目要求实现六个函数,分别是栈初始化,入栈,移除并返回栈顶元素,返回栈顶元素,判空&#xff0…

SpringBoot速成(12)文章分类P15-P19

1.新增文章分类 1.Postman登录不上,可以从头registe->login一个新的成员:注意,跳转多个url时,post/get/patch记得修改成controller类中对应方法上写的 2.postman运行成功: 但表中不更新:细节有问题: c是…

避坑:过早的文件结束符(EOF):解决“git clone龙蜥OS源码失败”的失败过程

避坑:过早的文件结束符(EOF):解决“git clone龙蜥OS源码失败”的失败过程 安装Anolis OS 8.9 下载AnolisOS-8.9-x86_64-dvd.iso并安装。 使用uname -a查看内核版本为5.10.134-18.an8.x86_64。 [rootlocalhost cloud-kernel]# c…

【综合实验】

1、拓扑图 2、配置 1、ip配置 2、地址库导入 3、链路接口 4、真实DNS 5、虚拟DNS 6、DNS策略及透明代理 7、安全策略 8、NAT策略 9、PC配置 10、IP-Link安全策略