xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共101篇）

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

补题目录

HDU6562 线段树，区间在a[i]前后加一个数字 Code

2019-09-09

0 390

“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学) E 小花梨的数组线段树

题意分析预处理出每个数的最小素因子，首先可以知道\(minprime(x*minprime(x))=minprime(x)\)，我们用线段树维护区间最大值\(mx[p]\)，注意这里的最大值并不是实际的最大值，同时维护区间\(a[i]\)乘\(minprime(a[i])\)的次数的最小...

线段树

2019-09-05

0 478