假暴力,cf1168B. Good Triple

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1168B - Codeforces


二、解题报告

1、思路分析

一眼没思路,打个暴力试试

因为如果 s[l, r] 是一个好字符串,那么s[i, r]一定也是好字符串,其中i < l

那么我们枚举左端点l,找到最近的r,那么l的贡献就是n - r

看起来是O(n^2)的,跑了下过了,而且只跑了46ms,这明明是O(n)复杂度才能跑出来的时间

然后看样例:

这个样例其实是在暗示只要长度大于等于9那么都是好字符串,这个可以二进制枚举2 ^ 9种字符串验证一下发现都是,那么对于长度大于9的字符串,由于它含长度为9的子串,所以它也是好字符串

所以我们的暴力做法其实是O(n)的

2、复杂度

时间复杂度: O(9n)空间复杂度:O(n)

3、代码详解

#include <bits/stdc++.h>
using i64 = long long;

int main () {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::string s;
    std::cin >> s;
    i64 res = 0;
    int n = s.size();
    std::vector<int> r(n + 1, n);
    for (int i = n - 1; ~i; i -- ) {
        r[i] = r[i + 1];
        for (int j = 1; i + j * 2 < r[i]; j ++ )
            if (s[i] == s[i + j] && s[i] == s[i + 2 * j])
                r[i] = i + 2 * j;
        res += n - r[i];
    }
    std::cout << res;
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/652958.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Mongo】索引结构

结论 Mongo3.2版本开始&#xff0c;索引的结构默认是B树。 起因 面试的时候&#xff0c;面试官问为什么Mongo DB底层使用B树而不是B树&#xff1f; 面试完赶紧恶补&#xff0c;结果发现面试官好像给我埋了个坑。。。 MongoDB官方描述&#xff1a; 翻译一下就是&#xff1…

Java 类加载机制解密一探到底

类加载是 Java 程序在运行期执行之前的重要环节&#xff0c;它决定着程序的运行效率和稳定性。本文将为您深入剖析 Java 类加载机制的整个生命周期&#xff0c;揭开神秘面纱&#xff0c;让您彻底掌握这一核心知识点。 一、类的生命周期概述 类的生命周期在Java中指的是从类被加…

【全开源】CMS内容管理系统源码(ThinkPHP+FastAdmin)

基于ThinkPHPFastAdmin的CMS内容管理系统&#xff0c;自定义内容模型、自定义单页、自定义表单、专题、统计报表、会员发布等 提供全部前后台无加密源代码和数据库私有化部署&#xff0c;UniAPP版本提供全部无加密UniAPP源码。 ​构建高效内容管理的基石 一、引言&#xff1a…

数据结构—队列(C语言实现)

文章目录 前言一、队列的概念二、队列的实现Queue.hQueue.c 三、设计循环队列问题数组实现链表实现 总结 前言 嗨喽喽&#xff01;&#xff01;小伙伴们&#xff0c;大家好哇&#xff0c;欢迎来到我的博客&#xff01; 今天将要分享的是另一种数据结构—队列&#xff0c;以及…

迈向F5G-A,开启全光万兆新时代——南通移动完成全市首个50G-PON技术验证

近日&#xff0c;南通移动在崇川区完成全市首个50G-PON万兆技术现网验证&#xff0c;标志着南通成为首批具备F5G-A(The 5th GenerationFixed Network-advanced)的万兆光网城市&#xff0c;使其成为网速最快、覆盖最全、时延最低的城市之一。 作为全光万兆的关键技术&#xff0c…

计算机图形学入门01:概述

1.什么是图形学? The use of computers to synthesize and manipulate visual information. 图形学是合成和操纵视觉信息的计算机应用。 百度百科&#xff1a;计算机图形学(Computer Graphics&#xff0c;简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格…

深入解析MySQL 8中的角色与用户管理

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 &#x1f38f;&#xff1a;你只管努力&#xff0c;剩下的交给时间 &#x1f3e0; &#xff1a;小破站 深入解析MySQL 8中的角色与用户管理 前言角色和用户的基础概念用户&#xff08;User&#xff09;…

一个基于预训练的DenseNet121模型的人脸年龄分类系统

这篇文章采用预训练的DenseNet121模型并使用自定义的数据集类和自定义的类似正态分布的标签平滑策略来训练了一个人脸年龄分类模型&#xff0c;最后基于这个模型用tk实现了一个娱乐向的小系统。 数据集展示&#xff1a; 两个文件夹&#xff0c;分别是训练集和测试集&#xff0…

光伏组件积灰检测系统

光伏组件积灰检测系统是一种专门用于监测光伏组件表面灰尘积累情况的设备。以下是关于该系统的详细信息和特点&#xff1a; 系统概述 光伏组件积灰检测系统安装在光伏板的框架上&#xff0c;通过实时监测光伏组件表面的灰尘厚度、分布情况和清洁度&#xff0c;为运维人员提供…

深入分析 Android Activity (五)

文章目录 深入分析 Android Activity (五)1. Activity 的进程和线程模型1.1 主线程与 UI 操作1.2 使用 AsyncTask1.3 使用 Handler 和 Looper 2. Activity 的内存优化2.1 避免内存泄漏2.2 使用内存分析工具2.3 优化 Bitmap 使用 3. Activity 的跨进程通信&#xff08;IPC&#…

如何修改WordPress网站的域名

我的网站用的是Hostease的虚拟主机&#xff0c;但是域名是之前在其他平台买的&#xff0c;而且已经快到期了&#xff0c;因为主机和域名在不同的平台上&#xff0c;管理不太方便&#xff0c;所以我又在Hostease重新注册了一个域名&#xff0c;然后把网站换成了新的域名&#xf…

配置环境变量

配置环境变量$(xxxx)&#xff0c;代表宏 32位操作系统&#xff0c;请自觉将文中路径中所有的x64换成x86。 %符号表示引用系统环境变量或用户自定义的环境变量 如果你想将某个文件夹添加到Visual Studio的路径中&#xff0c;你可以在环境变量中添加%FolderName%&#xff0c;其…

java项目之高校教师科研管理系统源码(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的高校教师科研管理系统源码。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 高校教师科研管…

关于python中屏蔽输出

python中屏蔽输出包含屏蔽标准输出&#xff08;比如打印出来的内容&#xff09;、屏蔽标准错误&#xff08;错误信息&#xff09;还有屏蔽logging信息等。 屏蔽标准输出 import contextlib import oswith open(os.devnull, "w") as devnull:with contextlib.redire…

100个 Unity小游戏系列四 -Unity 抽奖游戏专题二 水果机游戏

一、演示效果 二、知识点 2.1 布局 private void CreateItems(){for (int i 0; i < rewardDatas.Length; i){var reward_data rewardDatas[i];GameObject fruitOjb;if (i < itemRoot.childCount){fruitOjb itemRoot.GetChild(i).gameObject;}else{fruitOjb Instant…

大屏表格实现无限滚动效果

实现效果 实现思路 首先固定最外层的高度&#xff0c;并且设置超出高度后隐藏设置每一行的高度为固定35PX&#xff0c;默认显示10行&#xff0c;所以最外层高度就是 35 * 10 表头的高度遍历时克隆一份表格数据&#xff0c;用于视差效果显示设置滚动动画&#xff0c;让表格行所…

VMware vSphere Distributed Services Engine 和利用 DPU 实现网络加速

VMware相关学习专栏&#xff1a;虚拟化技术 vSphere 8.0 通过加速数据处理单元 (DPU) 上的网络功能实现了突破性的工作负载性能。 vSphere 8.0 通过加速 DPU 上的网络功能实现了突破性工作负载性能&#xff0c;从而满足现代分布式工作负载的吞吐量和延迟需求。借助 vSphere Dis…

GIGE 协议摘录

系列文章目录 GIGE 学习笔记 GIGE 协议摘录 文章目录 系列文章目录引言第 1 章 设备发现1.1 链路选择1.1.1 单链路配置1.1.2 多链路配置1.1.3 链路聚合组配置 LAG 1.2 IP配置1.2.1 协议选择1.2.2 静态IP1.2.3 DHCP1.2.4 链接本地地址 LLA 1.3 设备枚举1.3.1 GVCP设备发现 引言 …

4个月赚20万!一张图赚7500!多种变现方式,一个被忽视的暴力项目

大家好&#xff0c;今天给大家带来一个被很多人忽视&#xff0c;不起眼确很暴力的项目。 大胆放心干 课程获取&#xff1a; https://hsgww.com/https://hsgww.com/