弓长九日

分类

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)

/ 注册

全部文章（共313篇）

题解 | 算法进阶指南导弹防御塔

我们考虑跑网络流首先是二分图最大匹配 == 入侵者数量时时间可以缩小点才最多50个 50 * 50 最多发 3000 不到的导弹3000 和原点连 3000个边3000 和入侵者连最多15000边开前向星按 40000 * 8 边差不多了就因为连的太多了暴力点建图将塔分成很...

二分图网络流

2019-08-19

0 721

2019年牛客多校第八场 Explorer (线段树+可撤销并查集)

线段树上套每个区间可以有哪些并查集一直向下如果已经有大区间的管道到n 这个点覆盖区间线段树往下就不必要走了然后学会了安秩合并(启发式搜索) 不能压缩路径我们把大的合并到小的上面就使得长的被查询的的路径尽可能慢的长这样不压缩路径不超时的完成我们合并和实现撤销的操作 ...

2019-08-19

0 442

2019n牛客多校第八场 B Beauty Values (DP or 找规律)

f(i)=f(i-1)+i-(vis[a[i]]?vis[a[i]]:0) 公式怎么出来的呢?考虑由1-i 如果第i个数字出现过,那么他对前一个出现过的i维护的区间是没有贡献的,只有vis[i]-i有贡献. 如果没出现过肯定是前面维护的都+1: 有人可以看出是总ans不断减现在数据之前...

2019-08-19

0 524

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

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

2019-08-19

0 556

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

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

2019-08-19

2 849

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

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

2019-08-19

0 1058

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 521

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

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

2019-08-17

0 541

线段树进阶总结一 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 711

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

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

2019-08-16

0 567