ComplexPug

未归档

做题记录(1)

/ 注册

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

图论

目录 tarjan缩点找环 dijstra 堆优化dijkstra prim kruskal spfa 路径压缩，按秩合并并查集 tarjan缩点找环 #include <bits/stdc++.h&g...

模板

2018-11-06

0 496

分类迷路的算法

目录 ***但好用的线段树调试二分 ***但好用的线段树调试 void debug() { printf("debug\n"); printf(" %d\n", ...

模板

2018-11-06

0 431

manacher

算法流程我们要计算\(i+k\)这个点的回文串，\(i\)这个点是\(i+l[i]\)最大的点，也就是能达到的最远的点当我们计算\(i+k\)这个点没有在最远到达点之前，暴力扩展被包含的话，分情况讨论 ① i-k 回文串有一部分在 i 的回文串之外这种情况p[i+k]=p[i]-k 这时候就...

manacher

2018-11-05

0 478

P3939 数颜色

目录题目思路1(待修莫队) 思路2(vector+二分) 代码1 代码2 题目 P3939 数颜色思路1(待修莫队) 哇，这不是莫队模板题吗 3e5，TLE45分不行我有信仰啊 pow(n,0.66666) 7...

莫队暴力二分

2018-11-04

0 519

P1903 [国家集训队]数颜色 / 维护队列

关于时间复杂度对于多维莫队的复杂度差不多为\(O(n^{\frac{2k-1}{k}})\) 摘自zhihu大佬奇偶分类优化 return a.l == b.l ? (a.l & 1) ? a.r<b.r: a.r>b.r : a.l < b.l; 貌似不会...

莫队

2018-11-02

0 443

括号序和dfs序

记得清北讲过括号序和dfs序，忘记了 dfs序 dfs序就是dfs的顺序，这个好记就是在dfs遍历树的时候，将每个结点开始时记录一次，结束时记录一次而且一个子树可以表示为连续的一段，只有子树操作的时候最好用了虽然我只见过一个也可以用来求子树的权值大小括号序这个就不大常用了就是在...

2018-11-02

0 581

终于在nowcoder爆发了的懒惰

题目这类题目我实在忍不了了 Emma，随便做个nowcode比赛题吧,我在oj上也没找到题意求\(\sum_{L=1}^{n}\sum_{R=i}^{n}a[k](L<=k<=R)\)，使得和最大就是求所有区间的最大值之和思路我们用一个tot维护 \(\sum_{1...

单调栈

2018-11-02

0 457

P4303 [AHOI2006]基因匹配未完成

题目 luogu 暴力60pts部分显然如果没有出现次数==5的条件显然是\(N_{2}\)的求lcs的模板但是加点条件就完全不同了思路这个题短小精悍，不想数据结构那么***无脑我们考虑一下\(N_{2}\)的缺点首先我们知道，只有a[i]==b[j]的时候才会对答案有所贡...

DP 树状数组

2018-10-31

0 527

hdu4719 Oh My Holy FFF 线段树优化dp

思路好久之前的了，忘记什么题目了可以到我这里做luogu 反正就是hdu数据太水，导致自己造的数据都过不去，而hdu却A了好像是维护了最大值和次大值，然后出错的几率就小了很多也许是自己写错了，忘记了留坑待补代码 #include <iostream> #include &...

DP 线段树

2018-10-31

0 438

P1471 方差

题目 luogu 思路 \[\frac{1}{n}*\sum_{1}^{n}( a_{i}-A)^{2}\] \[\frac{1}{n}*\sum_{1}^{n}( a_{i}^2-2*A*a_{i}+A^2)\] \[\frac{1}{n}*(\sum_{1}^{n} a_{i}^{2}-2...

线段树

2018-10-31

0 493