- 博客(49)
- 收藏
- 关注
RSS订阅原创 单调栈简单题目整理
最大矩阵类问题1.求最大矩阵题目链接题目：直方图中的最大矩阵#include<bits/stdc++.h>#define pb push_back#define fi first#define se second#define ALL(a) a.begin(), a.end()#define SZ(a) (int)a.size()#define db1(x) cout<<#x<<" = "<<x<<endl#define db
2020-10-24 10:40:51
170
1
原创 线段树回顾
一、单点更新1.hdu1166 敌兵布阵单点增减，区间求和#include<stdlib.h>#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>#include<ctype.h>#include<iostream&...
2020-10-14 11:03:29
1129
原创 Codeforces Round #661 (Div. 3) E1 Weights Division (easy version)
我是真的sb，一开始就想到了怎么写，结果T了一个小时，我是本来我想的优先队列是比较减掉的值，结果必成加上的值，一直都以为我写的很对，少了两个+1 。提醒自己，真的菜！！！题意：一棵以1为跟的树，现在想要把这棵的树的所有叶子节点到根的路径和变成<=S。可以对边的权值进行操作，每一次操作都会试边权值/2(向下取整)，程序中直接除以2就可。思路：如果随便画一个图，不难发现每一条边都有一个使用次数(就是在求叶子节点到根的路径的贡献)，我们只需要贪心每一次找出操作之后减少的值最大的一条边，这里用优先队列维
2020-08-06 01:29:19
139
原创 字符串专题
字符串简介kmp算法，扩展kmp，manacherkmp算法视频讲解Next数组视频讲解manacher视频讲解kmp扩展kmpmanacher提供一种我认为比较好用的模板//求解原串中包含多少模式串，模式串可以互相覆盖，不能覆盖的稍微修改一下即可char ori[N*100], pat[N];//ori为原串，pat为模式串int Next[N];void get_next(char *pat){ int i = 0, j = -1; Next[0] = -1;
2020-08-02 20:15:28
943
3
原创 并查集&最小生成树专题
并查集：朴素并查集和带权并查集并查集介绍视频讲解难点：路径压缩和启发式合并的理解常用模板：(1)朴素并查集： int p[N]; //存储每个点的祖宗节点 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // 初始化，假定节点编号是1~n for (int i = 1; i <= n; i
2020-07-26 19:13:39
228
原创 codeforces1373E Sum of Digits
拖了很久才补的题，很巧妙的一道构造。最优情况是类似x999c， c是个位，x不一定只是一位数。然后我们就进行枚举c和9的个数，注意在计算和的时候我们先不考虑x，因为最优情况x的末尾不是9，所以x在进位时，x并不会变化，也就是说剩余的价值一定得是x*(k+1)。此时我们得到一个x, 然后再对x进行构造获得最小的x。x的结构一定是b999d，为了让x最小且符合最优情况d要尽可能大但又要小于9，也就是说如果剩下的价值可以让d等于8，d就是8，然后前面尽量排9，剩下的一位就是b了。#include<cs
2020-07-09 15:43:19
167
原创 acwing102. 最佳牛围栏
传送门二分答案，check函数主要方法就是，把所有的a[i]先减去x，如果区间和是大于等于0的，也就是说这个区间的平均数大于x，从f开始，记录前面的最小值，然后查看是否存在答案。#include<bits/stdc++.h>using namespace std;typedef long long ll;#define eps 1e-8const int N = 1e5+10;int n, m;double a[N], g[N];bool check(double x){
2020-07-08 21:27:25
187
原创 codeblosk中文注释乱码和一些头文件的不能使用的问题解决方法(error: failure to convert GBK to UTF-8|)
主页面点击右上角settings->compiler然后点击下图箭头最后按照下图更改编码格式即可。-finput-charset=UTF-8-fexec-charset=GBK
2020-07-07 23:23:32
1244
原创 acwing 97. 约数之和
传送门以下定理参考博客#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 9901;ll a, b;ll ksm(ll x, ll y){ ll ans = 1; x%=mod; while(y) { if(y&1) ans = (ans*x)%mod; x = (x*x)%mod;
2020-07-03 16:13:20
204
原创 acwing 95. 费解的开关
传送门枚举第一行的状态，然后向下进行递推，假设我们枚举的每个答案都是正确的，那就不可能从第一行进行翻转，此时如果第一行还有0那么就必须是第二行对应位置进行翻转，然后就依次向下进行递推。还有一种写法是从全1的情况逆向翻转找到所有合法情况进行hash，本题数据小也能过。#include<bits/stdc++.h>using namespace std;char mp[10][10], g[10][10];int n = 5;int dx[4] = {1, 0, -1, 0}, d
2020-07-02 19:06:29
113
原创 acwing 291. 蒙德里安的梦想
状压dp板题#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N =12, M = 1<<12;ll f[N][M]; ///代表前i-1列都被填满，j代表第i列的状态bool st[M]; ///预处理每一种状态是否合法int n, m;int main(){ while(scanf("%d%d", &n, &m)&&(
2020-06-23 22:26:23
257
原创 acwing 91. 最短Hamilton路径(哈密尔顿)
传送门状压dp#include<bits/stdc++.h>using namespace std;const int N =20, M = 1<<20;int f[M][N], d[N][N], n;///f[i][j]代表经过状态i，终点在j的点，i代表状态，转成二进制就代表经过那些点int main(){ scanf("%d", &n); for(int i = 0; i < n; ++i) for(int j = 0;
2020-06-23 00:18:45
179
1
原创 acwing 784. 强盗团伙
传送门经典并查集问题#include<bits/stdc++.h>using namespace std;const int N = 1010;int n, m;vector<int> e[N]; ///记录敌人int f[N];int Find(int x){ return f[x] = (x==f[x])?x:Find(f[x]);}void merge(int x, int y){ x = Find(x), y = Find(y);
2020-06-22 23:50:45
148
原创 acwing 238. 银河英雄传说
传送门带边权的并查集#include<bits/stdc++.h>using namespace std;const int N = 1e6+10;int f[N], num[N], d[N];///d[i]表示i到祖宗的距离，num[i]表示以i为祖宗的队列的长度,是否清零都可以,因为合并后就用不到了int Find(int x){ if(x == f[x]) return x; int root = Find(f[x]); d[x] += d[f
2020-06-22 23:49:31
143
原创 zzuli 2631: B(树链剖分)
传送门题目描述小p很早就听说，在古老的埃及，想要从斯芬克斯守护的地方经过，需要回答对它的一个问题。小p自命不凡，来到了斯芬克斯面前。斯芬克斯每天都望向远处（很远很远）的森林，看着一棵树，树上时不时会有一些小鸟落下，它每天的乐趣就是，当树上的小鸟的数量变化的时候，统计现在树上从一个树叶到另一个树叶上有多少个小鸟，它费尽心思没有搞懂，恰好小p来了，于是它将问题丢给小p，并说到：“我每天望向对面的森林，每天凌晨的时候，树上没有一只小鸟，每当有小鸟来的时候，我就记录 2 x y z，表示这个时候，从x号树叶到y
2020-06-17 17:02:04
175
1
原创 树链剖分板题acwing 917. 树上操作
传送门某大佬有趣的视频讲解大佬博客#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#include<queue>#include<math.h>#i
2020-06-17 16:54:50
144
原创 acwing 18. 重建二叉树
经典题目/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: map<int, int> hash;
2020-06-15 22:24:09
114
原创 AcWing 12. 背包问题求具体方案
传送门#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#include<queue>#include<math.h>#include<climit
2020-06-13 22:09:10
132
原创 AcWing 11. 背包问题求方案数
题意：有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。第 ii 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出 最优选法的方案数。注意答案可能很大，请输出答案模 1e9+7 的结果。f[j] 表示背包容积”恰好”为j时的最大价值和 ———— 最优解dpg[j] 表示背包容积”恰好”为j时取最优解的方案数 ———— 方案数dp#include<cstdio>#include<stdlib.h
2020-06-13 20:57:01
220
原创 牛客练习赛65(C)
传送门这是用的是一个记录斜率的方法，基本有斜率都是通分，毕竟浮点数会有误差。这个题很容易发现只有0，1,2,3,-1这几种答案，-1就是所有点都在同一直线且没有点与当前点的斜率相同， 0就是在原点，特判一下，3就是n为2, 然后四个点组成平行四边形。1的话就是x, y和其中的一个点的斜率相同(这里的斜率指的是点与原点之间的斜率)，2的话就是其他情况都考虑完就剩2了。比赛时写的太乱，分的情况太杂，最后也是没过。还有些大佬用的是奇角排序加二分判断斜率相同，不过总体思路都相同。大佬的题解#include
2020-06-12 23:36:40
158
原创 AcWing 178. 第K短路
传送门第k短路的裸题，第k短路涉及到A算法。遇到问题我们先思考暴力的解法，这道题暴力的解法就是把其放到队列里，并查看点的出队次数，出队次数就代表了从起始点到当前点的第出队次短路。然后就是用A算法进行优化，主要就是利用一个估价函数，估价函数要求估计值一定是小于等于真实值，这个真实值就是从当前点到终点的权值。估价函数求法是反向建边，求终点到其他点的最短路。注意一下，题目要求至少包含一条边，也就是说如果起点和终点相同，就是求第k+1条路，第1条为0的路就不算是最短路。#include<cstdio
2020-06-11 22:02:42
108
原创 洛谷 P4568 [JLOI2011]飞行路线(分层图最短路)
很容易理解的一个算法，只要把图画出来看看就行，感觉也很实用。#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#include<queue>#include<ma
2020-06-10 23:18:56
157
原创 zzulioj 2634: E（spfa限制边权+二分）
这道题是对这个全局最优的边权进行二分，我们知道这条路上的其他边的容量肯定都大于等于这个值。所以，就可以根据这个来限制当前的图，然后再判断当前图的可行性进行二分。#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include&
2020-06-10 22:17:57
134
原创 zzulioj 2636: G（二分图）
传送门经典二分图，经常用于解决这种覆盖问题。原理是把二维变成一维，把相邻的块当成边，然后进行二分图求最大匹配，单向边就可以。#include<cstdio>#include<stdlib.h>#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<map>#include<vector>#in
2020-06-10 22:12:15
119
原创 pta 郑州轻工业大学2020年数据结构练习集
6-1 顺序表操作集/*#include <stdio.h>#include <stdlib.h>#define MAXSIZE 5#define ERROR -1//typedef enum {false, true} bool;typedef int ElementType;typedef int Position;typedef struct LNo...
2020-02-26 15:02:21
4337
12
原创 HDU - 618（暴搜+递推+矩阵快速幂）
一种找规律的方法，先暴搜找出前几个值，再多次循环找表达式系数，流批https://www.cnblogs.com/yzm10/p/9313916.html//#pragma comment(linker, "/STACK:10240000000000,10240000000000")#include<bits/stdc++.h>#define debug(x) cout &l...
2020-02-08 14:49:36
153
原创 Codeforces Round #616 (Div. 2)
A - Even But Not EvenB - Array SharpeningC - Mind ControlA - Even But Not Even题意：给长度为n的一个数字串，求其子串符合子串每个数字和为偶数但子串是奇数。答案不唯一思路：其实根本不用考虑偶数，符合条件的串一定是奇数为偶数个数，且最后一位是奇数。由于答案不唯一，我们只考虑一种情况，有两个奇数的子串。只要够两个奇...
2020-02-03 17:42:25
171
原创 Codeforces Round #615 (Div. 3)
传送门A Collecting CoinsB Collecting PackagesC Product of Three NumbersD MEX maximizingA Collecting Coins题意：有3孩子，分別有a,b,c个糖果，现有n个糖果给他们，最后能否让三个人拥有的糖果数量相同。思路：找出糖果最多的孩子，先让三个孩子的糖果数量都等于最多的那个，然后看是否能平分剩...
2020-01-23 23:24:46
725
3
原创 HDU1274
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1274参考博客：https://mp.weixin.qq.com/s?__biz=MzUzMjU2NjYxMA==&mid=2247483728&idx=1&sn=85f272a7a184168595365c409832b90d&scene=21#wechat_redire...
2020-01-22 15:00:20
165
原创 HDU 2222(ac自动机)
ac自动机参考博客：https://blog.csdn.net/bestsort/article/details/82947639#include<queue>#include<cstdlib>#include<cmath>#include<cstdio>#include<string>#include<cstring...
2020-01-21 20:49:18
162
原创 Codeforces Round #614 (Div. 2)
传送门A ConneR and the A.R.C. Markland-NB JOE is on TV!C NEKO’s Maze GameD Aroma’s Search A ConneR and the A.R.C. Markland-N题意：有n层楼，每层都有饭店，一个住在s层的人想要吃饭，但是有k家饭店已经关门，告诉你是那k家。问离s层最近的还在营业的有多远(原题是要走多少楼...
2020-01-21 17:30:46
1540
原创 Codeforces Round #613 (Div. 2)
日常掉分，还是不够细心，第二题的全零数据直接把我干掉QAQ感觉自己比赛时写的代码太乱了，赛后还是得想想怎么写更短小精悍。A - Mezo Playing ZomaB - Just Eat It! C - Fadi and LCMD Dr. Evil UnderscoresE Delete a Segment ## A - Mezo Playing Zoma### 题意：给出长...
2020-01-12 16:16:29
189
原创 无法打开jar文件
首先要安装jdk，有java基本都行。我也有，但是由于我自己安装了两个版本的，我把前一个删了，但是注册表里的还是前一个的路径。windows+R打开regedit注册表。找到下图路径右键模仿上图格式修改一下路径，没有就改一改"E:\jdk\Java\jdk-11.0.2\bin\javaw.exe" -jar "%1" ...
2019-12-18 23:45:33
1396
原创 Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)
这里写自定义目录标题A Happy Birthday, Polycarp!暴力模拟B Make Them Odd题意：一次操作可把数组里一个是二的倍数的数全部(相同的)除以二，求最小操作次数题解：set他不香吗？，从最大的开始，是偶数就是除二插入set中，无论是奇偶都要删除。这样不用考虑大的变成小的，set直接就操作了。auto是万能变量，好像只有c++11以上才能用，不能用的就手写迭代器即可。C...
2019-12-17 16:35:06
237
原创 最小生成树(kruskal和prim)
两者区别：Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。两者其实都是运用贪心的思路prim#include<bits/stdc++.h>#define debug(x, y) cout << x<<" "<<y<<endl#define ...
2019-11-27 16:24:20
113
原创 约瑟夫问题(最快的对数算法模板)
递归写法：推荐博客·https://blog.csdn.net/yanweibujian/article/details/50876631
2019-11-23 14:44:47
379
原创 Codeforces Round #600 (Div. 2)
A - Single Push题意：没错这就是个线段树,a了他。。。找一个区间增加一个值，这个值>=0，只能操作一次。问能否把数组a变成b。题解：找出不相同的a和b的最大范围，看是否差值相同#pragma comment(linker, "/STACK:10240000000000,10240000000000")#include <bits/stdc++.h>usin...
2019-11-17 19:34:08
87
原创 Educational Codeforces Round 76 (Rated for Div. 2)
A - Two Rival Students水题#include<bits/stdc++.h> using namespace std;typedef long long ll;#define debug(x, y) cout <<x<<" "<<y<<endl#define pii pair<int, int>...
2019-11-15 15:03:46
102
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人