- 博客(372)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #779 (Div. 2)-D2 - 388535 (Hard Version)
异或字典树的最大值Max和最小值Min,由于正确答案res^a[i]时会得到[l,r]区间，因此只要。来求得res,但直接暴力遍历会超时，可通过建立字典树，然后求。之中，那么可以通过遍历。首先答案res一定位于。...
2022-07-28 01:26:53
167
原创 LeetCode-327. 区间和的个数
同时是对于前缀和数组进行分析，对于pre[i],当j>i,pre[j]位于区间[pre[i]+lower,pre[i]+upper]之间是合法的，因此可以从左到右遍历pre，对于pre[i],查询线段树中下标pre[i]的个数,然后将区间[pre[i]+lower,pre[i]+upper]加1，需要注意将pre[i]，pre[i]+lower,pre[i]+upper哈希离散化。思路归并排序/树状数组（线段树）2.树状数组（线段树）code2.数组数组。...
2022-07-25 23:45:50
184
原创 LeedCode-862. 和至少为 K 的最短子数组
对于右边窗口，若i=pre[j]，显然可以将pre[i]从窗口中去除，利用j作为左区间显然更好。利用滑动窗口维护一个合法区间，遍历i=0->n,对于当前下标j。而对于左边窗口，pre[i]已经求得其最小区间，故可以将其从窗口去除。先求出数组前缀和，问题就转变成前缀和之差不小于k的最小区间。思路前缀和+滑动窗口。......
2022-07-20 18:53:00
124
原创 关于C++的类型转换运算符 static_cast 和 const_cast 的说明
C++ 对于const_static 和 static_cast 关于去除或添加const/volatile的理解
2022-07-07 18:09:57
696
原创 Codeforces Round #791 (Div. 2)-D. Toss a Coin to Your Graph...
传送门：https://codeforces.com/contest/1679/problem/D思路：二分可以通过二分答案si，对于judge的判断，可通过对于所有不大于si的边重新构图，然后先找图中是否有环，有则true，没有则从入度为0的点开始BFS找最长的路径即可Code:#include<iostream>#include<algorithm>#include<vector>#include<queue>using namespac.
2022-05-26 18:31:18
126
原创 Codeforces Round #783 (Div. 2)-D. Optimal Partition
传送门：https://codeforces.com/contest/1668/problem/D思路：dp+树状数组， 参考博客https://www.cnblogs.com/Prgl/p/16169339.html需要注意dp初始化时需要把0先算上去，即假设数列的左边隐含着一个为0的元素做分割线Code:#include<iostream>#include<algorithm>#include<set>#include<unordered_map.
2022-05-18 02:13:10
105
原创 Educational Codeforces Round 125 (Rated for Div. 2)-D. For Gamers. By Gamers.
地址：https://codeforces.com/contest/1657/problem/D思路：要使得单位 i {di,hi}能够战胜怪兽{Di,Hi},有 Hidi>hiDi\frac{Hi}{di}>\frac{hi}{Di}diHi>Dihi，即 hi∗di>Hi∗Dihi*di > Hi*Dihi∗di>Hi∗Di ，而x个单位i战胜怪兽而不是死掉一个单位，即 i∗hi∗di>Hi∗Dii * hi * di > Hi * Dii∗hi∗.
2022-04-15 21:57:36
202
原创 LeetCode-1825. 求出 MK 平均值
地址：https://leetcode-cn.com/problems/finding-mk-average/思路：https://leetcode-cn.com/problems/finding-mk-average/solution/c-san-ge-multiset-jian-dan-mo-ni-by-newh-y4q9/维护 3 个 multiset：lower（保存最小的 k 个数）、middle（中间的数）、upper（保存最大的 k 个数）。插入操作如果 num≤max(lowe.
2021-04-16 02:58:12
304
转载 CentOs7安装apache以及遇到的问题
转载与https://blog.51cto.com/9083918/2159995新手在CentOs7装一个Apache时，可以参考本文1.下载httpd源码包 [root@localhost utils]# mkdir /usr/local/utils [root@localhost utils]# cd /usr/local/utils [root@localhost utils]# wget http://mirrors.hust.edu.cn/apache/httpd/ht
2021-01-14 00:35:41
450
原创 LeetCode-32. 最长有效括号
地址：https://leetcode-cn.com/problems/longest-valid-parentheses/思路：利用栈记录入栈字符的下标位置，从头处理字符串，对于s[i]，若栈头元素与其匹配，则将其从退栈，并求其长度并保存最大长度，若不匹配则入栈。Code:class Solution{public: int longestValidParentheses(string s){ stack<int> sta; int res=0; for(int i=0.
2021-01-06 20:32:36
117
原创 最小生成树-Kruskal算法模板
最小生成树-Kruskal算法：时间复杂度 O(mlogm) ,m为边数模板题：P3366 【模板】最小生成树Code:#include<iostream>#include<algorithm>using namespace std;struct node{ int u,v,w; bool operator<(const node &A)const{ return w<A.w; }};const int MAX_N=5e3+5;con
2020-12-23 23:40:40
125
原创 最小生成树-Prim算法模板
最小生成树-Prim算法：未优化：时间复杂度 O(n^2),n为顶点数堆优化：时间复杂度大概为 O((n+m)logm),m为边数模板题：P3366 【模板】最小生成树Code 未优化:#include<iostream>#include<vector>using namespace std;typedef pair<int,int> pr; const int MAX_N=5e3+5;const int INF=1e9+5;int n,m;ve
2020-12-23 23:38:32
119
原创 最短路-Dijkstra算法模板
最短路-Dijkstra算法不能处理负权边未优化：时间复杂度为O(n^2) ,n为顶点数堆优化：时间复杂度大概为O((m+n)logm)，m为边数模板题（未优化）：P3371 【模板】单源最短路径（弱化版）模板题（堆优化）：P4779 【模板】单源最短路径（标准版）Code 未优化：#include<iostream>#include<vector>using namespace std;struct node{ int v; int w;};const
2020-12-23 23:25:46
247
原创 数据结构-平衡二叉树（C++代码实现）
数据结构中平衡二叉树的C++代码实现有关参考博客：https://blog.csdn.net/qq_25940921/article/details/82183093https://www.cnblogs.com/zhangbaochong/p/5164994.html代码及其测试结果如下Code :/*二叉平衡搜索树(AVL):对于二叉搜索树的所有结点，其左右节点的高度之差不超过 1 */ #include<iostream>#include<queue>usi
2020-12-23 00:39:17
3060
2
原创 数据结构-二叉排序树（C++代码实现）
数据结构中二叉排序树的C++代码实现有关参考博客：https://blog.csdn.net/kang___xi/article/details/80392565Code :/*二叉排序树（二叉搜索树）：树上所有结点的左子树的值均小于该节点的值，右子树的值均大于该节点的值https://blog.csdn.net/kang___xi/article/details/80392565*/ #include<iostream>#include<queue>using n
2020-12-23 00:33:43
3202
原创 LeetCode-102. 二叉树的层序遍历
地址：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/思路：BFS/DFS思路一、BFS：利用广度优先搜索逐层搜索，每次搜索一层，将下一层的加入队列中即可思路二、DFS：利用深度优先搜索，则为从左向右搜索，对于层数可用变量进行记录即可Code BFS:class Solution { vector<vector<int>> res; queue<TreeNode *.
2020-12-18 14:23:26
94
原创 HDU-4192-Guess the Numbers
地址：http://acm.hdu.edu.cn/showproblem.php?pid=4192思路：首先将中缀表达式转为后缀表达式，然后将数组全排列取计算每一个排列的后缀表达式的值即可Code：#include<iostream>#include<algorithm>#include<stack>using namespace std;int n;int d[55];stack<string> sta;string transfo.
2020-12-18 12:53:40
211
2
原创 LeetCode-714.买卖股票的最佳时机含手续费
地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/思路：贪心 || DP思路一、贪心：利用贪心思路，当出现峰值（买卖间有正差值）时即将股票卖掉，同时寻找下一个峰值。对于卖出时需要手续费fee,其峰值相当于卖出价格prices[i]-fee,记录当前最小值Min,当prices[i]-fee>Min时，则答案加上其差值res+=prices[i]-fee-Min;同时令 .
2020-12-04 00:43:35
116
原创 牛客-50998.括号画家（栈）
地址：https://ac.nowcoder.com/acm/problem/50998思路：利用栈记录入栈的字符与其下标位置，从头处理字符串，对于str[i]，若栈头元素与其匹配，则将其从退栈，并求其长度并保存最大长度，若不匹配则入栈。Code:#include<iostream>#include<stack>#include<map>using namespace std;typedef pair<char,int> pr;int ma.
2020-12-02 00:48:08
220
原创 牛客-50963.Editor(栈)
地址：https://ac.nowcoder.com/acm/problem/50963思路：利用两个栈来分别存储下标前和下标后的元素，同时记录下标前的元素其前缀和以及答案即可。Code:#include<iostream>using namespace std;const int MAX_N=1e6+5;int Q,sl,sr;int dl[MAX_N],dr[MAX_N];int Sum[MAX_N],res[MAX_N];int main(){ ios::syn.
2020-11-29 23:44:52
128
原创 HDU-1506.Largest Rectangle in a Histogram
地址：http://acm.hdu.edu.cn/showproblem.php?pid=1506思路：并查集 || 单调栈思路一、并查集：首先对数组以b[]={值，下标}结构按照从小到大排序，然后从大的开始处理，对于b[i]={val,id}, 比较其id位置左右相邻的值是否大于等于val,若大于等于则将其合并成一个集合，同时记录其集合中元素的个数s，那么当前元素的最大值为 val*s，res取所有元素的最大值即可。思路二、单调栈：遍历数组，维护单调递增栈，对于当前元素x，其左边元素x0，当x0&.
2020-11-28 20:55:40
121
原创 LeetCode-239. 滑动窗口最大值
地址：https://leetcode-cn.com/problems/sliding-window-maximum/思路：优先队列 || 单调队列 || dp思路一、优先队列：利用优先队列维护区间的最大值，同时将记录其下标 <val,id>. 遍历数组nums[i]，将优先队列首节点不在k范围内的去除掉，在取首节点即可。时间复杂度O(nlogn)思路二、单调队列：利用双端队列来维护一个单调递减队列，从队列尾部加入值，队列头部取最大值和去除非法数据。遍历数组，从双端队列末尾加入值num.
2020-11-27 09:47:28
117
原创 HDU-1007.Quoit Design
地址：http://acm.hdu.edu.cn/showproblem.php?pid=1007思路：最近点对+分治对于点集a[n]先按x坐标从小到大排序，取中点a[n/2]将其分成左右两边进行分治，那么最近点对分为三种情况：1.最近点对都在左边 resL；2.最近点对都在右边 resR；3.最近点对一个在左边，一个在右边 resH。那么答案res为三种情况中的最小值，前两种情况按照分治思想可以处理，主要是第三种情况的处理。首先分治求出 res=min(resL,resR)，对于resH，.
2020-11-26 15:43:47
101
原创 LeetCode-138. 复制带随机指针的链表
地址：https://leetcode-cn.com/problems/copy-list-with-random-pointer/思路：map || 思维思路一、map：对于原链表head以及复制链表hd,可以用map[head]=hd进行一一对应，这样在处理随机random指针时，直接用map对应到相应复制链表即可。思路二、思维：对于复制链表来说随机指针由于找不到对于位置关系不好处理，因此可以将复制链表的节点插入到原链表对应节点后面，例如p1->pp1->p2->pp2->.
2020-11-26 00:27:11
107
原创 LeetCode-206. 反转链表
地址：https://leetcode-cn.com/problems/reverse-linked-list/思路：双指针 || 递归一、双指针：从链表头结点p=head开始反转，需要先保存pi=p->next，再将p->next指向p本身，同时记录已反转链表的头结点head=p（而初始头结点为NULL），然后遍历到下一个节点即可二、递归：思路相同，递归到下一节点，在将当前节点与其下一节点指针反转head->next->next=head,然后令head=NULL(使反转后.
2020-11-22 22:39:01
116
原创 LeetCode-337. 打家劫舍 III
地址：https://leetcode-cn.com/problems/house-robber-iii/198.打家劫舍地址： https://leetcode-cn.com/problems/house-robber/思路：树状dp对于根节点为 rt 的子树，dp[rt][k]为其根节点取和不取(k=0/1)时子树的最大价值,ld,rd分别为其左右节点，那么dp[rt][0]=max(dp[ld][0],dp[ld][1])+max(dp[rd][0],dp[rd][1]);dp[rt][1.
2020-11-21 18:07:08
93
原创 LeetCode-31.下一个排列
地址：https://leetcode-cn.com/problems/next-permutation/思路：通过模拟s[1,5,8,6,4,2]的下一个排列，n为其排列长度1.首先是从末尾向前找首个 r 使 s[r]>s[r-1],翻转s[r,n-1];即s[r]=s[1]=5,因为对于[8,6,4,2]已经是最大的排列了，因此需要将其转到最小的排列。2.在s[r,n-1]找首个 i 使 s[i]>s[r-1],交换s[i],s[r-1];在第一步时s[r,n-1]翻转变成了[2.
2020-11-20 11:30:57
86
原创 LeetCode-51. N 皇后
地址：https://leetcode-cn.com/problems/n-queens/思路：DFS+剪枝利用boo[x][y]判断（x,y）是否为皇后在DFS搜索第k层时，若boo[k][i]为0，将其即为皇后，同时将其本身和其列与斜线b[][]+=1即可Code:class Solution { vector<string> iv; vector<vector<string>> res; vector<vector<int>>.
2020-11-19 20:38:35
85
原创 LeetCode-95. 不同的二叉搜索树 II
地址：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/思路：DFSf(i): 以 i 为根的二叉搜索树个数s(n): n个节点的二叉搜索树个数s(n)=f(1) + f(2) + … + f(n)f(i) = s(i-1)*s(n-i)则s(n) = s(0)*s(n-1) + s(1)*s(n-2) + … + s(n-1)*s(0);通过s(n)以 i 为根进行构造Code:class Solution {.
2020-11-19 11:41:12
137
原创 LeetCode-96. 不同的二叉搜索树
地址：https://leetcode-cn.com/problems/unique-binary-search-trees/思路：一：dpf(i): 以 i 为根的二叉搜索树个数s(n): n个节点的二叉搜索树个数s(n)=f(1) + f(2) + … + f(n)f(i) = s(i-1)*s(n-i)则s(n) = s(0)*s(n-1) + s(1)*s(n-2) + … + s(n-1)*s(0);二：卡特兰数s(n) = s(0)s(n-1) + s(1)s(n-2) + .
2020-11-19 10:51:31
94
原创 LeetCode-754.到达终点数字
地址：https://leetcode-cn.com/problems/reach-a-number/思路：首先对于target,其正负结果是一样的，其负值就相当于正值走的路径方向相反，因此对其考虑正值设最少走 n 步，那么首先 s=n∗(n+1)2⩾targets = \frac{n*(n+1)}{2} \geqslant targets=2n∗(n+1)⩾target.则 n=sqrt(2*target);若 s = target.则 res=n;若 s < target.则 ++.
2020-11-18 23:30:34
153
原创 LeetCode-946. 验证栈序列
地址：https://leetcode-cn.com/problems/validate-stack-sequences/思路：用栈模拟其出栈序列popped[],遍历pushed[l],popped[l1],将pushed[l]压入栈sta,随后比较头结点sta.top()是否与popped[l1]相等，相等则一直将其出栈直到不相等，若pushed[]全部入栈sta后sta.top()与popped[l1]不相等则其不合法。Code:#include<iostream>#i..
2020-11-18 02:17:32
148
原创 Codeforces Round #668 (Div. 2)-C. Balanced Bitstring
地址：http://codeforces.com/contest/1405/problem/C思路：参考博客：https://blog.csdn.net/hzf0701/article/details/108439484对于子串a[0,k-1],a[1,k],两者满足条件，则必须满足a[0]=a[k],而对于相邻子串a[x,x+k-1],a[x+1,x+k]则必须满足 a[x]==a[x+k],因此对于所有子串有满足a[x%k]=a[x],且第一个子串a[0,k-1]合法即可Code:#..
2020-11-11 00:50:37
110
原创 2020ICPC·小米 网络选拔赛热身赛-A.ABBA
地址：https://ac.nowcoder.com/acm/contest/8409/A思路：动态规划或组合数学思路一，动态规划：思路二，组合数学：
2020-10-25 16:27:28
730
原创 ZOJ-What day is that day?
地址：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827369770思路：费马小定理，a^b%7,对于a可以a%7，因此a可化为只在 0-6之间，而对于b,根据费马小定理 a^6%7=1，因此 b可化为只在 0-5之间，因此对于所有的a^b就只有 7*6种情况，因此计算a^b所有情况的个数即可Code:#include<iostream>using namespace std;int n,T;str..
2020-10-13 01:25:32
160
1
原创 ZOJ-Problem Arrangement
地址：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827369762思路：二分搜索，对于n行，可从中分开，分别搜索前n/2行和后n/2行，记录其的值以及搜过的点，在对两边结果排序比较即可Code:#include<iostream>#include<algorithm>#include<vector>using namespace std;typedef long long ..
2020-10-13 00:21:09
135
原创 LeetCode-968.监控二叉树
地址：https://leetcode-cn.com/problems/binary-tree-cameras/思路：贪心/树状dp1.贪心：对于树来说，监控父节点一定不监控子节点覆盖的点多，因此只要从叶子节点处贪心，同时记录当前节点的状态即可，节点的有三种状态：0-节点未被覆盖、1-节点被覆盖但不是监控点、2-节点为覆盖点2.树状dp:节点同样是这三种状态，dp[i][j]为子树 i 为 j 状态时被覆盖所需要监控节点的最小数量再对父节点的左右节点是否存在分类讨论即可Code 1:..
2020-09-22 12:28:18
320
原创 LeetCode-105. 从前序与中序遍历序列构造二叉树
地址：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/思路：通过对先序遍历和中序遍历的遍历顺序分析，对于先序遍历，第一个节点一定是根节点，再定位到中序遍历中当前根节点的位置，可以将先序遍历拆分成两个子树的先序遍历，这样就可以利用递归将遍历集合一步步缩小，从而得到二叉树。Code:/** * Definition for a binary tree node..
2020-09-22 12:04:12
84
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人