生之、如舟 - 个人主页动态

2020-04-17 18:15

POJ - 2352 Stars 思路 考虑到是从左往右，从下往上给点的，所以可以遍历这个顺序把点插入到树状数组中，每次插入前，看当前树状数组中有多少个x是小于此时的X的，就算是这个点的level了。 代码 模板大于代码系列 #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <map> #include <set> #include <deque> #include <queue&g...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-17 17:05

河南理工大学 golang

POJ-2299 Ultra-QuickSort 【权值树状数组】【思维】

Ultra-QuickSort 题目链接：https://vjudge.net/problem/POJ-2299 思路 其实我们在学冒泡排序的时候，就可以发现有些相邻交换是不必要的。好的交换应该是使得数值更加的靠近他的真正位置。好的排序过程如图所示：这样每次新添加一个数，就看他之前有多少个比他大的数，就是交换次数(这个用树状数组就可以log级别完成统计) 代码 因为这题输入量挺大的，所以我使用了快读 #include <iostream> #include <algorithm> #include <string> #include <cstring&...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-16 19:14

河南理工大学 golang

AcWing 243. 一个简单的整数问题2 【模板题】【树状数组】【区间修改区间查询】

243. 一个简单的整数问题2 题目链接：https://www.acwing.com/problem/content/description/244/ 思路 维护了两个差分树状数组，差分树状数组的区间查询其实就是求一个近似半矩阵的区域，通过近似补矩阵的方法，就可以通过两个比较好算的两个求和，让两个和做差得到真正的区间和 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt"...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-16 18:04

河南理工大学 golang

AcWing 242. 一个简单的整数问题【树状数组】【区间修改单点查询】

AcWing 242. 一个简单的整数问题 题目链接：https://www.acwing.com/problem/content/248/ 思路 把树状数组改成差分数组，每次算差分后的一个数其实就是算前缀和 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-16 15:14

河南理工大学 golang

AcWing 241. 楼兰图腾【权值树状数组】【模板题】

241. 楼兰图腾 题目链接：https://www.acwing.com/problem/content/description/243/ 思路 遍历1-n，每次往树状数组的arr[i]位置插入1，表示arr[i]出现过一次。每当遍历到i时，就能通过树状数组查询小于arr[i]的元素个数，和大于arr[i]的元素个数。和权值线段树一样的操作。 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-25 20:20

已编辑

河南理工大学 golang

SnowWolf's Wine Shop 【multiset】【坑点】

SnowWolf's Wine Shop 题目链接：https://vjudge.net/problem/HDU-1897 思路 在multiset面前，这题就是个模拟，是给multiset量身定做的题，哈哈。因为multiset插入和删除都是logN,然后还可以放入重复元素。所以对于每一个需求，只需要lower_bound一下就可以了。 坑点 auto it = st.lower_bound(cur); 用自带的没问题auto it = lower_bound(st.begin(),st.end(),cur);用普通版的就会超时 代码 #include<bits/stdc++.h&gt...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-15 22:59

河南理工大学 golang

ACWing 244. 谜一样的牛【树状数组】

244. 谜一样的牛 题目链接：https://www.acwing.com/problem/content/description/245/ 思路 计算末尾的牛身高的时候，可以发现就是求他在剩余可选身高中排第几的问题。可以用树状数组算query(r)：前r身高还有多少个。这样对于一头牛说，前面比他低的还有t牛，那么就需要找到第一个query(r) == t+1 ,r就是这头牛的身高。因为树状数组是计算前缀和，所以可以二分操作这个过程 代码 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; ...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-15 21:22

河南理工大学 golang

AcWing 1264. 动态求连续区间和【树状数组】【模板题】

AcWing 1264. 动态求连续区间和 题目链接：https://www.acwing.com/problem/content/1266/ 思路 视频正在路上 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout); #define...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-15 13:40

河南理工大学 golang

codeforces div2 603 D. Secret Passwords 【并查集】

codeforces div2 603 D. Secret Passwords 题目大意： 有很多的字符串，如果两个字符串有相同字母，就属于同一组，字符串a与b一组，b与c一组，那么a也与c一组，问这所有字符串可以被分成几组。 思路 我们只需要维护26个小写字母的并查集就可以了。同属于一个字符串里面的所有字母，肯定属于同一个集合中，因为其他任何字符和这个字符串的一个字符相同，那么就和这个字符串所有字符都建立了关系。所以我们只需要把每个字符串相邻两个字符加进一组，最后看26个字母被分成了几组。注意还要定义一个vis[]数组，因为有些字母可能并没有出现。 代码 #include<bits/s...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-14 13:43

已编辑

河南理工大学 golang

2019 ICPC 徐州网络赛 B.so easy 【并查集路径压缩】

2019 ICPC 徐州网络赛 B.so easy (并查集) 题目链接：https://nanti.jisuanke.com/t/41384 题目大意 给定n个数，从1到n排列，其中有q次操作，操作(1) 删除一个数字 // 操作(2)求这个数字之后第一个没有被删除的数字（包括自己）。 思路 本题就是考的并查集的路径压缩，让每一次find，可以达到O(1)级别，每次删除x的时候，把fa[x] = x+1即可，这样x+1如果也是被删除的，那么fa[x+1] = x+1，这样循环下去肯定会到达x后第一个没有被删除的，这个过程经过路径压缩之后，每一次询问就是O(1)了。 代码 #include&l...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-13 18:57

已编辑

河南理工大学 golang

Boring Non-Palindrome 【马拉车算法】

Boring Non-Palindrome 题目链接：https://codeforces.com/gym/102307/problem/B 思路 因为只能从末尾加字符串，让其变成回文串，那么就可以找到以原字符串末尾结束的最长回文子串T(马拉车做)，然后把前面不属于T的部分命名成T2。然后输出原字符串，再反序输出T2。 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll;...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-13 17:46

河南理工大学 golang

P3805 manacher算法最长回文子串长度【马拉车算法】【模板】

P3805 manacher算法 题目地址：https://www.luogu.com.cn/problem/P3805 思路 马拉车其实就是每次算某个点的回文半径到时候，会看自身是否处在一个之前求过的回文串T中，然后根据镜面对称，O(1)获取以自己为中心在T中的最大回文子串,然后再尝试暴力，所有的更新暴力复杂度为O(n) 代码 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define debug freopen("in.txt&quot...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-12 23:31

已编辑

河南理工大学 golang

POJ-3368 Frequent values 【ST表】

Frequent values 题目链接：https://vjudge.net/problem/POJ-3368 思路 我的代码有两个预处理：第一个init: 将数组中的相等的元素，用首项是1，公差是1的等差数列表示，放在cnt[]中 然后用R[]数组，来表示某个元素所在段的下一段的起点 这个初始化，可以把我代码中的cnt[]和R[]打印出来，一看就能明白预处理init_st:就是对于cnt这个数组，求区间最大值。处理的时候，有可能L所在段是被切断的，所以第一段可能不完整，但是在一段内cnt[]是一个前缀和，所以可以通过上面R[]定位到下一段的开始，就可以用前缀和高出这一段的元素个数，然后l ...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-12 20:23

河南理工大学 golang

HDU4217 Data Structure? 【权值线段树】

Data Structure? 题目链接：https://vjudge.net/problem/HDU-4217 思路 主要就是这段话：以查询第k大为例，权值线段树的核心是到每个结点，如果右子树的权值总和大于了k，则说明其第k大值在右子树，递归进入右子树。反之则说明第k大值在左子树。 特别注意：若要进入左子树，需要k减去右子树的总和，比如要找的元素是第5大，右子树权值总和为3，则需5-3=2，说明该节点的第5大值存在于左子树的第2大值中。那么从左子树递归下去，直到递归到一个数，那就是答案了。 代码 #include<bits/stdc++.h> #define ios ios_ba...

Ryuichi的算法分享

0 点赞评论收藏

2020-04-14 12:56

已编辑

河南理工大学 golang

【19级算法训练赛第十场】题解

19级算法训练赛第十场 比赛地址：https://vjudge.net/contest/367058#overview 密码：IWantToACC内容涉及：A数学定理 B贪心入门 C枚举or数位dp D枚举or唯一分解定理 E离散化+差分 F唯一分解定理 G计算机常识+二进制 H签到 直播讲解高清录像放在B站上，点击下面链接进入 视频链接：https://www.bilibili.com/video/bv1ak4y197pm A-[NOIP2017]小凯的疑惑 #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio...

Ryuichi的算法分享

0 点赞评论收藏

关注他的用户也关注了：