ybt专题

【ybt】【数据结构树状数组课过例6】区间修改区间查询

区间修改区间查询题目链接：YbtOJ 解题思路我们可以把区间修改区间查询的差分与单点修改区间查询结合起来，也就是二维树状数组维护二维前缀和再加上差分。 code #include<iostream>#include<cstdio>#define lb(x) (x&(-x))#define int long longusing namespace std;int n,m

【ybt】【数据结构树状数组课过例4】区间修改区间查询

区间修改区间查询题目链接：YbtOJ 解题思路区间操作，我们可以想到差分。设差分数组为 d d d ，那么求 ∑ i = 1 n a i \sum\limits_{i=1}^na_i i=1∑nai 就可以转换为 ∑ i = 1 n ∑ j = 1 i d i \sum\limits_{i=1}^n\sum\limits_{j=1}^id_i i=1∑nj=1∑i

【ybt】【数据结构树状数组课过例3】严格上升子序列数

严格上升子序列数题目链接：YbtOJ 解题思路我们设 f i , j f_{i,j} fi,j 表示以 i i i 结尾，长度为 j j j 的序列数。如果直接暴力做，那是 O ( n 3 ) O(n^3) O(n3) 的时间复杂度。我们可以离散化，然后用树状数组维护每一种方案数的情况。其实和逆序对挺像的说（无端感受） code #include<algori

【ybt】【数据结构树状数组课过例2】逆序对

逆序对题目链接：YbtOJ/Luogu 解题思路我们可以进行离散化，然后用树状数组维护下标，每次在树状数组中找下标比当前小的就可以了。 code #include<algorithm>#include<iostream>#include<cstdio>#define lb(x) (x&(-x))#define int long longusing namespace

【ybt】【数据结构树状数组课过例1】单点修改区间查询

单点修改区间查询题目链接：YbtOJ/luogu 解题思路树状数组模板题，不解释。 code #include<iostream>#include<cstdio>#define int long long#define lb(x) (x&(-x))using namespace std;int n,q;int c[1000010];void in(int x,int

【ybt】【图论强连通课过例4】恒星的亮度

恒星的亮度题目链接：恒星的亮度题目描述解题思路我们可以先从小向大建边，然后缩点。如果缩点后同一集合内有两个点是小于的关系，那么不符合题意，无解。再用贪心的思想拓扑，累加答案即可。 code #include<iostream>#include<cstdio>#include<queue>#define int long longusing namespa

【ybt】【图论强连通课过例3】最大半连通子图

最大半连通子图题目链接：最大半连通子图题目描述解题思路我们可以发现，任何一个半联通子图在缩点后都是一条链，所以我们可以先用 T a r j a n Tarjan Tarjan 缩点，然后用 d f s dfs dfs 找出最大的数量，再跑一边找一共有多少个。 code #include<algorithm>#include<iostream>#include<c

【ybt】【图论强连通课过例2】受欢迎的牛

受欢迎的牛题目链接：受欢迎的牛题目描述解题思路我们先用 T a r j a n Tarjan Tarjan 缩点。如果一个点没有出度，证明它是明星点。但如果有两个点都没有出度的话，那么它们两个都无法指向，所以没有明星点。输出找出的明星点所包括的奶牛数即可。 code #include<iostream>#include<cstdio>#include<que

【ybt】【图论强连通课过例1】有向图缩点

有向图缩点题目链接：有向图缩点题目描述解题思路强连通分量模板，用 T a r j a n Tarjan Tarjan 算法。 code #include<iostream>#include<cstdio>#include<queue>using namespace std;queue<int> q;int n,m;int ans;int tm,tt;int

【ybt】【数据结构二分堆课过例4】工作安排

工作安排题目链接：工作安排题目描述解题思路我们先以时间为第一关键字、利润为第二关键字排序，然后贪心，在当前时间内选最大的利润。 code #include<algorithm>#include<iostream>#include<cstdio>#include<queue>#define int long longusing namespace std;pri

【luogu P4278】【ybt金牌导航4-5-2】带插入区间K小值（树套树做法）

带插入区间K小值题目链接：luogu P4278 / ybt金牌导航4-5-2 题目大意要你维护待插入和修改的区间 k 小在线的查询。思路正解是块状链表+值域分块，但是我是在替罪羊树专题里面看到这道题了，就用的是树套树。然后写完之后看了看正解的做法，懒得写的但是代码的下面会讲讲大概做法。提前说好，我的代码只能过 luogu 的数据（还要开 O2），因为树套树的复杂度确实非常

【Ybt OJ】[基础算法第5章] 广度搜索 [后半章]

「「「基础算法」」」第 5 5 5章广度搜索 ( ( (后 3 3 3题 ) ) ) 前半章 l i n k link link 目录： D.荆轲刺秦王E.电路维修F.逃离噩梦又臭又长的 c o d e code code D . D. D. 例题 4 4 4 荆轲刺秦王洛谷 l i n k link link 分析：由于一本通上的数据较水可以直

【BFS】Ybt_荆轲刺秦王

荆轲刺秦王解 BFS。注意处理情况的时候细心点。代码 #include <cstdio>#include <iostream>#include <cmath>#include <queue>using namespace std;int n, m, c1, c2, d, a, qx, qy, zx, zy, ans, ans1, ans2;int b[500]

YBT高效进阶 4.6.2 洛谷P1081 开车旅行(最详细)

YBT高效进阶 4.6.2 洛谷P1081 开车旅行 TITLE 题目描述小A和小B决定利用假期外出旅行，他们将想去的城市从1到n编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为h_i城市i和城市j之间的距离d_{i,j},恰好是这两个城市海拔高度之差的绝对值，即 d i , j = ∣ h i − h j ∣ d_{i,j}=|h_i-

1378：最短路径(shopth)（信息学奥赛一本通http://ybt.ssoier.cn:8088/problem_show.php?pid=2060）

1378：最短路径(shopth) 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 5673 通过数: 2243 【题目描述】给出一个有向图G=(V, E)，和一个源点v0∈V，请写一个程序输出v0和图G中其它顶点的最短路径。只要所有的有向环权值和都是正的，我们就允许图的边有负值。顶点的标号从1到n（n为图G的顶点数）。【输入】

【ybt】【图论并查集课过例6】逐个击破

逐个击破题目链接：逐个击破题目描述解题思路我们可以反过来想：我们现在有一些城市，需要把这些城市连成多个并查集，每个并查集中只能有一个敌方城市，要求花费最多。我们排序，贪心即可。 code #include<iostream>#include<cstdio>#include<algorithm>#define int long longusing namesp