xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

HDU-2243 考研路茫茫——单词情结 AC自动机+矩阵快速幂

题意给n个模式串，问有多少个长度不超过L的字符串中至少出现一种模式串。分析有多少个长度为L的字符串中不出现任意一个模式串的题已经做过，构造一个矩阵\(A\)，答案\(s_n\)即为\(s_0*A^n\) 用矩阵快速幂算下就行了，这题的计算方法就显然是\(26^0+26^1+26^2+\...

AC自动机矩阵快速幂

2019-09-26

0 485

HDU-2222 Keywords Search AC自动机模板

题意给n个模式串，一个文本串，问文本串中出现了多少个模式串。分析 AC自动机模板 Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define lso...

AC自动机

2019-09-25

0 388

2019ICPC上海网络赛 A Lightning Routing I 点分树(动态点分治)+线段树

题意给一颗带边权的树，有两种操作 \(C~e_i~w_i\)，将第\(e_i\)条边的边权改为\(w_i\)。 \(Q~v_i\)，询问距\(v_i\)点最远的点的距离。分析官方题解做法：动态维护直径，然后再支持询问两个点的距离，后者可以 dfs 序 + lca + 树状...

点分树动态点分治线段树

2019-09-25

0 444

洛谷P2634 [国家集训队]聪聪可可点分治模板

题意在一棵树上任意选两个点，求它们距离模3为0的概率。分析树分治模板 Code #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define lson l,m...

点分治

2019-09-19

0 391

codeforces1209E2 状压dp，枚举子集

题意给一个n行m列的矩阵，每一列可以循环移位，问经过任意次移位后每一行的最大值总和最大为多少。分析每一行的最大值之和最大，可以理解为每一行任意选择一个数使它们的和最大。设\(dp[i][S]\)为前i列，已经确定值的行集合为S时，和的最大值。答案为\(dp[m][(1<<...

状压dp

2019-09-18

0 377

2019icpc沈阳网络赛 D Fish eating fruit 树形dp

题意分别算一个树中所有简单路径长度模3为0，1，2的距离和乘2。分析记录两个数组， \(dp[i][k]\)为距i模3为k的子节点到i的距离和 \(f[i][k]\)为距i模3为k的子节点的个数 \(ans[k]\)为所有简单路径长度模3为k的距离和 \(v\)是\(u\)的儿子...

树形DP

2019-09-14

0 351

POJ - 3376 Finding Palindromes manacher+字典树

题意给n个字符串，两两拼接，问拼接后的\(n\times n\)个字符串中有多少个回文串。分析将所有正串插入字典树中，马拉车跑出所有串哪些前缀和后缀为回文串，记录位置，用反串去字典树中查询，两字符串拼成回文串有三种情况：未匹配完，反串后缀是回文串。匹配结束，正串后...

manacher 字典树

2019-09-12

0 507

HFUUOJ1024 动态开点线段树+标记永久化

题意分析动态加点线段树，标记永久化好写常数小 Code #include<bits/stdc++.h> #define fi first #define se second #define lson l,mid,p<<1 #define rson mid+1,...

线段树

2019-09-12

0 506

HDU 3374 exkmp+字符串最大最小表示法

题意找到一个字符串中最先出现的最小(大)表示位置，和最小(大)表示串出现次数分析用最小(大)表示法求出最先出现的最小(大)表示位置，然后将串长扩两倍用exkmp找出现次数。 Code #include<bits/stdc++.h> #define fi first #de...

exkmp 字符串最大最小表示法

2019-09-10

0 366

模板 BSGS

EXBSGS 用于求解形如\(a^x≡b~(mod~p)\)的方程 ll exbsgs(ll a, ll b, ll p) { if (b == 1LL) return 0; ll t, d = 1, k = 0; while ((t = gcd(a, p)) != 1)...

BSGS

2019-09-09

0 330