2 KXL5180

尚未进行身份认证

暂无相关简介

等级
TA的排名 5w+

Codeforces Edu 85 G. Substring Search(FFT字符串匹配)

题目连接题意:给你一个s和t串,然后用s去匹配t串中的每一个长度与s相等的子串。如果si=tjs_i=t_jsi​=tj​或者pidx(si)=idx(tj)p_{idx(s_i)}=idx(t_j)pidx(si​)​=idx(tj​)则可以匹配,输出每一个位置可以匹配的情况。做法:显然是不能用常规的字符串匹配去解决。这里如果你做过洛谷上的带有通配符的字符串的匹配,可能知道怎么做,就是用...

2020-04-22 17:42:54

点分治学习模板及一些例题

点分治这里没有动态点分治。。点分治是解决树上问题的一类算法,很多复杂度能从暴力的O(n2)O(n^2)O(n2)降低到O(nlogn)O(nlogn)O(nlogn).具体做法是就是求一个树的重心,树的重心的性质,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡。就是说子树的大小可以lognlognlogn的降低,这样复杂度就降下来了。如...

2020-03-25 12:13:09

P4103 [HEOI2014]大工程

题目题意:给出一个树,给出k个关键点,这k个点每一对点的路径和,最小值以及最大值。做法:首先我们看见多组询问并且k和n同阶,应该就知道是虚树的处理了。首先考虑怎么树上dp。设dp[u]dp[u]dp[u]表示当前uuu为根的子树中关键点之间的和,接下来按照每一个子树的遍历顺序可以得到总的代价可以通过如下关系得到:ans+=(dp[u]+sz[u]∗dis)∗sz[v]+dp[v]∗sz[u...

2020-03-21 14:23:34

虚树——P2495 [SDOI2011]消耗战

好久没有学习新的知识了。https://www.luogu.com.cn/problem/P2495今天我学习了一下虚树。虚树就是一个不存在的树。用来简化问题。它只包括一些关键点和他的LCA我们来看看上面这一道题题意给出一棵树,含有边权。每次询问给出k个点,然后询问每个点与根断开的最小代价。做法因为数据的关系肯定没法直接dp过去的。首先我们可以发现可以与根到其他点的路径没有关系...

2020-03-18 22:14:22

UOJ188【UR #13】Sanrd (Min_25筛)

这里题意:说白了就是求这个∑i=1npsmax(i)\sum_{i=1}^{n}p_{smax}(i)∑i=1n​psmax​(i)其中psmaxp_{smax}psmax​表示次小质因子,规定1和质数的次小质因子为0做法:这道题是一道min25筛法的题,但不过不是普通的积性函数求和,需要对该算法有一定的理解。首先我们还是以s(n,j)s(n,j)s(n,j)表示在1−n1-n1−n范围内...

2020-02-18 15:28:22

Min_25筛 代码及模板

LOJ简单的函数以这道题为例子,讲一下min_25筛如何用代码实现。首先min_25是一种亚线性筛,可以处理1e9以上的数据,老版min_25筛的复杂度为O(n0.75logn)O(\frac{n^{0.75}}{logn})O(lognn0.75​),新版已经优化到O(n23)O(n^{\frac{2}{3}})O(n32​),复杂度,我也不会证明。据说常数比较大,确实是跑得快,但不过差距...

2020-01-19 15:54:17

The 2019 ICPC Asia-East Continent Final(部分题解)

这是今年我的最后一场,顺便写一下游记,第一场因为发挥打铁,心里很郁闷,加之最近学业加(我们学院都是硬件专业) 。那天考了四级(不能过)就和另外一个队一起坐高铁来到西安,到的时候时间还有还可以打一打热身赛,不得不说志愿者服务真好。第一天热身赛,看了一眼,旁边都是比我们好的学校,直接签了A题,C++,JAVA都试了一下还不错,Clion好用,B题刚刚开始想对了,但不过被自己干掉了,然后试了一试机器,...

2020-01-12 20:30:37

Common Substrings POJ - 3415(后缀自动机)

https://vjudge.net/problem/POJ-3415其实很早以前这道题就过了,但不过因为后缀数组的方法自己也不是很懂就没有写。今天我学了一下后缀自动机,我们利用后缀自动机解决。首先对A串建立后缀自动机,然后对每一个非克隆结点进行标记, 然后建一颗fail树,用一个dfs进行计数,这个步骤就是其他博客上写的拓扑排序。首先对于一个结点,他所包含的子串个数为 len[i]−...

2020-01-11 20:35:28

树链剖分 入门题(洛谷)

最近学习了树链剖分。发现这个东西其实并不是很难,而是因为代码量比较长,在码的过程中容易出错。但不过其中还是用套路可循的,如果要学习树链剖分必须要知道DFS序和线段树。这里就不详细讲了,只给出一些入门题,供个人参考。https://www.luogu.com.cn/problem/P3384这是一个模板题首先树链剖分有两个dfs其中一个dfs是处理轻重儿子的,另外一个dfs是维护重链上的...

2020-01-09 10:13:55

P5840 [COCI2015]Divljak【AC自动机+fail树+树上乱搞】

https://www.luogu.com.cn/problem/P5840题意:中文题,给你n个串,然后m次操作,两种操作。1操作,集合T加入一个串。2操作,询问集合T中出现上面的n个串的第i个几次。首先听说解法挺多的,如果有幸学会了,后来补上吧。做法:这里用AC自动机做吧,首先对n个串建立AC自动机,建立fail树,然后每一次往T集合中加入一个字符串,就让他到AC自动机中跑,跑到的点对...

2020-01-07 16:02:47

E. Tree-String Problem (AC自动机+fail树)

https://codeforces.com/problemset/problem/291/E题意:给你一颗树,然后每一条边有一个字符串,然后给你一个字符串,问这个字符在所有的树的根到叶子结点练成的串中,出现了多少次。做法:建立AC自动机,每个点进行计数,在对询问串建AC自动机时不需要计数,然后dfs遍历fail树进行计数就可以了。#include "bits/stdc++.h"usin...

2020-01-07 09:35:40

「TJOI2015」弦论

https://loj.ac/problem/2102只是一道后缀自动机的题目做法:首先当T=0时,就相当于从空串出发的有多少条路径,相当于每一个点都是1,然后dfs进行计数,在后缀自动机上进行贪心的输出就行了。当T=1是,就相当于对于每一个非clone的点都为1 ,然后在建fail树,进行计数就可以了,再用dfs进行计数,在贪心的输出就可以了。#include "bits/stdc++....

2020-01-03 13:44:23

「SDOI2016」生成魔咒

https://loj.ac/problem/2033题意:这道题是中文题。就是给你一个字符串,询问每一个前缀中有多少个不同子串。做法:说到不同子串的数量,应该想到的是某种字符串算法。这道题应该用后缀自动机解决。首先一个字符串中不同子串的数量就是从空串起点t0t_0t0​出发有多少条路径。我们可以利用SAM的树形结构跑一个动态规划 dp[u]=1+∑vdp[v]dp[u]=1+\sum_...

2019-12-31 18:54:51

P3804 【模板】后缀自动机 (SAM)

https://www.luogu.com.cn/problem/P3804很早以前就想把这个坑补了,最近终于把他补了。后缀自动机是对一个字符串信息高度压缩后的产物。这次把这个坑了补了。建议从这些博客入门https://www.cnblogs.com/xzyxzy/p/9186759.htmlhttps://oi-wiki.org/string/sam/https://www.luo...

2019-12-31 17:12:26

Codeforces Round #610 (Div. 2) 简要题解

http://codeforces.com/contest/1282坚持下去谁也不知道结果是什么,但不坚持我肯定会后悔的。这场比赛自闭了,对我极其不友好,读不懂,读懂了又做不来。A.Temporarily unavailable题意:给一个区间[a,b],以及一个基站c,以及信号覆盖范围半径r,一个人以单位速度从a到b运动,问过程中有多少时间不再基站信号范围内。做法:直接模拟即可,求出信...

2019-12-25 15:02:56

gym-102452 香港区域赛部分题解

gym-102452 香港区域赛部分题解本人水平有限只会这几道题B - Binary Tree题意:给出一颗二叉树,Alice和Bob轮流删除子树,子树要求是完全二叉树。在这里想了很久,什么模拟都来了,最后想了一下,好像退了几个样例找到了结论。根据n的奇偶判答案#include<bits/stdc++.h> using namespace std;typedef lo...

2019-12-19 14:28:55

Codeforces Round #594 (Div. 2) 简要题解

http://codeforces.com/contest/1248A. Integer Points做法:统计两条垂直线的截距的奇偶性就行了#include "bits/stdc++.h" using namespace std;typedef long long ll;const int maxn = 100000 + 10; int main() { i...

2019-10-31 21:22:25

P4980 【模板】Polya定理

https://www.luogu.org/problem/P4980题意:很简单的,就一个最简单的polya定理。做法:网上随便看看吧,写得都不错。我们要求的就是上面的式子,我们容易知道|G|=n,|B|=n;但不过重点就是c(g);但不动的时候c(g)=n这点没有毛病吧,因为都没有动。但动k个点时候,这个时候就要看k了,随便找一找规律就知道这个就是 gcd(n,i...

2019-10-10 21:02:09

E.Counting Sequences II (2019上海网络赛)指数生成函数

https://nanti.jisuanke.com/t/41413题意:给出一个1*n的方格,和1-m的数,每一个数有无限多吧,要求,把方格填满,但不过偶数必须出现偶数次,求方案数。做法:首先,我当时不知道这是一道生成函数,给一个学习生成函数的博客https://blog.csdn.net/wu_tongtong/article/details/78854572这道题如果用组合数学的...

2019-09-18 20:23:23

P1231 教辅的组成 (最大流)

https://www.luogu.org/problem/P1231题意:给出书,答案和练习册,以及每本书可以匹配的答案和练习册,问最大有多少匹配。做法:很简单,应该能想到是最大流,但不过建图也很简单,源点-》答案-》书(拆点)-》练习册-》汇点。但不过每一本书只能用一次,必须要拆点,相当于限流。跑一个最大流就可以了。#include "bits/stdc++.h"usin...

2019-09-12 16:50:45

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。