弓长九日

分类

CDQ(1) codeforces(1) DP(9) SSM框架(3) 《算法竞赛进阶指南》杂谈(14) 二分(1) 分块(1) 动态规划(1) 图论(11) 基本算法(5) 字符串(6) 差分(2) 并查集(2) 思维(18) 搜索(7) 数学(16) 数据结构(17) 未归档(128) 树型结构(4) 树套数(1) 模拟(2) 爬虫(6) 系统配置记录(1) 线段树(8) 计算机网络(2) 贪心(2) 面试(3) 题解(4) 题集(45)

/ 注册

全部文章（共320篇）

2019 牛客暑假多校第八场 A All-one Matrices

第3次了关于最大01矩阵的这次找尽可能大不相互包含的寻找策略是下一层1的长度不等于我当前这层长度剩下的依然是单调栈维护1矩阵左右到哪里 #include<bits/stdc++.h> using namespace std; const int maxn = 300...

2019-08-19

0 552

题解 | 算法竞赛进阶指南关押罪犯

带权并查集+二分图解法带权并查集分析A，B之间的相对距离，可以得到rnk[fa] = rnk[A]+x-rnk[B]。注意到这时，对于原来的A的树，只更新了fa跟结点的权值，那么其它结点的更新在查找的那一步里面实行了。维护是相对距离一开始 ab之间关系 a到b是s 在 fa fb 不一样...

2019-08-19

2 846

题解 | 算法竞赛进阶指南 lost cow (3种做法)

题描述有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。现在这nn头奶牛站成一列，已知第i头牛前面有AiAi头牛比它低，求每头奶牛的身高。输入格式第1行：输入整数nn。第2..n行：每行输入一个整数AiAi,第i行表示第i头牛前面有AiAi头牛比它低。（注意：因为...

2019-08-19

0 1046

2019HDU多校第六场 6635 Nonsense Time (LIS 记录路径)

Problem Description You a given a permutation p1,p2,…,pn of size n. Initially, all elements in p are frozen. There will be n stages that these element...

2019-08-17

0 510

线段树进阶总结二 (区间取模开根)

P4145 上帝造题的七分钟2 / 花神游历各国洛谷区间开根最多开几次根就变成1了这里我们选择维护区间和如果区间和等于区间长度不更新不等于更新到底反正最多跟新不了几次正好问的也是区间和。。 #include <iostream> #include <c...

2019-08-17

0 525

线段树进阶总结一 DFS序欧拉序(括号序)

DFS序前置的几道题线段树DFS序 1 单点更新区间查询 https://blog.csdn.net/qq_40831340/article/details/84501232 线段树DFS序 2 区间子树更新单点查 https://blog.csdn.net/qq_40831340/ar...

2019-08-16

0 702

牛客小白月赛16 小雨坐地铁（分层最短路|优化建图）2019暑期多校训练营（第六场）D move

一种优化分层图建图方法直接暴力建这样线特别乱得图因为中转得关系我们得暴力扫完这些中转用一个虚拟点代表中专这样建就直接处理得换线得问题了考虑分层图最短路。很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(nm^2)的，可能会超时...

2019-08-16

0 546

2019牛客多校第九场 H Cutting Bamboos (二分主席树)

看到题解说二分心里也有数了。。。。。 H Cutting Bamboos 给了一些高度得柱子每区间你可以坎y次 y次之后必须砍没有了没有砍总长度得一样问第x次砍得高度在哪里因为砍得次数和每次砍得总长度是一定得我们二分高度这样剩下得总长度就可以用来做二分得判断了小于高...

2019-08-16

0 464

2019 牛客多校第九场 E All men are brothers (并查集 | 数学)

每4个互相不能是朋友考虑并查集维护我们正着数有点难正好我们朋友关系是一个一个加进去的这样就可以每次减去我们加入这2个集合产生的冲突 + 剩下集合贡献出的2个如果每次在数就超时了而且我们组合数减去的是所有大于2的集合贡献2个元素的量所以开一个变量存下加的时候把这...

2019-08-15

0 554

2019 牛客多校第九场 D Knapsack (折半搜索)

D Knapsack Cryptosystem (折半搜索) 给了36 个数给了 s 问能不能凑出s 我们折半分开搜索复杂度下去就好二进制啊二进制打印反了可还行唉打印二进制打印反了 wa了 #include <bits/stdc++.h> #define int l...

2019-08-15

0 488