工大最菜

分类

01规划(3) ACM比赛总结(3) ACM训练日记(11) bfs(7) dfs(5) Dilworth定理(1) dp(80) exgcd(1) gcd(2) java(1) KM(1) kmp(4) map(4) MOD运算(1) os(3) rmq(1) set(2) STL的操作(1) __int128(1) 一般图带花树的最大匹配(2) 三分(2) 中位数(1) 主席树(6) 二分(8) 二分图匹配(9) 二分图最大匹配(1) 二分图的多重匹配(1) 二维偏序(2) 二进制(2) 优先队列(2) 倍增DP(2) 其他(1) 分块(11) 分层图最短路(1) 分治(5) 分组背包(3) 前缀和(6) 动态最短路(1) 区间dp(18) 单调队列(2) 单调队列dp(2) 博弈论(11) 双连通(5) 同余最短路(1) 后缀和(1) 后缀数组(2) 因数(1) 大整数(1) 大模拟(2) 字典树(1) 字符串哈希(16) 完全背包(1) 容斥(1) 尺取(4) 并查集(3) 序列自动机(2) 康托展开(1) 异或(4) 强连通(1) 思维(6) 扩展KMP(3) 扫描线(2) 技巧(11) 拉格朗日插值法(1) 拓扑排序(3) 数位dp(8) 数学推导(2) 数论(18) 整体二分(2) 暴力(6) 最大权闭合子图(1) 最小生成树(5) 最小表示法(1) 最短路(15) 未归档(2) 构造(2) 构造树(1) 染色问题(1) 树(9) 树dfs序(2) 树上分块(2) 树上启发式合并(6) 树上差分(2) 树形dp(16) 树状数组(3) 树的BFS序(1) 树链剖分(6) 概率(24) 模拟退火(6) 欧拉函数(3) 欧拉回路(4) 点分治(5) 状压dp(11) 珂朵莉树(2) 生成函数(4) 矩阵快速幂(3) 矩阵计数(1) 离散数学(1) 离线(1) 线性基(1) 线性规划(1) 线段树(18) 线段树合并(2) 组合数学(1) 组合计数(1) 网络流(14) 莫比乌斯反演(1) 莫队(6) 表达式求值(1) 计数(5) 计算几何(4) 调度问题(1) 贪心(8) 费用流(6) 费用背包(1) 递归(2) 长链剖分(1) 题解(14)

/ 注册

全部文章（共568篇）

二分连续长度>=F的区间的最大平均值

题目链接：http://poj.org/problem?id=2018 题目大意：是在一个数组里，寻找一段连续和，使其平均和最大，但是长度不能小于F, 首先可以看出是满足单调性的，但是怎么二分呢，我们先枚举一个可能的数。然后数组里的值全部减去这个值（结果会有正有负），那么我们就看是否存一段长度大...

2019-01-31

0 885

BFS有限制的迷宫+技巧

题目链接：https://ac.nowcoder.com/acm/contest/330/C 题目大意：和普通的bfs不同的是：记录不同状态下的最短路，在由从队列中得到x, y时，在判断x，y处是不是’@’。是否可以衍生出新的状态。这样在队列中的时间线不会乱。,并且bfs就记录了所有的状态，最先...

2019-01-30

0 554

数论欧拉降幂+费马小定理+指数循环节

题目链接：https://ac.nowcoder.com/acm/contest/330/E 题目大意：求2^a%1000000007。和队友一直怼快速幂。然后T了。后来发现这个余数应该是循环的，我当时认为循环节是1000000007。后来才知道发现是1000000006。让我们来复习一下费马小...

2019-01-29

0 556

线段树专题节点的含义

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610 题目大意：在一条线上绘制一些彩色片段，一些先前绘制的片段可能被后续的一些片段覆盖。您的任务是计算最后可以看到的不同颜色的片段。每个数据集的第一行恰好包含一...

2019-01-28

0 516

线段树专题开根号的优化

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027 题目大意：有n个战舰都排成一排。我们可以使用我们的秘密武器来使一个区间每个战舰的耐力变成到其原始耐力值的平方根。输入包含几个测试用例，由EOF终止。第一行输入一个整数n 第二行包含n个整数E...

2019-01-28

0 590

线段树专题线段树+离散化

题目链接：http://poj.org/problem?id=3468 题目大意：有一个长为10000000的墙，有1 <= n <= 10000个市长候选人去张贴海报，每个人的海报长度不限。上面的海报会覆盖下面的海报，问你最后能看见哪些海报。思路：这个用线段树add标记维护当前区...

2019-01-28

0 448

三角形的面积爆double + nth_element()

题目链接：https://ac.nowcoder.com/acm/contest/327/A?&headNav=acm 题目大意：平面上有n个点，问：平面上所有三角形面积第k大的三角形的面积是多少? 输入描述: 第一行T，表示样例的个数。对于每一组样例，第一行两个整数n和k，接下来...

2019-01-25

0 528

dp专题字符串转化

题目链接：https://www.luogu.org/problemnew/show/P2758 题目大意：设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种： 1、删除一个字符； 2、插入一个字符； 3、将一个字符改为另一个字符；！皆为小写字...

2019-01-25

0 520

dp专题丢失阵列(组合数dp)

题目链接：http://codeforces.com/problemset/problem/1105/C 题目大意：给你一个n, l, r; 让你构造阵列满足以下条件：阵列长度为n；阵列中所有的整数位于[l, r]之间这个阵列所有的整数和能被3整除让你求有多少个构造方...

2019-01-23

0 479

dp专题公平的坚果和字符串（类似跳台阶dp）

题目链接：http://codeforces.com/contest/1084/problem/C 对于一个由小写拉丁字母组成的字符串s，坚果想找到严格增加的序列p1，p2，…，pk的数量，保证：对于每个i（1≤i≤k），spi =‘a’。对于每个i（1≤i<k），存在pi <j ...

2019-01-09

0 395