kkkkahlua-CSDN博客

原创 CSDN拜拜~

新博客：http://www.cnblogs.com/kkkkahlua/还是因为之前博客更新的事情...溜去了博客园今天回来想发个公告发现博客配置里面又可以换回原来的版面了...有点小遗憾毕竟这里也攒了一些东西了...嘛嘛嘛嘛怎么说...博客园还是比CSDN好看很多_(:з」∠)_

2017-10-08 22:59:22 496

原创 Codeforces 526D Om Nom and Necklace 循环节 kmp

题目链接题意给定一个串 TT，对它的每一个前缀能否写成 A+B+A+B+...+B+AA+B+A+B+...+B+A 的形式（kk 个 AA，k+1k+1 个 BB，均可为空串）思路A+B+A+B+...+B+AA+B+A+B+...+B+A 可以看做 AB+AB+AB+...+AAB+AB+AB+...+A，即 kk 个 ABAB 和 11 个 AA. 也就是判断这个串能否被表示为 kk 个循

2017-09-22 15:30:03 612 1

原创 Codeforces 536B Tavas and Malekas kmp找所有与前缀匹配的后缀

题目链接题意有只含小写字母的字符串 TT，其中出现了若干次字符串 PP，并升序给出其中一部分 PP 的起始位置，要求 TT 有多少种不同的可能。思路就是找有多少空缺位置 kk，答案就是 26k26^k.按顺序把 PP 往 TT 中填充，同时记录空缺位置。此时需要判断是否与之前已填充的部分矛盾，其实就是判断给定的 PP 的前缀与后缀是否匹配。直接比较显然会 tletle. 故应预处理出 PP 的所有与

2017-09-21 20:47:34 415

原创 HDU 4125 Moles 二叉排序树树状数组 kmp

题目链接题意将一串数（n≤1e6n\leq 1e6）依次插入到一棵二叉排序树中，dfsdfs一遍，将经过的每个节点的信息加到一个串尾（如果当前节点为奇数则加′1′'1'否则加′0′'0'）。最后再给一个模式串，问其在得到的串中出现了多少次。思路这道题的每一块都十分清晰，建树，dfsdfs，kmpkmp。然而问题就出在了数据量上。因此，要在两个方面进行优化。11. 插入到二叉排序树中：这里有用到一个性

2017-09-21 00:23:07 287

原创 HDU 1867 A + B for you again 字符串拼接 kmp

题目链接题意给定两个字符串 AA，BB，可以拼成 ABAB 也可以拼成 BABA，拼接时前缀与后缀的相同部分在拼接成的字符串中只出现一次。要求输出最短的且字母序最小的字符串。这道题关键是要读懂题意= =思路基本同HDU 2594 Simpsons’ Hidden Talents 两字符串前缀与后缀的最长公共部分.直接用 failfail 数组就完了。Code#include <bits/stdc++

2017-09-20 20:26:58 250

原创 HDU 6208 The Dominator of Strings 读入挂＋kmp / AC自动机

题目链接题意给定 nn 个串，问是否存在一个串包含其它所有串。读入的问题The total length of strings in each case has the limit of 100000.The limit is 30MB for the input file.考虑将所有的串读到一整个串里，记录每个串在其中的开始位置和长度注意：这种情况下，如果每个串末尾有 '\0'，则开的长度不是

2017-09-20 09:32:50 292

原创 HDU 2594 Simpsons’ Hidden Talents 两字符串前缀与后缀的最长公共部分

题目链接题意对于给定的两个字符串 TT 与 PP，求最长的子串，既是 PP 的前缀，又是 TT 的后缀。法一：kmp思路对 PP 求 failfail 数组，然后与 TT 进行匹配，最大长度即为匹配到最后的公共长度。注意在中间就匹配成功时处理一下。Code#include <bits/stdc++.h>#define maxn 100010using namespace std;typedef

2017-09-19 21:25:08 499

原创 hdu 1358 & hdu 3746 & poj 2406 & uva 12012 循环节与kmp

参考kmp next函数 kmp的周期问题，深入了解kmp中next的原理 ——Because Of YouHDU 1358题意对于给定的字符串 TT，对其每一个前缀，问其是否由若干个循环节祖成。思路充要条件：len%(len−fail[len])==0len \% (len-fail[len]) == 0Code#include <bits/stdc++.h>#define maxn 10

2017-09-19 20:14:07 335

原创 HDU 3336 Count the string 所有前缀在串中的出现总次数

题目链接题意给定一个串 SS，求其所有前缀在其中的出现次数的总和。思路考虑 failfail 数组，fail[i]=jfail[i] = j 的含义是 S[0..j−1]==S[i−j..i−1]S[0..j-1] == S[i-j..i-1].记 dp[i]dp[i] 为以 ii 结尾的串中与前缀相同的串的个数。由 fail[i]=jfail[i] = j 有 S[0..j−1]==S[i−j..

2017-09-19 18:58:23 845 1

原创 HDU 4749 & POJ 3167 kmp变形

HDU4749题意给定一个主串 TT 和模式串 PP，问 TT 有多少个不重合的子串与 PP 匹配。在这里，串 aa 与串 bb 匹配的含义是，∀i,j,1≤i,j≤n,⎧⎩⎨a[i]<a[j]↔b[i]<b[j]a[i]==a[j]↔b[i]==b[j]a[i]>a[j]↔b[i]>b[j]\forall i,j,1\leq i,j\leq n,\begin{eqnarray}\begin{cas

2017-09-19 16:57:08 462

原创 2017 ACM-ICPC 亚洲区(西安赛区)网络赛 E Maximum Flow

题目链接题意有 nn 个点，0,1,2,...,n−10,1,2,...,n-1，对于没对点 <i,j>(0≤i<j<n)<i,j>(0\leq i\lt j\lt n)，有一条 i→ji\rightarrow j 边，流量为 i Xor ji\ Xor\ j，问从 00 到 n−1n-1 的最大流。思路首先，00 到 n−1n-1 必须要割；其次，对于任意一个 ii，0→i0\rightarrow

2017-09-17 11:18:37 757

原创 HDU 6194 string string string 后缀数组+rmq

题目链接题意问一个字符串有多少个子串出现恰好 kk 次思路求出 heightheight 数组后，对于相邻的 kk 个后缀，它们包含恰好出现 kk 次的子串当且仅当 k−1k-1 个 heightheight 值中的最小值 >\gt max{max\{其中第一个与前一个的公共前缀，其中最后一个与后一个的公共前缀}\}，差值即为这一段的个数。遍历一遍统计即可，最小值用 rmqrmq。注意 k=1k=1

2017-09-15 19:20:47 248

原创后缀数组倍增算法模板详解

参考2009国家集训队论文后缀数组——处理字符串的有力工具 ——罗穗骞模板bool cmp(int* r, int a, int b, int l) { return r[a] == r[b] && r[a+l] == r[b+l]; }void init(int* r, int* sa, int n, int m) { int* x=wa, *y=wb, *t, i, j, p;

2017-09-15 13:39:45 555

原创 2017多校九 hdu6162 02题 Ch's gift dfs序+树状数组+离散化 / 树链剖分+线段树

题目链接题意给定一棵 nn 个节点的树，每个点上有权值。mm 次询问，问 u,vu, v 链上满足权值 a≤val≤ba\leq val \leq b 的点的权值和。思路将一条链拆成四条从某个结点到根节点的链，即转化为问根节点到某个结点的链上满足权值 a≤val≤ba\leq val \leq b 的点的权值和。离线处理，将从链中拆出来的四个点u,v,lca(u,v),fa(lca(u,v))u,

2017-09-14 11:38:41 287

原创 2017多校九 01题 HDU6161 Big binary tree 树形dp+hash

题目链接题意有一棵 nn （n≤1e8n\leq 1e8）个节点的完全二叉树，节点 ii 的父亲节点是 ⌊i2⌋\lfloor\frac{i}{2}\rfloor。初始时每个点的权值都是它本身。现有两种操作 mm 次（m≤1e5m\leq 1e5）：修改某个点的权值询问经过某个点的权值和最大的链的权值和思路dp[ ]dp[\ ] 记录从某个点向下走最长的链的权值和，修改即一路向上更新

2017-09-14 08:21:27 533

原创 AtCoder ARC082 E Convex Score 贡献思想双射

题目链接题意给定 NN 个点，对于一个凸 nn 边形，称其的 nn 个顶点构成一个集合 SS，并且这个多边形内及其边上有 kk 个顶点，定义这个 SS 的 scorescore 为 2k−n2^{k-n}. 对所有的 scorescore 求和，输出 mod 998244353mod\ 998244353 的值。思路考虑一个凸 nn 边形，其内与其上共 kk 个顶点，那么它对最后答案的贡献是 2k−

2017-09-09 01:06:44 529

原创 LeetCode Best Time To Buy and Sell Stocks I II III IV

I题意要求：交易一次（交易的定义为一次买入和一次卖出，并且进行下一次交易前上一次交易必须结束，且同一天不能同时进行买入和卖出的操作）思路求个前缀最小值和后缀最大值，枚举中间点时间复杂度：O(n)O(n)Codeclass Solution {public: int maxProfit(vector<int>& prices) { int n = prices.siz

2017-09-08 23:36:36 214

原创 BZOJ 2212 [Poi2011]Tree Rotations 线段树合并

题目链接题意现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 nn 个叶子节点，满足这些权值为 1..n1..n 的一个排列)。可以任意交换每个非叶子节点的左右孩子。要求进行一系列交换，使得最终所有叶子节点的权值按照遍历序写出来，逆序对个数最少。参考线段树的合并 ——杭州二中黄嘉泰【bzoj2212】[Poi2011]Tree Rotations ——

2017-09-05 23:16:21 307

原创 HDU 4585 Shaolin 找最接近的数 Treap / set

题目链接题意若干组插入与询问，每次询问与当前要插入的数最接近的数。思路向左走向右走的时候记录一下即可。（是最近写的 TreapTreap 里面最简单的了(躺倒写博客的时候想了一下，为啥不用 setset 呢！因为是搜 HDU 上 Treap 相关的题目搜到的这题...。用 set 几行就搞定了吗= =而且写 TreapTreap 就相当于自己写了个 setset 啊…。（写 setset 一

2017-09-05 17:41:14 223

原创 HDU 5877 Weak Pair dfs序 + 树状数组 + 离散化

题目链接题意给定一棵树，点上有权值。问多少对点 (u,v)(u,v) 满足 uu 是 vv 的祖先且 val[u]∗val[v]≤kval[u]*val[v]\leq k.思路类似dfs序题目小集-hdu 3887注意点因为 k≤1e18,val≤1e9k\leq 1e18, val\leq 1e9，所以需离散化，离散化的时候可以将 val[i]val[i] 及 k/val[i]k/val[i

2017-09-05 17:03:43 263

原创 HDU 5096 ACM Rank Treap综合

题目链接2017.9.5 1:40 用很大很大的数据量对拍了好久好久终于找出了错误智障到哭泣 eraseerase 时 bool dir = t->ch[1]->key < t->ch[0]->key; 写成了 bool dir = t->ch[1]->val < t->ch[0]->val; 一直RE完全不知道哪里出了问题，只好一点一点跟别人的代码对，很多无关紧要的地方都改成了别人

2017-09-05 01:45:56 293

原创 BZOJ 2733 [HNOI2012]永无乡 Treap + 并查集

题目链接题意给定一个图，每个点上有权值。两种操作，连结两个点；问与某个点连通的所有点中权值为第 kk 小的点的编号。思路HDU 3726 Graph and Queries 离线处理 treap + 并查集的简易版，直接正着做，也没有修改操作Code#include <bits/stdc++.h>#define maxn 100010int fa[maxn], sz[maxn], val[ma

2017-09-04 17:07:02 218

原创 HDU 3726 Graph and Queries 离线处理 treap + 并查集

题目链接题意给定一个图，每个点上有权值。三种操作： 1. 删去某条边； 2. 修改某个点的权值； 3. 询问与某个点连通的所有点中权值第 kk 大的值；最后输出所有询问的平均值。思路因为是离线操作，所以考虑倒着处理，先删去所有要删的边，倒着处理的时候再加回去，用并查集维护。每一个集合都是一个 TreapTreap，合并的时候把 sizesize 小的树里面的点一个个拆出来往 size

2017-09-04 16:29:28 311

原创 POJ 1442 Black Box 升序询问第k小优先队列 / Treap

题目链接题意按顺序插入 nn 个数，给出 mm 个询问，问插入第 bib_i 个数后序列中的第 ii 小数。法一：优先队列思路因为该题中所问的第 kk 小数是升序询问的，所以可以用两个优先队列搞一搞，第一个降序（维护最小的 kk 个），第二个升序。注意：每次插入前要使第一个队列尽量满，从而保证第二个队列中的最小值大于第一个中的最大值。Code#include <cstdio>#include

2017-09-03 23:23:29 316

原创 POJ 2985 The k-th Largest Group 第k大数 Treap / 树状数组 + 并查集

题目链接题意有 nn 只猫，mm 次操作（n,m≤2e5n,m\leq 2e5）： 0 i j0\ i\ j：将第 ii 只猫所在组与第 jj 只猫所在组合并； 1 k1\ k：询问第 kk 大的组中有多少只猫。法一：Treap参考资料董的博客数据结构之Treap clj的treap ——wbysr POJ 2985 Treap平衡树（求第k大的元素） ——潇洒走一回LW注意点

2017-09-03 23:13:12 245

原创 POJ 3667 Hotel & HDU 2871 Memory Control 线段树区间合并

POJ 3667参考poj 3667 Hotel ——Titanium题意一条线段长度为 nn，初始未被覆盖。进行两种操作 mm 次： 1. 询问最左边的未被覆盖的长度 ≥D\ge D 的区域的左端点，并覆盖这段区域； 2. 清除 [x,x+d−1][x,x+d-1] 区域的覆盖。思路线段树上记录的信息还是老套路，左边连续的最大值，右边连续的最大值，一整段中的最大值；清除操作也

2017-08-31 19:29:40 248

原创 hdu 1540 Tunnel Warfare 线段树 / set

题目链接题意一排数字1,2,3,...,n1,2,3,...,n，一些操作： D xD\ x：擦除 xx（可重复擦除） Q xQ\ x：询问包括 xx 的最长连续区间 RR：恢复上一个擦除的数字法一：线段树思路维护很常规，维护区间内左起连续的个数，右起连续的个数，最大连续的长度。询问时比较独特，需要额外的判断：如果询问的 xx 在当前区间(lsonlson)的右起连续区间内，则要同时询问

2017-08-28 15:47:19 240

原创 poj 3237 Tree 树链剖分线段树

题目链接题意给定一棵树，每条边上都有权值。三种操作： 1. 修改某条边的权值 2. 将某条树链上所有边的权值变为相反数 3. 询问某条树链上的最大边权思路先树链剖分，然后建线段树，维护一段的最大值和最小值（Lazy TagLazy\ Tag 好题）。Code#include <cstdio>#include <cstring>#include <iostream>#include <

2017-08-28 10:42:12 240

原创 BZOJ 4551 树 dfs序+线段树 / 并查集

题目链接题意给定一颗有根树（根为1），有以下两种操作： 1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记）； 2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）。法一：dfs序+线段树分析类似于区间修改，单点查询，因为给某个结点打上标记会对它的整棵子树产生影响。修改的注意点是只有当前修改的情况优

2017-08-27 09:18:10 267

原创 dfs序基本类型详细

参考dfs序七个经典问题 ——weeping本博文又名：手把手教你写树状数组1. 单点修改，子树和查询单点修改，区间查询树状数组维护每个点的权值： 1. 修改xx（增加ww）：单点修改——add(x,w); 2. 查询xx的子树：区间查询——ans=query(le[x])-query(ri[x]-1);2. 单点修改，树链和查询首先将 u−vu-v 树链和查询转化成 u−root,v−

2017-08-25 20:58:01 704

原创 dfs序题目小集

参考dfs序题目练习 ——樱花庄的龙之介大人HDU 5692 +线段树题意给定一棵树，有两种操作： 1. 改变某个点 xx 的权值； 2. 定义路径的价值为其上所有点的权值之和，询问以 xx 为根的子树内的点到根的路径的价值的最大值。分析(画好了图上传不了就很气) 1 /\ 2 3 /\4 5对于这样的一棵树，dfsdf

2017-08-24 20:51:53 1066

原创 2017多校九 05题 hdu 6165 FFF at Valentine 缩点 dp找最长链/拓扑排序

题目链接题意判定一个图是不是单向连通图。 // 其实就是poj 2186，不过poj的那道题数据水了些= = // 浏览题目时看成了FFT at Valentine吓死我= =思路先套路一发，tarjan求强联通分量，缩点，至此预处理完成。（这部分详细内容烦请移步本菜另一篇强联通分量缩点 tarjan 入门题小集）然后怎么处理呢？法一现在我们得到了一个DAGDAG，直观想法就是有没有

2017-08-23 19:53:03 524

原创强联通分量缩点 tarjan 入门题小集

参考强联通分量及缩点tarjan算法解析 ——九野的博客强连通tarjan模版 ——九野的博客hdu 1269题意判断给定的有向图是否强联通，即判断图中的强联通分量数是否为 11.Code#include <bits/stdc++.h>#include <stack>#define maxn 100010using namespace std;struct Edge {

2017-08-22 22:49:45 396

原创 hdu 5608 function 莫比乌斯反演 / 杜教筛

题目链接题意有∑d|Nf(d)=N2−3N+2\sum_{d|N}f(d)=N^2-3N+2求∑i=1Nf(i)\sum_{i=1}^{N}f(i) N≤1e9N \leq 1e9，答案 mod(1e9+7)mod (1e9+7)法一：莫比乌斯反演+杜教筛善后(?) 546ms（先感叹一句…我真的是学啥忘啥，看到题目就啥都不想直接杜教筛的方式展开压根就忘了莫比乌斯反演…明明是这么优美的莫比乌斯反演

2017-08-21 16:44:15 424

原创 BZOJ 3930 [CQOI2015]选数 & 51nod 1244 莫比乌斯函数之和 & BZOJ 2301

这篇文章姑且叫做小总结大杂烩吧（大雾）BZOJ 3930题意从区间 [L,H][L,H] 中选取 NN 个整数，求它们的最大公约数为 KK 的方案总数，答案 mod1e9+7mod 1e9+7. 1≤N,K≤1e9，1≤L≤H≤1e9，H−L≤1e51\leq N,K\leq 1e9，1\leq L\leq H\leq 1e9，H-L\leq 1e5.推导就是莫比乌斯反演最常规的套路了记 f(

2017-08-21 11:43:26 320

原创 BZOJ 3211 花神游历各国线段树 / 树状数组+并查集

题目链接题意两种操作 1. 对一段区间开方 2. 询问区间和思路这道题最关键的地方就是注意到开方操作进行几次后数字就变成了 11（或者有的一开始就为 00），之后的操作都是没有意义的了线段树用一个 flagflag 标记这段区间是否全部 ≤1\leq 1，如果是的话就没有必要继续往下修改了。Code#include <bits/stdc++.h>#define maxn 100010#d

2017-08-20 16:39:39 370

原创 NJU 1017 [JSCPC2016]Heresy 莫比乌斯反演

题目链接题意求∑i=1n∑j=1mi2j2gcd(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m}i^2j^2gcd(i,j) （题面上写 n≤106n\leq 106，事实上是 n≤1e6n\leq 1e6. 十分感谢WuBaizhe，不然我就一直RE死不瞑目了… 莫比乌斯反演这块也是一篇一篇看着WuBaizhe的blog学的，对初学者十分友好，每篇的推导都很详细，非常感谢原

2017-08-20 12:51:51 393

原创 BZOJ 3994 [SDOI2015]约数个数和莫比乌斯反演

题目链接题意求∑i=1N∑j=1Md(ij)\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)其中 d(x)d(x) 为 xx 的约数个数结论d(ij)=∑ii|i∑jj|j[gcd(ii,jj)=1]d(ij)=\sum_{ii|i}\sum_{jj|j}[gcd(ii,jj)=1] 证明参见PoPoQQQ 还有一版iwtwiioi推导原式=∑i=1N∑j=1M∑ii|i∑jj

2017-08-20 11:26:32 238

原创 BZOJ 3309 DZY Loves Math

题目链接题意求∑i=1a∑j=1bf(gcd(i,j))\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i, j)) 其中f(x)={α1,x=p1α1∗p2α2+...+pnαn,α1>α2,...,αn0,x=1\begin{eqnarray}f(x) =\begin{cases}\alpha_1, x = p1^\alpha_1*p2^\alpha_2+...+pn

2017-08-19 00:59:10 213

原创 2017多校八 1002题 hdu 6134 Battlestation Operational 艾弗森约定莫比乌斯函数分块

题目链接题意：Your should calculate the total damage to the battlefield. Formally, you should computef(n)=∑i=1n∑j=1i⌈ij⌉[(i,j)=1],where [(i,j)=1] evaluates to be 1 if gcd(i,j)=1,

2017-08-18 13:14:21 719

空空如也

空空如也