3 calabash_boy

尚未进行身份认证

我要认证

退役

等级
TA的排名 4w+

NEERC 2012 Moscow Subregional D Darkwing Duck : 区间最大后缀:单调栈

从叉姐姐那里学到的棒棒题~题意:给一个串,区间询问字典序最大后缀。可以离线。n,q≤5⋅105n,q \le 5\cdot 10^5n,q≤5⋅105题目链接题解:在线做法还没看懂,留坑。离线做法是这样的:首先去掉这个题的字符串背景,单纯考虑求区间最大值,有一种离线单调栈的做法:从左到右扫,维护一个单减的单调栈,然后每次处理掉所有r=ir = ir=i的询问,只需要在单调栈里二分l...

2020-01-02 12:23:06

字符串科技:Palindrome Series

文章目录简介背景知识弱周期定理Border SeriesPalindrome SeriesPAM例题:CF 932G题意题解暴力DP使用Palindrome Series优化DP符号约定转移方法总结代码第二个题: 2019 ICPC 沈阳 MNote题意:题解:代码:简介其实不太清楚这个应该叫什么,知道的同学可以麻烦告知我。众所周知,一个串的border数量是O(n)O(n)O(n)的,但是...

2019-11-19 23:51:13

GP of China H Inner Product: 边分治 + 虚树dp

题意给出两棵树TTT和T′T'T′,求∑i,j∈[1,n]dis(i,j)∗dis′(i,j)\sum_{i,j \in [1,n]}{dis(i,j) * dis'(i,j)}i,j∈[1,n]∑​dis(i,j)∗dis′(i,j)题解对TTT进行边分治,当前分治的边为<u,v><u,v><u,v>,边权为www时,设uuu一侧的点集为LLL,v...

2019-10-15 23:57:46

洛谷P5115 : SAM + 边分治 + 虚树dp

题意给出串SSS,K1,K2K1,K2K1,K2,求∑i=1n∑j=i+1nLCP(i,j)⋅LCS(i,j)⋅[LCP(i,j)≤K1]⋅[LCS(i,j)≤K2]\sum_{i = 1}^{n} \sum_{j = i + 1}^{n}{LCP(i,j) \cdot LCS(i,j) \cdot [LCP(i,j) \le K1] \cdot [LCS(i,j) \le K2]}∑i=1n...

2019-10-15 01:00:37

Codeforces 图论板刷总结(更新中)

图论太菜了呀,那怎么办呀,刷点题吧,写下来可以以后复习,或者造福后人?大概就从这开始刷吧:Link题目对应简略思路+题解786B 区间图最段路741C 构造题 二分图567E 最短路DAG必经边527E 欧拉回路786B 区间图最段路没啥好说的,标准的区间图最短路,建议整理板子。我的板子:Link741C 构造题 二分图很容易被搞到2-sat上去,但是猜到一定有解的情况下, 构造出二分...

2019-09-07 22:09:17

洛谷 P4557 战争:凸包+闵可夫斯基和

题意:给出两个凸包AAA和BBB,有若干询问,每次给出一个向量V=(x,y)V = (x,y)V=(x,y),将BBB按照VVV的方向平移到B′B'B′,然后回答AAA和B′B'B′是否相交。题解:题目的条件等价于 存在点a,ba,ba,b,其中a∈A,b∈Ba\in A, b \in Ba∈A,b∈B,且满足a=b+Va = b + Va=b+V。则得...

2019-05-13 21:51:49

ICPC World Final 2019 G First of Her Name :广义SAM / 离线ACAM / 树上SA

题意:给出n个人,他们每个人的名字都是之前某个人的名字在最前边加上一个字母得到。比如2号的名字是ACACAC,3号在2号前边加一个字母KKK,这样3号的名字是KACKACKAC。之后给出k次询问,每次给出一个字符串TTT,询问名字前缀是TTT的有几个人。题解1:把每个人名字反过来看,所有人的名字就是一个Trie。要求的是以某个T(需要把输入的T给做一次reverse)为后缀的串个数。因此考...

2019-04-05 22:59:52

莫比乌斯反演、容斥 题集

洛谷 P2257题意求x∈[1,N]x \in[1,N]x∈[1,N],y∈[1,M]y \in [1,M]y∈[1,M],且(x,y)=质数(x,y) = 质数(x,y)=质数的点对个数\begin{equation}\sum\end{equation}

2019-02-01 13:54:10

Codeforces 653F Paper Task : SAM

题意:给出一个括号串,求有多少个本质不同的合法括号子串。题解:首先,本质不同操作,果断SAM走一波。然后括号序列,前缀和一波,处理得到sum数组。然后map<int,vector<int>>map<int,vector<

2018-12-20 01:32:40

2014 ACM/ICPC 牡丹江 J Jacobi Pattern

题意:给出一个串(len<5000len<5000len<5000),求出所有满足要求的偶数长度区间[l,r][l,r][l,r]的个数:前面一半与后面一半是循环同构。题解:稍微有点面向数据。。。因为无法构造出能卡掉这种做法的数据。。。一个串的前半与后半是循环同构,即S=UV,T=VU,ST=UVVUS = UV , T = VU,ST = UVVUS...

2018-11-01 13:42:19

codeforces gym 100962 D Deep Purple: SAM+树剖+线段树

题意:给出一个字符串,有q次询问,每次询问一个子串S[l,r]S[l,r]S[l,r]最长的border,即最大的t<r−l+1t<r-l+1t<r−l+1,满足S[l,l+t−1]=S[r−t+1,r]S[l,l+t-1] = S[r-t+1,r]S[l,l+t−1]=S[r−t+1,r]。题解1:复杂度O(nlog2n)O(nlog^2n)O(nlog2...

2018-10-30 00:29:37

Codeforces 1073G Yet Another LCP Problem:SAM+虚树DP

题意:给出一个长度为n的串s,每次询问给出两个整数集合:S,T,求∑x∈S∑y∈TLCP(S[x,n],S[y,n])\sum_{x \in S} \sum_{y \in T}LCP(S[x,n],S[y,n])∑x∈S​∑y∈T​LCP(S[x,n],S[y,n])题解:先将S reverse一下,询问等价于 前缀的最长公共后缀,而两个串的最长公共后缀,对应于他们sam节点的fail树...

2018-10-26 23:52:31

Codeforces 570E Pig and Palindromes : DP+滚动

题意:给出一个n*m(n,m<=500)的矩形区域,每个格子上有一个小写字母,从(0,0)出发,只能向右或上走,走到(n,m),且要求路径上的字符构成回文串,问方案数。题解:由于是回文串,要求对称,因此我们从两头一起走。dp[step][xl][xr]dp[step][xl][xr]dp[step][xl][xr]表示现在两头分别走到了(xl,step−xl)(xl,step-xl)...

2018-10-09 14:36:08

Codeforces 246 E Blood Cousins Return: DSU on Tree

题意:给出一棵树,其中father=0的为根,会有多个根,每个点有一个name,有Q次询问,每次询问节点v的深度为h的儿子的name有多少种。题解:DSU ON Tree using mapO(nlog2n)O(nlog^2n)O(nlog2n)Code:#include <bits/stdc++.h>using namespace std;typedef long l...

2018-10-08 13:31:49

ccpc-wannafly Palindrome: SAM+Manacher

题目链接题意:给出一个串串,要求选出两个子串,使他们拼接起来是一个回文串,设一种方案是[l1,r1]在前,[l2,r2]在后拼接而成,则这种方案用有序四元组(l1,r1,l2,r2)表示,求这样的四元组的个数。题解:首先,串串有2e5,如果他是2e5个a,那么答案大约是(2e5)^4,爆掉了ull。。。得开个__int_128\_\_int\_128__int_128 ,好坏怀阿。我们分...

2018-10-04 14:23:30

Codefoces Gym 101915 G Robots : Brute Force

发一个水题。。证明我还活着。。。题意给出一棵边权互不相同且根为1的树,并给出q次询问,每次询问给出一个x,问,从根出发,只能往儿子走,每次会选择不超过x的最大的边走下去,如果不存在儿子或者不存在这样的边,则停止,问最终会停在哪个点,将所有询问的答案求和输出。题解:无脑一把梭题解 :离线,然后LCT,没了。暴力题解:离线,从小到大把边插入树中,每次插边的时候,如果近根点已经有了一个儿子边,...

2018-10-01 22:33:05

UOJ#310 【UNR #2】黎明前的巧克力:FWT

题意: 给出一个数组a,要求把a数组选出两个不相交且不同时为空的子集,满足两个集合中数字的异或和相等。题解:考虑dp[i][j]dp[i][j]dp[i][j]表示考虑前iii个数字,且现在两个集合数字的异或和为jjj时的方案数。转移方程为:dp[i][j]=dp[i−1][j]+2∗dp[i][jxora[i]]dp[i][j]=dp[i−1][j]+2∗dp[i][jxo...

2018-08-17 19:44:03

2018 HDU 多校第一场 1008:RMQ Similar Sequense

题意定义运算RMQ(A,l,r)=maxi=lrA[i]RMQ(A,l,r)=maxi=lrA[i]RMQ(A,l,r) =\max_{i=l}^{r}A[i] 定义两个等长的数组A、B RMQSimilar∼∀i∈{1,n}∀j∈{i,n}RMQ(A,i,j)=RMQ(B,i,j)RMQSimilar∼∀i∈{1,n}∀j∈{i,n}RMQ(A,i,j)=RMQ(B,i,j)RMQ S...

2018-07-24 11:39:22

2018 nowcoder 多校第二场 K题 carpet

题意找一个最小权值和 二维循环周期。题解:一般这种题,都先扔掉最优化的条件,思考如何求解,然后在考虑最优化。那么如何求解二维循环周期(注意不是循环节)呢?显然对于每一行KMP以下就可以找到每一行的循环周期,对于一个size=p行*q列的周期,意味着column[i] = column[i+q],更具体的说就是 对于每一行r 都有s[r][i] = s[r][i+q] 。这意味着q是...

2018-07-24 10:27:27

51Node 2012 字符串的魅力:SAM

题目传送门题解:由于k很小,显然要在这里搞一搞事情的。考虑SAM(由于要考虑所有的子串……就直接想SAM了……),由于每个节点保存的是一些后缀,而这个k是对前缀的限制,诶……经典套路了,把输入串反过来,k就变成了对后缀的限制,那么对于每个节点保存的这些后缀,长度小于k的暴力处理,长度大于k的O(1)处理,细节巨多……写了好久。据说SA可以秒。。。Code:#include...

2018-06-26 13:50:21

查看更多

勋章 我的勋章
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。