vegeone
0%

题意

给定一个只含‘E’、’B’、’F’的字符串,F可以被修改为E或B,求最终转化为没有‘F’的字符串中含有“EE”、“BB”的子串个数和的各种情况

思路

通过找规律可以发现最终的结果是一段等差数列,然后列举F的情况:

  1. 首尾的F转变为E或B可以给答案增加0或1的贡献

  2. 对于中间的F,若两边相同,转变为E或B可以给答案增加0或2的贡献;若两边不同,可以给答案增加1的贡献,这种F可以直接当作E或者B来看
    所以可以得出结论,如果首尾有F,那公差为1,否则公差为2,因此我们只需贪心的求最小值和最大值即可。然后,对于一连串的F,最小值尽可能间隔着以EBEBEB的形式放,最大值尽可能以EEE或BBB的形式放:

  3. 对于情况1,最小值只要和最近的非F字符不同即可,可以做到贡献为0,最大值和最近的非F字符相同即可

  4. 对于情况2,最小值由于需要间隔放,考虑到F串的左右两边相同或否,需要根据奇偶判断贡献为1/0;最大值无论和左边相同还是和右边相同结果一样

阅读全文 »

以下是我的字符串模板:编辑距离、后缀数组、回文树、扩展KMP、字符串哈希、AC自动机、Border、KMP、Manacher、SAM

阅读全文 »

一、课题理解与分析:


所有记分点要求内容均已实现。

根据要求来看,主界面主要实现的是向各个界面的跳转功能。备忘录界面实现的记录的存储、显示以及其他查看操作。待办事项界面可以通过借鉴备忘录界面实现一些记录的存储、显示以及其他查看操作,但是多了时间和提醒的概念。记账只要结合备忘录界面和待办事项界面即可。

对于数据的存储,可以采用数据库来进行存储以及处理。对于大部分的需求内容,都可以采用课上的讲义内容来执行,例如第二章的界面跳转、第三章的recycleview、fab、menu等、第五章的通知提醒等。
文件链接在文末

阅读全文 »

以下是我根据洛谷limit的线段树题单中挑了一部分有趣的题来做,一些trick还是比较有意思的。

阅读全文 »

以下是我的线段树模板

参考了dls的线段树模板,封装+减少了许多的码量

阅读全文 »

这是我的第一个博客,我将在这里分享我的相关内容