怎样做自己的视频网站,百度关键词排名联系方式,做网站用c语言吗,苏州高端网站制作文章目录摘要基础算法二分倍增前缀和构造图论bfsdfs\dfs序同余最短路差分约束LCA基环树dp线性dp概率期望背包dp树形dp数位dp状压dp区间dp计数dp数据结构优化dp数据结构树上启发式合并主席树Splay线段树分治Kruskal重构树数论基础数论摘要
发现前面学的东西都忘得差不多了…
文章目录摘要基础算法二分倍增前缀和构造图论bfsdfs\dfs序同余最短路差分约束LCA基环树dp线性dp概率期望背包dp树形dp数位dp状压dp区间dp计数dp数据结构优化dp数据结构树上启发式合并主席树Splay线段树分治Kruskal重构树数论基础数论摘要
发现前面学的东西都忘得差不多了想复习也找不到原来写的题了所以从今天开始记录一下学习算法的足迹。
基础算法
二分
Codeforces Round #686 (Div. 3) F. Array Partition 求满足max(1,x)min(x1,y)max(y1,n)max(1,x)min(x1,y)max(y1,n)max(1,x)min(x1,y)max(y1,n)的len1x,len2y−x,len3n−ylen1x,len2y-x,len3n-ylen1x,len2y−x,len3n−y 。根据minminmin和maxmaxmax具有二分的性质直接在二分的时候判断两个条件来调整l,rl,rl,r即可。
倍增
Codeforces Round #717 (Div. 2) D. Cut 倍增 一个比较巧妙的在序列上的倍增启发了能跳一步就可以用二进制倍增一下子跳很多步。
前缀和
Codeforces Round #619 (Div. 2) E. Nanosoft 思维 二维前缀和
构造
Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4) 根据x(x1)moda,y(y1)modbx(x1)\bmod a,y(y1)\bmod bx(x1)moda,y(y1)modb的方式来构造每个点所在的每行每列都不相等的矩阵。 Codeforces Round #712 (Div. 2) D. 3-Coloring 交互 构造 奇偶构造让后第三种颜色放非空的位置。 Codeforces Round #609 (Div. 2) D. Domino for Young 黑白染色 进行黑白染色可以将1×21×21×2的多米诺骨牌进行匹配答案为小的那个颜色。 Codeforces Round #619 (Div. 2) D. Time to Run 矩阵回路构造
图论
bfs
Codeforces Round #619 (Div. 2) F. Super Jaber 多源bfs 思维转换
dfs\dfs序
P3605 [USACO17JAN]Promotion Counting P 配合树状数组解决一类子树统计问题比如这个题就是统计pjpip_jp_ipjpi的个数。
Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4) 模型抽象 问题转化。
同余最短路
通常伪装成一类数论题。
跳楼机 板子题用x,y,zx,y,zx,y,z组成hhh。
墨墨的等式 板子题看到这一类的式子应该很快想到同余最短路让后将[l,r][l,r][l,r]的区间转化为前缀区间即可。
GYM Sums 上一题的简化版这个题只问了能否组成xxx那么只需要xdis[xmodbase]xdis[x\bmod base]xdis[xmodbase]即可。
Lazy Running HDU - 6071 好题 分层 同余最短路
差分约束
E. Capitalism 根据ajai1a_ja_i1ajai1构造不等式让后判断是否有负环且由于这个题的特殊性还要判断是否为二分图。
LCA
Codeforces Round #620 (Div. 2) E. 1-Trees and Queries 思维 LCA 比较巧妙的一个题多加一条边可能改变路径的奇偶性。
基环树
Codeforces Round #686 (Div. 3) E. Number of Simple Paths 基环树求路径长度111的路径个数。用总情况n∗(n−1)n*(n-1)n∗(n−1)减去在一棵树的情况se[i]∗(se[i]−1)/2se[i]*(se[i]-1)/2se[i]∗(se[i]−1)/2即为答案。
dp
线性dp
E2. Square-free division (hard version) 题解 预处理出来leftleftleft数组方便找能转移的位置让后直接dp转移就行啦。
概率期望
P5104 红包发红包 www的红包第kkk个人抢到的钱的期望为w2k\frac{w}{2^k}2kw。
游走 在DAG上路径长度的期望f[i]f[i]f[i]表示到iii这个点的总长度g[i]g[i]g[i]表示到iii这个点路径的总个数。
Codeforces Round #604 (Div. 2) E. Beautiful Mirrors 题解 从111走到nnn失败了就回111号点求到nnn期望步数。主要理解一下回到起点的一部分。 f[i](f[i−1]1)∗pi100(f[i−1]f[i]1)∗100−pi100f[i](f[i-1]1)*\frac{p_i}{100}(f[i-1]f[i]1)*\frac{100-p_i}{100}f[i](f[i−1]1)∗100pi(f[i−1]f[i]1)∗100100−pi
SP1026 FAVDICE - Favorite Dice 一个n面的骰子求期望掷几次能使得每一面都被掷到。求出概率让后期望1/概率得出答案即可。
绿豆蛙的归宿 基础期望dp建反图逆推就好啦。
CF1042E Vasya and Magic Matrix 列出普通式子让后把平方拆开维护一下变量O(1)O(1)O(1)转移即可。
背包dp
AT F - Potion f[i][j][k]f[i][j][k]f[i][j][k]表示前iii个数选了jjj个且modlen\bmod \ \ lenmod len为kkk
树形dp
Codeforces Round #701 (Div. 2) E. Move and Swap 思维 dp 去绝对值优化转移。
数位dp
AtCoder Beginner Contest 194 F - Digits Paradise in Hexadecimal 比较裸的数位dpdpdp了说一下状态吧设dp[pos][state][flag][lead]dp[pos][state][flag][lead]dp[pos][state][flag][lead]为到了pospospos位置状态为statestatestate是否能枚举到上界flagflagflag以及是否存在前导零leadleadlead
Palindromic Numbers LightOJ - 1205 用数位dpdpdp求[l,r][l,r][l,r]有多少个回文数。我们只需要记一下每次选的数让后dpdpdp状态设计加上回文开始的位置preprepre以及当前是否为回文就可以表征出这个数字的状态了。
状压dp
Educational Codeforces Round 80 (Rated for Div. 2) 二分 状压 O(n∗2n)O(n*2^n)O(n∗2n)递推子集。 Codeforces Round #622 (Div. 2) D. Happy New Year 状压dp 根据区间涉及状态将区间离散化成为左闭右开的区间信息都存在左端点先删后加。
区间dp
Codeforces Round #715 (Div. 2) C. The Sports Festival 区间dp 将aaa数组排序之后就是个裸的区间dpdpdp了可以只从两头转移复杂度优化成O(N2)O(N^2)O(N2)。
计数dp
Educational Codeforces Round 81 (Rated for Div. 2) F.Good Contest \ 洛谷 划艇 组合 计数dp
数据结构优化dp
Educational Codeforces Round 81 (Rated for Div. 2) E. Permutation Separation 线段树 dp 通过线段树区间加法以及维护全局最小值可以优化dpdpdp过程。 Codeforces Round #620 (Div. 2) F2. Animal Observation (hard version) dp 线段树 优化区间转移。
数据结构
树上启发式合并
CodeForces - 208E Blood Cousins 树启板子将原本询问与xxx的ppp级祖先相同的个数转化成祖先的ppp级儿子有几个减一即为答案。把询问存到每个点上维护一下子树的depthdepthdepth更新即可。
CodeForces - 570D Tree Requests 每次询问vvv对应的子树中深度为hhh的这层节点的字母能否打乱重排组成回文串。定义一个c[i][j]c[i][j]c[i][j]表示深度为iii字母j′a′jaj′a′有几个让后在定义一个flag[i]flag[i]flag[i]表示深度为iii有几个字母出现了奇数次让后当flag[i]1flag[i]1flag[i]1的时候可以否则不可以。
CodeForces - 600E Lomsat gelral 问子树中出现次数最多的节点编号之和。经典入门题了不多说。
CodeForces - 1009F Dominant Indices d(u,i)d(u,i)d(u,i)表示uuu子树到uuu距离为iii的个数对每个uuu求最小kkk使得d(u,k)d(u,k)d(u,k)最大。定义一个cnt[i]cnt[i]cnt[i]让后更新ididid即可。最后删除子树的时候不要忘记更新maxmaxmax和ididid为000。
CodeForces - 375D Tree and Queries 题解 好题 cntcntcnt维护kjk_jkj的颜色个数可以省掉一层lognlognlogn。
2019 ICPC Asia Nanchang Regional K.Tree 树启 动态开点。
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 树启 状压 好题。需要用到dsudsudsu遍历的顺序先遍历轻儿子清空轻儿子才遍历重儿子所以修改全局的值不会影响到后来遍历的重儿子的值。
主席树
主席树求mex 维护每个数最后出现的位置在第rrr棵树上找出现位置lll的最小值即可。 2016中国大学生程序设计竞赛长春Sequence II HDU - 5919 主席树维护第一次出现的位置维护区间和倒着插入即可。 Prefix HDU - 5790 字典树 主席树 维护每个前缀最后出现的位置查询区间和即可。 P2839 [国家集训队]middle 二分 主席树 在值域上建区间 中位数建主席树优化递推求每次的区间。 P3899 [湖南集训]谈笑风生 主席树解决二维数点 在dfsdfsdfs序上建树让后转换成一个深度区间和一个dfsdfsdfs序区间以深度为下标建立主席树即可。 P3293 [SCOI2016]美味 主席树 伪01trie 利用01trie的思想将树上贪心转换成区间贪心每次都可以转换成区间询问让后根据询问结果更新答案即可。 Codeforces Round #716 (Div. 2) D. Cut and Stick 主席树 思维 主席树查询区间是否存在出现次数大于n/2n/2n/2的数。
Splay
线段树分治
二分图\模板 将每个边出现的时间在线段树上划分成lognlognlogn段让后用可撤销并查集维护就好啦。
CF981E Addition on Segments 线段树分治 bitset优化 题解 将询问区间分成lognlognlogn段让后从根遍历到最后只有一个点的时候保证了这个点可以成为最大值因为所有区间都包含这个点让后每次用bitsetbitsetbitset的左移操作将其加xxx即可。
Kruskal重构树
目前做的题都比较套路维护边权≤w\le w≤w能到的连通块。 Network 黑暗爆炸 - 3732 倍增lca || Kruskal重构树 两点的lcalcalca即为最大边。 Peaks加强版 黑暗爆炸 - 3551 Kruskal重构树 主席树 找到连通块dfs序处理一下即为查询块第kkk大。 P4768 [NOI2018] 归程 Kruskal重构树 倍增 最短路 最短路预处理。
数论
基础数论
HDU - 4497 GCD and LCM 给三个数的lcmlcmlcm和gcdgcdgcd求满足条件的(x,y,z)(x,y,z)(x,y,z)个数。经典套路把(x,y,z)(x,y,z)(x,y,z)都除个gcd(x,y,z)gcd(x,y,z)gcd(x,y,z)让后对lcm(x,y,z)gcd(x,y,z)\frac{lcm(x,y,z)}{gcd(x,y,z)}gcd(x,y,z)lcm(x,y,z)分解质因子统计数量即可。
Educational Codeforces Round 106 (Rated for Div. 2) D. The Number of Pairs 方法同上只不过给了个式子没有那么明显。只需要让lcm(x,y)k∗gcd(x,y)lcm(x,y)k*gcd(x,y)lcm(x,y)k∗gcd(x,y)再进行化简式子就好啦。
Educational Codeforces Round 81 (Rated for Div. 2) D. Same GCDs 欧拉函数 将a,ma,ma,m都除gcd(a,m)gcd(a,m)gcd(a,m)之后答案即为mgcd(a,m)\frac{m}{gcd(a,m)}gcd(a,m)m的欧拉函数。
