1 追风者_

学生身份

我要认证

要我自我介绍,挺秃然的

等级
TA的排名 3w+

Gym 101466 E - Text Editor KMP + 二分答案

题意:给你一个主串和模式串,找出模式串最大的前缀,使得其在主串中的出现次数大于等于n。思路:首先会想到KMP。但是如果直接拿模式串一位一位匹配是O(n2)的时间复杂度,肯定过不了。我们发现模式串长度越长,越不容易满足要求。所以这里有个单调性,可以来二分。我们二分答案可能的长度,然后用这么长的前缀丢进KMP里面,看看能否满足,如果发现可以,就把长度调大一点,反之调小一点。时间复杂度O(nlogn)。最后注意KMP用来计数时,每次匹配完不能直接j=0, i -= p.size(),因为这样会使得指针回溯

2020-10-13 13:34:55

Educational Codeforces Round 96 ABCDE 题解(详解)

我的博客园传送门,看起来更方便些A. Number of Apartments题意:用3、5、7凑数,若能凑出给出方案,不能则输出-1。思路:观察发现除了1 2 4凑不到以外其他都凑得到。那么关于方案的话,既然其他数都凑得到,我们就可以用dp的思想每次试探着来,若减去当前数还是个可以凑得到的就继续减直到等于0。view code#include<iostream>#include<string>#include<algorithm>#include&lt

2020-10-12 22:08:22

Codeforces Round #674 (Div. 3) ABCD 题解

A. Floor Number题意:一开始的数为2,问加多少次x才能加到超过n。思路:水题,循环一遍就行。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#in

2020-09-28 19:40:40

Codeforces Round #673 (Div. 2) ABC 题解

博客园传送门A. Copy-paste题意:问在保持每个数都小于等于k的情况下,最多能执行多少步a[j] += a[i] ,其中(i,j)为任意不同下标。思路:水题,排个序,用a[1]去加到别的值上,看每个数能加多少个a[1],累加贡献即可。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>

2020-09-28 13:29:40

Educational Codeforces Round 95 ABC 题解

我的博客园传送门,看起来更方便A. Buying Torches题意:合成一个物品需要一个a和一个b,一开始有一个a。现在有下面两种操作:1.用1个a换x个a。2.用y个a换1个b。问你合成k个物品最少需要多少次操作。思路:水题,先算出一共需要多少个a,然后用这个数除(x-1)上取整得到合成出这么多a需要的次数,再加上k次转化成b的次数即可。view code#include<iostream>#include<string>#include<algori

2020-09-15 11:20:03

【HDU 5961】 传递 bitset爆破 或 拓扑排序

传送门思路:一开始看到6s,直接用多源最短路看是否每两点距离都是1(若有路径),但是还是T飞了。后来学到bitset的方法,属实不错。这里讲一下自己的理解。我们把这个联通的概念再深入理解一下。如果1->2,表示1到2有一条边,那要满足题目限制条件的话,2连向的所有边,1都应该连过去!。如2->3, 2->4, 2->5 有边,那也一定要有1->3, 1->4 , 1->5 。到此,我们就可以引出bitset了。用二进制串表示当前这个结点和其他点的连接

2020-09-14 14:16:43

Codeforces Round #669 ABC 题解

A. Ahahahahahahahaha题意:给个一个偶数长度的01序列,要求删除不超过2/n个元素使得奇数位和等于偶数位和。思路:注意到题目给的提示,只有0和1,且为偶数长度。那么对和有贡献的也就只有1,而且0或1总有一个出现次数小于等于n/2。所以我们就有这样的策略,把最后搞的只剩0或者1即可,0的个数小就删0,反之删1。最后注意只保留1的时候还要考虑一下答案数组长度的奇偶性。view code#include<iostream>#include<string>

2020-09-09 00:57:34

SCAU 2019年校赛 部分题解

我的博客园传送门,阅读起来方便些18438 First Blood题意:∑i=1a\sum_{i=1}^a∑i=1a​∑j=1b\sum_{j=1}^b∑j=1b​(i+j) , 求和。思路:签到题,照着题目A就行了。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include&lt

2020-08-27 17:41:11

SCAU 2018新生赛 初出茅庐 全题解

我的博客园传送门,看起来更方便一些(em。。。题面都比较直接这里就不赘述题意了)查看代码点击 veiw code18363 ACMer不得不知道的事儿(五)思路:题目问有牌子就行,那就贪心,当懒狗摸铜牌最优。但是有一点要注意。不能直接当前rank/0.6向上取整来算。因为银牌和铜牌是由金牌 * 2和 * 3得到的。比如rank = 5时,若直接⌈5/0.6⌉\lceil 5/0.6 \rceil⌈5/0.6⌉会得到9,然而这个时候是没有金牌的(9*0.1=0,向下取整)。所以这个题要先将当前

2020-08-26 22:21:20

【HDU 1789】 Doing Homework again 贪心 优先队列

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the fin

2020-08-24 22:21:12

【HDU 1257】最少拦截系统 DP or 贪心 详解

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.Input输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于

2020-08-19 14:07:24

【HDU 2159】 FATE 完全背包

最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗?Input输入数据有多组,对于每组数据第一行输入n,m,k,s(0 < n,m,k,s < 100)四个正

2020-08-18 01:05:15

【HDU 1005】 Number Sequence 周期

A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.Given A, B, and n, you are to calculate the value of f(n).InputThe input consists of multiple test cases. Each test case contains 3 integers A, B and

2020-08-07 01:15:06

【Codeforces Round #661 (Div. 3)】 ABCD 题解

E题没思路就没搞了。A. Remove Smallest题意:找出最多的绝对值相差不大于1的对,使得剩下只有一个思路:排个序,相邻着取最优,这样还不能就真的不能了AC代码:#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#i

2020-08-06 00:36:12

【LibreOJ】#6280. 数列分块入门 4 分块

题目描述给出一个长为 的数列,以及 个操作,操作涉及区间加法,区间求和。输入格式第一行输入一个数字 。第二行输入 个数字,第 个数字为 ,以空格隔开。接下来输入 行询问,每行输入四个数字 、、、,以空格隔开。若 ,表示将位于 的之间的数字都加 。若 ,表示询问位于 的所有数字的和 。输出格式对于每次询问,输出一行一个数字表示答案。样例样例输入41 2 2 30 1 3 11 1 4 40 1 2 21 1 2 4样例输出14题意:更新操作:对【L,R】

2020-08-05 16:07:40

【LibreOJ】#6279. 数列分块入门 3 分块

题目描述给出一个长为 的数列,以及 个操作,操作涉及区间加法,询问区间内小于某个值 的前驱(比其小的最大元素)。输入格式第一行输入一个数字 。第二行输入 个数字,第 个数字为 ,以空格隔开。接下来输入 行询问,每行输入四个数字 、、、,以空格隔开。若 ,表示将位于 的之间的数字都加 。若 ,表示询问 中 的前驱的值(不存在则输出 )。输出格式对于每次询问,输出一行一个数字表示答案。样例样例输入41 2 2 30 1 3 11 1 4 40 1 2 21 1

2020-08-05 15:26:15

【LibreOJ】 #6278. 数列分块入门 2 分块

题目描述给出一个长为 的数列,以及 个操作,操作涉及区间加法,询问区间内小于某个值 的元素个数。输入格式第一行输入一个数字 。第二行输入 个数字,第 个数字为 ,以空格隔开。接下来输入 行询问,每行输入四个数字 、、、,以空格隔开。若 ,表示将位于 的之间的数字都加 。若 ,表示询问 中,小于 的数字的个数。输出格式对于每次询问,输出一行一个数字表示答案。样例样例输入41 2 2 30 1 3 11 1 3 21 1 4 11 2 3 2样例输出30

2020-08-05 14:52:22

【LibreOJ】#6277. 数列分块入门 1 分块模板题

题目描述给出一个长为 的数列,以及 个操作,操作涉及区间加法,单点查值。输入格式第一行输入一个数字 。第二行输入 个数字,第 个数字为 ,以空格隔开。接下来输入 行询问,每行输入四个数字 、、、,以空格隔开。若 ,表示将位于 的之间的数字都加 。若 ,表示询问 的值( 和 忽略)。输出格式对于每次询问,输出一行一个数字表示答案。样例样例输入41 2 2 30 1 3 11 0 1 00 1 2 21 0 2 0样例输出25AC代码:#include

2020-08-05 13:23:42

【洛谷】 P2709 小B的询问 莫队算法

题意:若干询问,每次询问输出区间内每个数出现次数的平方和思路:既然是考莫队算法,我们就像add和del函数怎么写。考虑对每个位置i,它对答案的贡献就是这个位置产生的次数贡献,cnt[a[i]]++,然后看看应该增多少。若原来的cnt[a[i]]为m-1,目前为m,那增量为m2 - (m-1)2 = 2m - 1。所以add函数就加上2*m-1即可。del则反过来。AC代码:#include<iostream>#include<string>#include<alg

2020-08-05 00:26:56

【洛谷】P1903 [国家集训队]数颜色 / 维护队列 带修莫队

题目描述墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?输入格式第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。输出格

2020-08-04 23:43:39

查看更多

勋章 我的勋章
  • 签到王者
    签到王者
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)