2020-09-17 14:39 已编辑 Fleet AntiSubmarine Warfare Training Center (San Diego) C++

关注

好题:KMP应用,数学-Om Nom and Necklace

传送门:https://vjudge.net/problem/CodeForces-526D

题目大意：对于字符串的每一个前缀，询问是否能够看成 k + 1 个 A 和 k个B交替形成的字符串。

题目思路: KMP 找循环节 + 数学推导

着实被这个题解法秀到了.

首先想要答案存在，将 S = A + B。这个S肯定是这个前缀的一段循环节。

我们知道最小循环节为: $min\_cir=n-next[n]$

$设 S = q * min\_cir$

$n = k * |S|+|A|=k * (q*min\_cir)+|A|$

我们知道： $0\leq |A|\leq|S| = q*min\_cir$

$n = k * |S|+|A|=k * (q*min\_cir)+[0,q*min\_cir]$

$=[k * (q*min\_cir),(k + 1) * (q*min\_cir)]$

由于n是定值，那么就是求是否存在一个正整数 q :

$[\frac{n}{(k + 1 )*min\_cir} , \frac{n}{ k *min\_cir} ]$

所以接下来就判断区间中是否包含正整数，可以将左端点的值L向上取值，右端点的值R向下取值，判断 L <= R.

全部评论

推荐最新楼层

昨天 22:11

上海交通大学算法工程师

线程池有哪些核心参数？

面试题简述你平时用过线程池吧？那你说一下线程池有哪些核心参数？提交任务有哪几种方式？如果线程池里的任务抛异常了，你一般是怎么感知和处理的？面试官想听的这道题本质上考察的是并发模型的理解。核心考点在于：1、你是否理解线程池设计背后的资源控制和并发治理，而不仅仅是记住参数；2、你是否理解不同任务提交方式的语义差异，特别是它们如何影响任务的执行和异常处理；3、你是否处理过线程池异常丢失的问题，并能在生产环境中做到预防和监控。面试回答举例线程池的核心目标在于 复用线程、控制并发度、避免资源耗尽。线程池的设计围绕着资源控制和并发治理展开，其核心参数都是为了确保在并发任务量突增的情况下，既能保证系统稳定运...

技术必备题库

点赞评论收藏

02-19 17:14

中北大学测试开发

测试开发 - 小天才 - 三面

自我介绍目前绩点是多少之前实验室的经历具体介绍是自己申请的么有考虑继续深造么之前几段实习的工作岗位还有部门业务的区别，具体介绍综合上来看，在你们学校对你的相关的这个专业培养方面，有哪些是很有力的支持到你的落地实操，有哪些是你觉得它其实在你们往后学弟学妹的培养当中可以持续去迭代和优化的目前对于公司的业务有明确的要求或者投递限制么目前有哪些 offer为什么不考虑其他几家家是哪里的父母退休了么父母做什么工作东莞当地有亲戚或者朋友么个人博客名字的来历对于古文化的哪一方面感兴趣在你看过的历史书籍里，印象深刻的哪一本你现在比照片上瘦了多少现在有 150 斤 么目前期望的总包是多少目前三方在自己手上么反问...

查看20道真题和解析

点赞评论收藏

01-25 15:42

蚌埠坦克学院后端工程师

基本都在宿舍

我基本都在宿舍面试，也没啥讲究，直接开摄像头就开聊，也没有搞一个纯色背景，背后就直接是室友的床铺，不过面试官都挺理解，没也没有因为这个难为我。有次室友洗完澡，湿漉漉地从身后路过，我还在面试呢，面试官也没介意，就当是生活的一部分了，不过还是不要学我比较好，能找一个安静的环境最好

牛客10001：我也宿舍，想不到还能去哪啊，图书馆教室都有人吧，找个没人的楼道或者啥的还忒背着死沉的游戏本，面试时间太长没电了咋整，学校那个面试间至今没搞懂咋开门

你都在哪些场所面过试？

点赞评论收藏

01-30 22:03

门头沟学院 Java

我这个简历春招有机会吗

大家觉得我这个简历能找到什么样的，中厂有希望吗，简历无水分全真实的

用微笑面对困难：我滴妈，【俩月】【实习】【主管】仨debuff吃满了，独立设计开发的项目写了绝大占比的运营板块，你独立开发，那维护、问题复盘、日志更新、bug、策划书全是自己整的？

不建议写那么大，可以从小出发更容易

点赞评论收藏

今天 14:55

吉林大学测试工程师

开水加点🍬

发了一包糖哈哈哈哈，要变成甜水团吗哈哈哈哈哈哈哈哈哈

点赞评论收藏

全站热榜

创作者周榜

正在热议