• 等级
  • 14836 访问
  • 187 原创
  • 0 转发
  • 30796 排名
  • 30 评论
  • 9 获赞

Manacher 最长回文子串

RL[i]:关于i的回文半径MaxRight:pos能到达的最右端的位置MaxLen:记录答案首先在原字符串中插入字符“#”例如:“abba”->"#a#b#b#a#"这样不影响回文串,好处是可以同时解决长度为奇偶的字符串,而且(回文半径-1)就是原来的回文串长度问题转化为如何高效的求每个字符的回文串半径,当我们知道pos能到达的最右端位置MaxRight,我们继续向后...

2019-02-19 10:58:36

BZOJ 2154 Crash的数字表格 (莫比乌斯反演)

Crash的数字表格今天的数学课上,Crash小朋友学习了最小公倍数(LeastCommonMultiple)。对于两个正整数a和b,LCM(a,b)表示能同时被a和b整除的最小正整数。例如,LCM(6,8)=24。回到家后,Crash还在想着课上学的东西,为了研究最小公倍数,他画了一张NM的表格。每个格子里写了一个数字,其中第i行第j列的那个格子里写着数为LCM(i,j)。一个...

2019-02-07 23:24:02

莫比乌斯函数线性筛

intmo[maxn],vis[maxn],prime[maxn];voidinit(){ mo[1]=1; mem(vis,0); intlen=0; for(inti=2;i<maxn;++i){ if(!vis[i]){ prime[len++]=i; mo[i]=-1; } for(intj...

2019-02-01 09:19:22

BZOJ-2440 (莫比乌斯函数)

题目链接Description小X自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小X的生日,小W想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数,然后选取了第K个数送给了小X。小X很开心地收下了。然而现在小W却记不...

2019-02-01 09:15:56

HDU-5249 KPI(STL or 权值线段树)

题目链接ProblemDescription你工作以后,KPI就是你的全部了.我开发了一个服务,取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录,有时我想知道当前管道内请求的重要值得中间值。Input有大约100组数据。每组数据第一行有一个n(1≤n≤...

2019-01-31 18:15:23

湖南大学第十四届ACM程序设计新生杯(重现赛)- FFind the AFei Numbers(数位dp)

题目链接题目描述AFeilovesnumbers.Hedefinesthenaturalnumbercontaining“520”astheAFeinumber,suchas1234520,8752012and5201314.NowhewantstoknowhowmanyAFeinumbersarenotgreaterthann...

2019-01-08 20:57:36

Kali 拨号上网

下载PPPOEaptinstallpppoe终端输入nm-connection-editor根据提示新建DSL连接

2019-01-07 20:53:11

湖南大学第十四届ACM程序设计新生杯(重现赛)L-The Digits String (矩阵快速幂)

题目链接题目描述Considerdigitsstringswithlengthn,howmanydifferentstringshavethesumofdigitsaremultipleof4?输入描述:ThereareseveraltestcasesendwithEOF.Foreachtestcase,thereisani...

2019-01-06 17:52:19

最小表示法

循环同构字符串S=“dcba”,它的循环同构"cbad",“badc”,“abcd”.最小表示字符串和它的所有循环同构中字典序最小的字符串。S=“dcba"的最小表示"abcd”求最小表示初始i=0,j=1,k=0.i指向第一个字符,j指向第二个字符,k表示增量。每次比较t=s[(i+k)%len]-s[(j+k)%len...

2019-01-05 19:36:24

牛客练习赛36 Rabbit的字符串(最小表示法)

题目链接题目描述Rabbit得到了一个字符串,她的好朋友xxx可以给这个字符串施加一次魔法。魔法可以选择字符串的任一位置,并将该位置后面的所有字符水平拼接到串首。例如:对于字符串abcde,可以通过施加魔法得到cdeab。如果xxx通过施加魔法将字符串的字典序变得严格比之前的小,那么他将拿走这一字符串。Rabbit想知道自己的字符串会不会被xxx拿走。输入描述:第一行一个整数n,表...

2019-01-05 19:13:09

牛客练习赛36 F-Rabbit的蛋糕 (叉积求面积, 记录前缀)

题目链接题目描述Rabbit和xxx获得了一个很大的蛋糕,这个蛋糕实际上是由N个点组成的凸多边形(点从1到N编号,保证没有三点共线)。接着两个人开始分蛋糕,他们准备沿着蛋糕上两点连成的直线把蛋糕切成两份,由于Rabbit是女生,xxx总会把大的那一份分给Rabbit。现在有Q种切的方案,xxx可以选择任意一种,问xxx最多能分得多少蛋糕?输入描述:第一行两个整数N,Q。接下来N行,每行...

2019-01-04 23:35:22

Linux(deepin)下配置atom C++环境

配置方法总是忘记,在这里记录下。安装atomsudoaptinstallatom下载插件在atom的package中下载看大家的网速(貌似需要科学上网)。可以在用clonegithub上的package然后安装。安装nodejssudoaptinstallnodejs#查看是否安装成功nodejs-v安装npmsudoaptinstall...

2019-01-03 23:34:35

Codeforces Round #529 (Div. 3) E. Almost Regular Bracket Sequence (括号配对,前缀和)

翻转一个括号使得所有括号都能配对,问一共可以翻转几个括号。AC方法1:如果某个位置上的右括号数量大于他的左括号的数量那么这个位置及之后的位置无论如何翻转都不能满足配对。例如:())((()第三个位置:右括号2个,左括号1个,位置3之后的括号无论如何变化,第三个位置上的状态都不会改变。同理如果从右边开始考虑,如果某个位置上的右括号数量小于左括号数量,之后位置上的括号也是不能匹配...

2019-01-03 00:31:15

Codeforces Round #529 (Div. 3) F. Make It Connected(最小生成树)

AC最小生成树,建边的时候不需要N2{N^2}N2,首先N个点需要N-1条边,每个顶点都会用到,也会有一些顶点重复。我们让重复的点为权值最小的点,就可以保证生成树最小将特殊边加到边集里,跑一边Kruskal#include<bits/stdc++.h>#definePpair<int,int>#definelowbit(x)(x&amp

2018-12-28 12:18:45

Codeforces Round #528 (Div. 2) - D. Minimum Diameter Tree

AC在树的边缘上分配权值,使得树上最大路径权值和最小。因为是在树的边缘上分配权值,所有所有的中间节点(非叶子节点)的权值为0,这样树上任意两点的距离最大就是一条包含两个边缘节点的路径。统计所有边缘节点(叶子节点)的数目,计算每个节点的权值,然后两个权值和就是答案。#include<bits/stdc++.h>#definePpair<int,int>...

2018-12-24 12:41:29

py-词频统计

title:py-词频统计date:2018-12-2112:32:35tags:[解析式,lambda]categories:Python词频统计importstringpath='C:/Users/Desktop/Walden.txt'withopen(path,'r',encoding='utf-8-sig')astext:#首字母...

2018-12-21 12:41:10

牛客练习赛34 E little w and Digital Root(数位dp)

title:牛客练习赛34ElittlewandDigitalRoot(数位dp)date:2018-12-1722:38:37tags:数位dpcategories:ACM题目链接题目描述数根(又称数字根Digitalroot)是正整数的一种性质,换句话说,每个正整数都有一个数根。数根是将一正整数的各个位数相加(即横向相加),若加完后的值大于等于10的话,则...

2018-12-17 22:48:40

牛客练习赛34 - C little w and Segment Coverage(思维、树状数组)

title:牛客练习赛34-ClittlewandSegmentCoverage(思维、树状数组)date:2018-12-1516:36:55tags:[树状数组,思维]categories:ACM题目链接题目描述小w有m条线段,编号为1到m。用这些线段覆盖数轴上的n个点,编号为1到n。第i条线段覆盖数轴上的区间是L[i],R[i]。覆盖的区间可能会有...

2018-12-15 17:17:35

HDU-4777 Rabbit Kingdomom(树状数组、区间离线)

染发噶发发呆

2018-12-14 12:16:21

牛客小白9 换个角度思考(离线+树状数组)

title:牛客小白9换个角度思考(离线+树状数组)date:2018-11-2915:25:18tags:[离线,树状数组]categories:ACM题目链接题目描述给定一个序列,有多次询问,每次查询区间里小于等于某个数的元素的个数即对于询问(l,r,x),你需要输出的值其中[exp]是一个函数,它返回1当且仅当exp成立,其中exp表示某个...

2018-11-29 15:38:52

henuyh

关注
  • 学生
  • 中国 河南省 郑州市
奖章
  • 持之以恒