Three Friends

这篇具有很好参考价值的文章主要介绍了Three Friends。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[BalticOI 2014 Day1] Three Friends

题目描述

有一个字符串 S S S,对他进行操作:

  1. S S S 复制为两份,存在字符串 T T T
  2. T T T 的某一位置上插入一个字符,得到字符串 U U U

现在给定 U U U,求 S S S

输入格式

第一行一个整数 N N N 代表 U U U 的长度。
第二行 N N N 个字符代表字符串 U U U

输出格式

  • 如果不能通过上述的步骤从 S S S 推到 U U U,输出 NOT POSSIBLE
  • 如果从 U U U 得到的 S S S 不是唯一的,输出 NOT UNIQUE
  • 否则,输出一个字符串 S S S

样例 #1

样例输入 #1

7
ABXCABC

样例输出 #1

ABC

样例 #2

样例输入 #2

6
ABCDEF

样例输出 #2

NOT POSSIBLE

样例 #3

样例输入 #3

9
ABABABABA

样例输出 #3

NOT UNIQUE

提示

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(35 pts): N ≤ 2001 N \le 2001 N2001
  • Subtask 2(65 pts):无特殊限制。

对于 100 % 100\% 100% 的数据, 2 ≤ N ≤ 2 × 1 0 6 + 1 2 \le N \le 2 \times 10^6+1 2N2×106+1,保证 U U U 中只包含大写字母。

说明

翻译自 BalticOI 2014 Day1 B Three Friends。

读题

经典的hash题啊,用hash做是不错的,效率很高,那么就让笔者用string水了吧。

代码

#include<bits/stdc++.h>
#include<string>
using namespace std;
string a,b,s;
bool f1=0,f2=0;
int l=0;
int main() {
    int n;
    cin>>n>>s;
    if (!(n&1)) cout<<"NOT POSSIBLE";
    else {
    	int x=n/2;
		a = s.substr(0,x);
		b = s.substr(n-x,x);
		for (int i=x;i<=n-1 and l<x;i++)
			if (s[i]==a[l]) l++;
		if (l==x) f1=1;
		l=0;
		for (int i=0;i<=n-x-1 and l<x;i++)
			if (s[i]==b[l]) l++;
		if (l==x) f2=1;
		if (!f1 and !f2) cout<<"NOT POSSIBLE";
		else if (f1 and f2 and a!=b) cout<<"NOT UNIQUE";
		else
			if (f1) cout<<a; else cout<<b;
	}
    return 0;
}

分析

hash题就用hash做,但笔者选择string+暴力,并采用压行技术,让代码可读性提到最高了
这段代码是用于判断给定字符串是否可拆分为两个相等的部分的算法。我来解释一下代码的逻辑:

初始

通过 cin 输入一个整数 n 和一个字符串 s。

接下来的条件判断语句 if (!(n&1)) cout<<“NOT POSSIBLE”; 检查 n 是否为奇数,如果是偶数,则输出 “NOT POSSIBLE”,表示无法拆分成两个相等的部分。至于((!(n&1))的意义与原理,留给读者思考。

否则,计算出拆分位置 x,即 n/2。后面需以x为界限进行匹配即可。

使用 string::substr 函数将字符串 s 分别拆分成前半部分 a 和后半部分 b。

判断

使用 for 循环遍历字符串 s 的后半部分,比较每个字符是否与 a 中对应位置的字符相同,如果相同,则将 l ++。这里的变量 l 是一个计数器,用于记录成功匹配的字符数量。

如果 l == x,则表示成功匹配了 x 个字符,将 f1 设置为 true,表示前半部分 a 是可行的。

清零 l,重复以上的过程,但这次遍历的是字符串 s 的前半部分,比较每个字符是否与 b 中对应位置的字符相同。

同样,如果 l 等于 x,则表示成功匹配了 x 个字符,将 f2 设置为 true,表示后半部分 b 是可行的。

根据 f1 和 f2 的取值,输出结果。如果两者都为 false,则输出 “NOT POSSIBLE”;如果两者都为 true,且 a 不等于 b,则输出 “NOT UNIQUE”;否则根据 f1 的取值输出 a 或 b。(想一想,为什么)

end

string过hash,是种技巧吧。文章来源地址https://www.toymoban.com/news/detail-498873.html

到了这里,关于Three Friends的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • HuggingGPT Solving AI Tasks with ChatGPT and its Friends in Hugging Face

    HuggingGPT 让LLM发挥向路由器一样的作用,让LLM来选择调用那个专业的模型来执行任务。 HuggingGPT搭建LLM和专业AI模型的桥梁。 Language is a generic interface for LLMs to connect AI models Task Planning: 将复杂的任务分解。但是这里是将任务分解为一系列的structured tasks。还可以通过之前的 ch

    2024年02月15日
    浏览(46)
  • 《2023 HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face》阅读笔记

    借助大语言模型(LLMS)在语言理解生成推理等方面表现出的出色能力,考虑将其作为控制器来管理现有的各种AI模型, 把语言作为通用接口 。基于这一理念,提出了HuggingGPT框架,利用LLMS(ChatGPT)来连接机器学习社区(Hug face)中的各种AI模型,具体来说就是在接收用户请求

    2024年02月02日
    浏览(66)
  • Verilog的三种描述方式(结构化描述、数据流描述、行为级描述对电路功能的描述有三种方式:结构化描述、数据流描述、行为级描述

    Verilog的三种描述方式(结构化描述、数据流描述、行为级描述对电路功能的描述有三种方式:结构化描述、数据流描述、行为级描述。三种描述方式抽象级别不同,各有优缺点,相辅相成,需要配合使用。 目录 一、结构化描述 1、概念 2、特点 3、示例 真值表: 电路抽象:

    2024年02月04日
    浏览(67)
  • 全减器---Verilog实现(结构描述,数据流描述,行为描述,层次结构描述)

    全减器真值表—引用知乎:链接: 全减器真值表怎么理解 代码部分 原理图 代码部分 原理图 代码部分 原理图 代码部分 原理图

    2024年02月12日
    浏览(59)
  • THREE.JS使用详细(three.js创建3d物体,three.js的使用方式)

    简述:three.js封装了WebGL的底层细节,是一款运行在浏览器中的 3D 引擎,可以用它创建各种三维场景,包括了摄影机、光影、材质等各种对象,目前在Git上已经拥有90k+的star,今天用three.js来构建一个三维模型; 1、首先,在项目中需要下载threejs的相关依赖; 2、在js页面引入使

    2024年01月23日
    浏览(84)
  • 【Three.js】Three.js快速上手教程

    官网对 Three.js 的介绍非常简单:“Javascript 3D library”。 即: three.js 是 JavaScript 编写的 WebGL 第三方库。提供了非常多的3D显示功能,是一个常见的 web 3D 库。 相关概念解释:three.js webGL openGL openGL 是一个跨平台3D/2D的绘图标准, webGL 则是 openGL 在浏览器上的一个实现。 web前端

    2024年01月16日
    浏览(57)
  • three.js(四):react + three.js

    绘制多个立方体 1.搭建react+ts 项目 react+ts 的用法可参考此链接: https://react-typescript-cheatsheet.netlify.app/docs/basic/setup 2.安装three依赖 3.安装路由 react-router-v6 的用法可参考此链接:https://juejin.cn/post/7088526716049555492 4.用路由组件包裹APP。 index.tsx 5.构建项目页面 src/view/Basics.tsx src/

    2024年02月11日
    浏览(55)
  • Three.js 的组件库react-three-fiber和react-three-drei

    类似于这种字体,可以用Text或者Text3d,但是要处理一个问题,就是要保证字体一直正面视角。 这中间的处理比较的麻烦,于是可以使用react-three-drei中的Html来做这件事

    2024年01月24日
    浏览(63)
  • three.js(三):three.js的渲染结构

    概述 three.js 封装了场景、灯光、阴影、材质、纹理和三维算法,不必在直接用WebGL 开发项目,但有的时候会间接用到WebGL,比如自定义着色器。 three.js 在渲染三维场景时,需要创建很多对象,并将它们关联在一起。 下图便是一个基本的three.js 渲染结构 Renderer 渲染器 Renderer

    2024年02月11日
    浏览(43)
  • three.js(二):webpack + three.js + ts

    webpack 依旧是主流的模块打包工具; ts和three.js 是绝配,three.js本身就是用ts写的,ts可以为three 项目提前做好规则约束,使项目的开发更加顺畅。 1.创建一个目录,初始化 npm 2.调整 package.json 文件 确保安装包是 private(私有的) ,并且移除 main 入口。这可以防止意外发布你的代码

    2024年02月11日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包