当前位置: 首页 > news >正文

E. Archaeology(纯思维)

Problem - E - Codeforces

爱丽丝买了一个刚果总理视频的订阅,正在看一部关于苏格兰卡特林湖的因子岛的考古发现的纪录片。考古学家发现了一本书,其年代和来源都不明。也许爱丽丝可以对它进行一些解释?

这本书包含一串字符 "a"、"b "和 "c"。有人指出,没有两个连续的字符是相同的。还有人猜测,这个字符串包含一个异常长的子序列,从两边看都是一样的。

帮助爱丽丝验证这一点,找到这样的子序列,它至少包含原始字符串的一半的字符,并向下取整。请注意,你不一定要把它的长度最大化。

如果一个字符串aa可以通过删除几个(可能是0个或全部)字符从bb中得到,那么这个字符串就是bb的一个子序列。

输入
输入包括一个字符串ss(2≤|s|≤1062≤|s|≤106)。字符串ss仅由字符 "a"、"b"、"c "组成。保证没有两个连续的字符是相等的。

输出
输出一个宫锁链tt,它是ss的子序列,并且|t|≥⌊|s|2⌋|t|≥⌊|s|2⌋。

如果有多个解决方案,你可以打印其中任何一个。你不必使tt的长度最大化。

如果没有解决方案,则输出一个字符串 "IMPOSSIBLE"(为清晰起见,加引号)。

例子
输入
cacbac
输出
aba
输入
abc
输出
a
输入
cbacacacbcbababacbcb
输出
cbaaacbcaaabc
注意
在第一个例子中,其他有效的答案包括 "cacac"、"caac"、"aca "和 "ccc"。
题解:

(不得不说,cf思维题出的是真的好,如果你写这种题时,一个条件没怎么用到,思路肯定是不对的)

 题目的关键:没有相邻的两个字母,字母只有三个,从这句话你能领悟到什么?(...)

首先第一点:字母只有三个,每相邻四个肯定有两个

第二点:没有相邻的两个字母,从字符串中,任意截取两段字符长度为2的子串,这两个子串一定有字符相同

接着我们就可以从两边开始找了,模拟这个过程(第二点)即可

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII; 
const int N = 1e6 + 10;
int f[N]; 
void solve()
{string s;cin >> s;int n = s.size();s = " " + s;int l = 1,r = n;while(l < r){if(r - l + 1 < 4){f[l] = 1;break;}if(s[l] == s[r]){f[l] = f[r] = 1;l ++;r --;}else if(s[l + 1] == s[r]){f[l + 1] = f[r] = 1;l += 2;r--;}else if(s[l] == s[r - 1]){f[l] = f[r - 1] = 1; l ++;r -= 2;}else if(s[l + 1] == s[r - 1]){f[l + 1] = f[r - 1] = 1;l += 2;r -= 2;}}for(int i = 1;i <= n;i++){if(f[i])cout << s[i];}
}signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve(); }
}

相关文章:

E. Archaeology(纯思维)

Problem - E - Codeforces 爱丽丝买了一个刚果总理视频的订阅&#xff0c;正在看一部关于苏格兰卡特林湖的因子岛的考古发现的纪录片。考古学家发现了一本书&#xff0c;其年代和来源都不明。也许爱丽丝可以对它进行一些解释&#xff1f; 这本书包含一串字符 "a"、&…...

FISCO BCOS(三十四)———商品溯源(智能合约+后端)

FISCO BCOS(三十四)———商品溯源(智能合约+后端) 一、智能合约函数调用流程 注:智能合约来源(官网的合约仓库中) 但是TraceabilityFactory合约有问题,我已经做了修改,可以看原版与我的,只有一个函数不同。 官网上这套合约在TraceabilityFactory这个合约上缺少getGo…...

ts体操训练

1 实现pick type MyPick<T, K extends keyof T> {[P in K]: T[P] }2 实现readonly 让interface中所有属性变为可读 type MyReadonly<T> {readonly [K in keyof T]: T[K] }3 TupleToObject 将元组类型转换为对象类型 type tupleToObject<T extends any[]&…...

int指令

格式&#xff1a; int n,n为中断类型码&#xff0c;它的功能是引发中断过程 CPU执行过程 取中断类型码n&#xff1b;标志寄存器入栈&#xff0c;IF0&#xff0c;TF0&#xff1b;CS&#xff0c;IP入栈&#xff1b;&#xff08;IP&#xff09;&#xff08;n4&#xff09;&…...

Cycling 74 Max for Mac:音乐可视化编程软件

Cycling 74 Max是一款音乐、视觉、互动艺术等领域中广泛使用的编程语言和应用软件&#xff0c;它允许用户创作和控制实时音频和视频效果、交互式应用程序和媒体艺术品等。 Max将程序设计和可视化编程相结合&#xff0c;通过简单的拖拽和连接方式&#xff0c;用户可以将各种功能…...

ROS学习第十二节——话题通信控制小乌龟

1.基操一下 首先打开小乌龟程序和键盘控制程序 rosrun turtlesim turtlesim_node rosrun turtlesim turtle_teleop_key 查看话题列表 rostopic list 打开计算图查看具体是那个话题在起作用 rqt_graph 从上图可以看到两个节点之间的话题是 /turtle1/cmd_vel 使用以下命令获…...

matlab点云的可视化-源码复制粘贴即可(一)

一、导入并可视化一个无属性的点云 clc; clear; close; % clear everything% Import a point cloud from a plain text file (run type(Lion.xyz) to see the contents of the file) pc pointCloud(Lion.xyz);% Generate a z-colored view of the point cloud pc.plot;% Set …...

反射-Class类分析

反射相关的主要类 java.lang.Class&#xff1a;代表一个类&#xff0c;Class对象表示某个类加载后在堆中的对象java.lang.reflect.Method&#xff1a;代表类的方法&#xff0c;Method对象表示某个类的方法java.lang.reflect.Field&#xff1a;代表类的成员变量&#xff0c;Fie…...

Let’s Make C++ Great Again——string与常用字符处理函数

文章目录 string使用string类的例子&#xff0c;统计一个字符串中单词的个数&#xff1a;在算法模拟题中翻转字符串&#xff1a;判断回文字符串&#xff1a;字符串查找&#xff1a;字符串替换&#xff1a; 常用字符处理函数strlen()strcpy()strcat()strcmp()toupper() 和 tolow…...

〖Python网络爬虫实战⑰〗- 网页解析利器parsel实战

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000 python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;目前专栏免费订阅&#xff0c;在转为付费专栏前订阅本专栏的&#xff0c;可以免费订阅付…...

中电金信:生成式AI热潮下,文本智能走向何方?

突破通用人工智能场景&#xff0c;生成式AI正在向全行业应用进攻。 一个脑筋急转弯&#xff0c;几个月前ChatGPT是这样回答的&#xff1a; 然而&#xff0c;仅仅几个月的迭代&#xff0c;它的回答却让人出乎意料。 看似调侃的对比背后实则是无数次模型训练的支撑。基于数据的激…...

探索Linux设备树:硬件描述与驱动程序的桥梁

目录标题 引言&#xff1a;Linux设备树简介 | Introduction: Linux Device Tree Overviewa. 设备树的背景与发展 | Background and Development of Device Treeb. 设备树的作用与意义 | The Role and Significance of Device Tree 设备树语法与结构 | Device Tree Syntax and S…...

UNION ALL用法 以及 UNION ALL和UNION的区别

部分参考自文章&#xff1a; https://blog.csdn.net/a200822146085/article/details/119545374(CC 4.0 BY-SA版权协议)CSDN「我心依依旧」 https://www.1keydata.com/cn/sql/sql-unionall.php SQL Union All SQL指令 UNION ALL用法 UNION ALL 这个指令的目的也是要将两个 SQL 语…...

Ubuntu Linux操作

引言 晚上上课发现桌子上遗留了这本书&#xff0c;水课就看了看学习下&#xff0c;以下内容直接总结知识点 磁盘内存解析 (1)硬盘有数个盘片,每个盘片两个面,每个面一个磁头。 (2)盘片被划分为多个扇形区域即扇区。 (3)同一盘片不同半径的同心圆为磁道。 (4)不同盘片相同半径…...

MongoDB常用语句(CURD)

文章目录 一、数据库操作二、集合操作三、文档操作3.1 插入文档3.2 查询文档3.3 更新文档3.4 删除文档 四、安全认证4.1 创建管理员账号4.2 创建应用数据库用户4.3 启动和连接 (校验方式) 提示&#xff1a;以下是本篇文章正文内容&#xff0c;MongoDB 系列学习将会持续更新 一…...

一篇文章让你彻底学会--节流(并且自己可以手写)

Hi,有的小伙伴们在面试的时候会被要求手写节流函数&#xff0c;很多都被难着了吧&#xff0c;宝贝&#xff0c;那你你没有理解节流函数。 今天&#xff0c;就让我带你攻克它&#xff01; 1.节流 单位时间内&#xff0c;事件触发&#xff0c;最多只执行一次事件回调。 人话:说…...

C++ 形参是类的指针 class * 通过new的方式创建对象

当你在C中使用类指针&#xff08;class *&#xff09;作为函数的形参&#xff0c;并通过 new 关键字创建对象时&#xff0c;这种用法确实会改变类对象的值。原因是你通过指针传递了对象的内存地址&#xff0c;而不是传递对象本身。这意味着在函数内部对对象的任何修改都会直接影…...

手把手教你将项目部署到服务器!

一、导入centos7虚拟机&#xff1a; 打开VMWare&#xff0c;点击“打开虚拟机”&#xff0c;选择centos7.ova之后&#xff0c;选择存储路径&#xff1a; 点击导入&#xff1a; 选择“不再显示此消息”&#xff0c;点击“重试”按钮&#xff1a; 点击“编辑虚拟机设置”&#x…...

OpenHarmony应用开发-ArkUI方舟开发框架简析

方舟开发框架&#xff08;简称ArkUI&#xff09;为OpenHarmony应用的UI开发提供了完整的基础设施&#xff0c;包括简洁的UI语法、丰富的UI功能&#xff08;组件、布局、动画以及交互事件&#xff09;&#xff0c;以及实时界面预览工具等&#xff0c;可以支持开发者进行可视化界…...

【Transformer系列(4)】Transformer模型结构超详细解读

前言 前一篇我们一起读了Transformer的论文《Attention Is All You Need》&#xff0c;不知道大家是否真的理解这个传说中的神&#xff08;反正俺是没有~&#xff09; 这两天我又看了一些视频讲解&#xff0c;感谢各位大佬的解读&#xff0c;让我通透了不少。 这篇文章就和…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...