课过专题

【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

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

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