- 博客(103)
- 收藏
- 关注
RSS订阅原创 ros、marros安装和验证（亲测非常有效）
ros安装看这篇（脚本是真的牛逼）这边需要注意的是4.(2)部分~验证看这篇px4部分（4-7）marros安装看这篇。
2023-04-14 22:30:39
120
原创 进阶指南----最大子序列
暴力思想就是求前缀和，然后从左到右枚举终点，暴力得以每个点为终点的前m个数的和的最大值优化第二步，从左到右是有顺序的，我们可以考虑维护一个队列，每次将一个点的前缀和扔进去，到某个点时，看看前面m个里的最小前缀和即可，而当我们扔数的时候，又发现，扔一个数进去，如果它比队列里面的一些数大，则前面那些比它大的数则永远不可能再用到，所以可以把比它大的数扔出去，而这个样子，就成了一个单调队列，那么前面m个的最小前缀和是哪个？队头！就变成O(n)了#include <bits/stdc++.h>usi
2020-12-19 11:05:53
90
1
原创 进阶指南-----小猫爬山
dfs基础题枚举所有的情况：对于一只猫，有两种情况，一个是放在现有的缆车，但不能超重，一个是自己再重新上一辆缆车对于剪枝：什么情况不会继续呢？最容易想到的就是现在用的车车已经比曾经试过的多了，然后这个能不能再快一点？我们用了一个方法，优先枚举离根近的分枝少的，那咋整勒？越胖的猫！每辆缆车都不行枝不就少了？代码如下#include <bits/stdc++.h>using namespace std;int ans = 1000;int cat[25],sum[25],n,w;//c
2020-12-16 21:33:27
121
原创 进阶指南---小组队列
很朴素的想法就是开个数组，如何疯狂判断这组有没有，有的话插入，没有在后面插入，显然复杂度有点高那如果把其的总队列与分队列分开，则上面插入加复杂度的问题就解决咯，就四种情况：插入如果原来有，则直接在分队列插入该数否则，则再在队列末插入该数所在的队列删除直接得总队列的第一个队列是谁，直接删分队列中第一个数如果分队列中的该队列的数被删完了，则在总队列将该队列删去#include <bits/stdc++.h>using namespace std;const int MA = 1
2020-12-15 11:15:06
113
原创 进阶指南-----直方图中最大的矩形
最朴素的想法就是分别以每一个为高，分别找出左边和右边 >= 其的最大长度那另一种想法从左到右一个个入栈，那么对于前面入栈的小矩形，则需要保证后面来的比他大，其长度才能快乐地延伸下去，比它小了，也就说明了，前面那个在栈里大的那位，延伸不下去了，也就只好统计出来咯，但因为其对前面的还有用，所以切到比准备进来那个高的部分，继续进去栈当个打工人，就O(n)咯#include <bits/stdc++.h>using namespace std;const int MA = 1e5+10
2020-12-14 21:38:26
83
原创 进阶指南---火车出栈
只要前20个，且要字典序，那不就暴力dfs字典序无非就决定了其出栈的顺序，那想想看一个数进栈之后是要等下一个数进来，下一个数先出还是自己先出呢，自己是1，下一个是2，肯定自己小先出才能保证字典序小咯，所以字典序小就是栈里有数先出就欧克啦代码如下：#include <bits/stdc++.h>using namespace std;int cnt = 20,n;int state3;//未入栈的 stack<int> state2;//栈中的 vector<in
2020-12-12 15:08:58
135
原创 进阶指南---编辑器
在对于栈的使用上，我们可以根据题目的喜好而加入一些其他栈，例如经常左右移动，加入对顶栈，对于前缀和的最大值保存查询，可加入最大栈和总和栈，这题就是对这些栈的小运用#include <bits/stdc++.h>using namespace std;const int MA = 1e6+10;//tl目前到的位置没有操作 int stl[MA],str[MA],tl,tr;//左栈右栈int sum[MA],f[MA];//总和与最大值 void worfs(int k) //对最大
2020-12-09 21:39:32
69
原创 八数码poj1077----只能过poj
战术挂机，后面再重写#include <cstdio>#include <algorithm>#include <queue> #include <map> #include <iostream>using namespace std;int en[]={1,2,3,4,5,6,7,8,0};int EN = 123456780;const int MA = 1e6;int dis[5][2]={{0,0},{-1,0},{1,
2020-12-08 20:59:21
73
原创 进阶指南--国王游戏
1、比较相邻两个大臣，要他们二者的顺序下的最大值最小，则推公式可得，谁的左手右手乘积越小在前，则二者的最大值最小所以即对大臣们进行乘积从小到大排即可2、处理过程中的高精度，需要注意除法需要消去前导0#include <bits/stdc++.h>using namespace std;const int MA = 1010;pair<int,int> PDD[MA];//对每位大臣的金币的乘积进行排序 vector <int> AA;//表示前面的和 ve
2020-11-11 21:19:55
269
原创 进阶指南----雷达监测
每个区间至少包含一个点，问最少需要多少个点：按右端点升序排列即可将每个岛屿转化为区间，即这个岛能被哪个区间的雷达扫描到，可得区间为 （x - sqrt (R * R - y * y ) , x + sqrt (R * R - y * y )） 问题等价完成两个端点，对其中一个进行升序排列，可用 pair ,其 pair.first 在 sort 时对其升序排序！！！！因为其为浮点数受其精度的影响，所以要 + 1e-6 来消除浮点误差#include <bits/stdc++.h>
2020-11-10 21:51:58
148
原创 进阶指南---畜栏预定
遇到一段区间，求最大不重合子序列,只需左顶点从小到大排列即可因为后面还需要每头牛的编号，所以说明牛的区间排列之后还要还原，所以引入b记录牛刚开始的位置方便还原如果发现已经有的畜栏最小右边 >= 准备进来牛的左边，则再开一组畜栏,畜栏需要右边和该位置的组数，所以要用结构体，记得重载 < 运算符代码如下：#include <bits/stdc++.h>using namespace std;const int MA = 5e4 + 10;struct stu{ int
2020-11-10 17:56:46
112
原创 进阶指南--天才ACM
先是校验值，显然对于集合中要M对(数差的平方) 的和MAX，可知每次选先排序，然后选最大和最小，次大和次小…即可 而又给了个T，问咋样能使每组的校验值最大不超过T,最少能分几组，可得目标为每组的校验值尽量大 因为数差的平方的和为单调递增，所以我们可以采用二分枚举r的位置，但因为二分具有不稳定性，极限情况会超时，所以采用倍增 同理，在进行排序的时候，因为快排不稳定，所以利用倍增时我们已经把(l,r) 排完序，这时只需要对（r+1,r+len）快排，再进行归并排序，可以降低复杂度#i
2020-11-02 17:00:30
105
原创 奇数码---结论题（逆序对）
通过诸多伟大的数学家证明，如果要判断奇数码是否能从一个状态走到另一个状态，只需要判断两个状态的逆序对的 奇偶性是否一样即可即从左到右从上到下的顺序搞成一维（0直接删掉），然后判断二者逆序对的奇偶性是否一致，结束。#include <bits/stdc++.h>using namespace std;const int MA = 3e5+10;int b[MA],a[MA],c[MA];//ab存两个状态，c逆序对辅助数组 void merge(int a[],int l,int r,
2020-10-21 21:01:03
167
原创 进阶指南--超快速排序（归并+逆序对）
归并排序： 将数组切成两半，然后左边排完 右边排完 （二分递归） 合并排列（用临时数组：对左右两边的数谁大谁进去）逆序对对于i,j (i < j ) 如果 a[i] < a[j] 则构成一个逆序对那思考：归并排序 你知道左边一个单调递增数列，右边一个单调递增数列,mid是左右分界，属于左边，那对于右边的数 a[j] 而言，在合并的时候，如果发现自己小于前面的一个数 a[i] 进了数组， 那说明 a[i]~a[mid] 都比a[j] 大，构成了(mid-i+1) 个逆序对这
2020-10-17 21:18:16
232
原创 最简快排模板+第k大数
快排这个快排模板，还是记住吧。。。边界太复杂了，搞不懂搞不懂它的思路和普通快排不是很一样：普通快排的思想从任选一个数，正常选中间，然后在数组中找到这个数的位置，选定，继续把这个数的左边和右边继续递归搞完这个快排就其实思路也差不多，它把小于等于X的搞在左边，大于等于X的搞在右边，然后继续递归，就排完了，，，代码简单嘿嘿#include <bits/stdc++.h>using namespace std;const int MA = 1e6+10;int a[MA];void q
2020-10-10 23:02:38
101
原创 c++读文件，造数据
读文件 freopen("3.in","r",stdin); //读入，在你的代码的文件夹里需要有这个东西 3.in freopen("3.out","w",stdout);//输出，输出怎样的格式看你自己，也可3.txt，如果你的文件夹有这个3.out直接读到里面，如果没有它给你创一个 造数据#include <bits/stdc++.h>using namespace std; char str[100];int main(){ std::ios::sync_with_
2020-10-10 11:08:49
549
原创 三分法---黄金分割（求单峰函数最值） 洛谷--P3382 【模板】三分法
黄金分割法具体思路看这个看懂之后看代码是秒懂纯纯的三分进化版，思路和三分一毛一样，只是取的两个三分点变成了两个黄金分割点，每次缩小的范围比三分点稍微大一点点#include <bits/stdc++.h>using namespace std;const double gold = (sqrt(5)-1)/2;//黄金分割率const double eps = 1e-8;//正常题目要求精度+2const int MA = 15;double xi[MA];//所存系数 in
2020-10-07 20:52:08
633
原创 进阶指南---动态中位数（听说这个叫对顶堆）
要动态搜中位数的这个对顶堆真妙，只是优先队列忘的一干二净呜呜呜插入一下优先队列小知识//小数先出priority_queue <int,vector<int>,greater<int> > q;//大数先出priority_queue <int,vector<int>,less<int> >q;priority_queue<int> q;一定要注意优先队列默认大数先 出回到题目用两个优先队列，一个大数先出
2020-10-01 16:06:32
87
原创 进阶指南---七月祭（中位数+前缀和）
思路1.交换两个相邻的摊点，要么只改变行，要么只改变列2.就可以等价于两个均分纸牌：交换相邻的行中纸牌，使其最后每行的牌数相等，又因为最后一行与第一行也相邻，就进化成了环形均分纸牌（哇哦）3.普通的均分纸牌，减去平均数后，取每个行前缀和的绝对值相加即可4.环形可以看成n种切断某个点的普通均分纸牌，那么切断后的前缀和值会有什么改变呢？看图·知真理巧的就是那个sum[n]=0的利用，妙啊！在这里插入代码片...
2020-10-01 13:42:05
165
原创 进阶指南---货仓选址
排序，发现规律：距离最小为选在最中间的那个数，如果是偶数个，则可以随意选择其中一个#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int MA = 1e5+10;int a[MA];int main(){ int n; scanf("%d",&n); for (int i = 0 ; i < n; i++) scanf(
2020-09-29 16:45:49
145
原创 进阶指南--电影
题意找那部看它很开心的人数最多的电影，很开心一样就看比较开心的那就把人数存起来呗，因为编号到1e9,那hash不想写,所以就用unordered_map 代替咯 然后暴力比较就完事了#include <cstdio>#include <iostream>#include <algorithm>#include <unordered_map> using namespace std;const int MA = 2e5+10;int yin[M
2020-09-29 16:29:16
87
原创 进阶指南--最佳牛围栏
听说这个叫二分答案判定题目就是n块田地，每块田多少牛，然后问你连续区间长度不小于F的牛数量的和的平均值的最大值那由题目我们可以知道，平均值的区间为1-2000，那平均值又要怎么和我们的判定联系起来呢假设我们已经知道了这个平均值最大值a的值，这个时候将每块田的牛减去这个a，这个时候得到的连续区间长度不小于F的和最大值是不是为0？那如果刚开始我们不知道进行枚举平均值呢？是不是如果最大值 > 0 枚举的数大了其他情况 枚举的数小了所以接下来就是然后求得到的连续区间长度不小于F的和的
2020-09-29 16:02:20
293
原创 关于scanf 加空格或者‘\n‘问题
被学弟学妹问倒，哎呀呀，没玩过，配合他们玩一玩其实正常来讲是没有人会写\n在scanf里的正常来说scanf是用来格式化输入的例如你要输入 1,2,3 你想读到1和2和3哎呀呀很容易啊 scanf("%d,%d,%d",&a,&b,&c); 这样子1和2和3就会完美存入a,b,c啦那为啥子不推荐在scanf("")里面写’\n’呢主要是因为，你读整数，小数的时候人家c 会很主动地帮你忽略’\n’空格等制表符啊，人家都那么主动了，你还忍心多此一举，你你你，哎呀呀，(注意：
2020-09-25 21:30:00
4336
4
原创 进阶指南---最高的牛
还是差分思想，化对区间的变动成对点的变动，中间的牛矮那就把该区间全部减一，反正最后最高的牛肯定是0，那么得前缀和之后再加上最高的牛的高度即可，有两个坑1.a,b 大小顺序不定swap2.可能会重复两头牛，map<pair<int,int>,int>代码如下：#include <cstdio>#include <iostream>#include <cstdio>#include <map>#include <al
2020-09-22 23:41:10
67
原创 进阶指南---Incdec序列（增减序列）--差分
差分真妙，是前缀和的逆过程例如：b[3] = a[3] - a[2]b[2] = a[2]-a[1]b[1] = a[1]你会发现 a[3] = b[3]+b[2]+b[1]!!!哇哦是不是发现新大陆？还有更妙的 前缀和的[L,R]加d ,你会发现，等价于 差分的[L]+d, [R+1]-d !!!也就是 a[L~R]+d <==> b[L]+d 、b[R+1]-d那么差分还有什么意思勒，两个数的差！那么所有数之间的差如果都为0的意思，不就是所有数相等？？那么区
2020-09-22 23:16:22
455
原创 进阶指南---激光导弹 （二维前缀和）
哇，一维都不会突然就二维了哇但其实思想就是对前面的数进行一个O(n)统计而二维的规律看图：可以发现 sum[i,j] = sum[i,j-1] + sum[i-1,j] - sum[i-1,j-1] +a[i,j] (a[i,j] 为那个位置的数)然后题目炸一个R的正方形，那不就是举一反三嘛，来看图（红色的正方形）= sum[i,j] - sum[i,j-r] - sum[i-r,j] + sum[i-r,j-r]不就是有手就行?!哦题目有两个坑：位置可能重复，而你需要叠加该位置的
2020-09-22 18:38:27
235
原创 进阶指南-----约数之和
又是A^B…现在变成了求约数都被搞了那么多次，该懂了遇到就要拆，那拆啥，把A拆成约数相乘呗A =( P1 ^ k1) * (P2 ^ k2 )* …(Pn^kn)A^B = (P1^(k1B)) * (P2^(k2B)) * … (Pn^(knB))所以约数组合的和就可以表示为（1 + P1^1 + P1^2 + P1^3… P1^（k1B））* （1 + P2^1 + P2^2 + P2^3… P2^（k2B））…（1 + Pn^1 + Pn^2 + Pn^3… Pn^（k
2020-09-22 17:00:49
178
原创 进阶指南--奇怪的汉诺塔
本来学的是三个的汉诺塔，现在4个怕了吧哈哈哈，例如我呜呜呜1.三个汉诺塔（A、B、C）的情况就是把 有的n个汉诺塔分为两部分：最下面那个和上面的n-1个，你会发现，我们可以把n-1个先转移到B塔，把最下面那个给扔到C塔，再将n-1个移到C塔，哦吼就完成啦！所以递推公式为： *dp[i] = dp[i-1] 2 +1;2.四个汉诺塔我们可以类比推理三个汉诺塔，我们在三塔的时候可以把一个转移B塔，那么如果我们在四塔的时候把i个转移到B塔，那剩下的是什么，三个塔！那么不就是 dp [n-i] !最后
2020-09-21 17:48:35
120
原创 进阶指南---费解的开关
本题就是在于找规律，我们发现，只要第一行一旦固定，后面的所有状态都固定了，例如如果第一行的状态为11110，那你后面就只能按第二行的最后一个开关，而没有其他选择，因为你要保证前面的都是全亮。而缺点是这样子递推的话，最后一行的状态也是固定，所以就需要再判断一下是否符合要求即可1.第一行按的方式有32种，用二进制位表示很好操作2.转换开关可以用异或或者非进行0/1变换代码如下#include <cstdio>#include <iostream>#include <cs
2020-09-21 16:34:03
93
原创 进阶指南--递归实现排列型枚举
裸回溯代码如下#include <cstdio>#include <algorithm>#include <iostream>using namespace std;int used[12];int n,chosen[12];void pp(int x){ if(x == n+1){ for (int i = 1; i <= n; i++){ printf("%d ",chosen[i]); } printf("\n"); r
2020-09-18 22:37:03
87
1
原创 进阶指南---递归实现组合型枚举
因为要求要字典序从小到大来，那我们就要考虑一下顺序，也就是先选小的，再不选小的，和上一个选与不选调换一下位置即可然后数据范围变大，考虑剪支，什么情况没用勒，1.选择的数已经比要的多了2.剩下的数的数量加上已经选择的数也不够要的这样子就行了代码如下#include <cstdio>#include <iostream>#include <algorithm>#include <vector>using namespace std;vecto
2020-09-18 22:25:58
82
原创 进阶指南-- 递归实现指数型枚举
题意就是从n个数选任意多个进行组合每一个数不就两种情况嘛，要么选，要么不选，再加个边界输出return，拿个数组存一下要放入组合的数不就结束了？哦，记得回溯代码如下：#include <cstdio>#include <iostream>#include <algorithm>#include <vector>using namespace std;int n;vector <int> chosen;void cc(int x)
2020-09-18 22:12:55
80
原创 进阶指南（简单模拟）--起床困难综合症
很纯的模拟从高位到低位暴力0/1的与、或、异或即可暴力完判断一下如果用掉的内存加上这个数没超内存 m ，那就加上，超了就算了注意：0/1的选择上除非1的最终结果大于0的结果，不然都是选0才最优代码如下:#include <cstdio>#include <iostream>using namespace std;const int N = 1e5+10;char s[N];//存字符 int t[N];//存t int main(){ int n,m,T;
2020-09-18 16:11:52
93
原创 进阶指南---最短Hamilton路径（状态压缩dp）
题目为带权无环图，要将每个点都走恰好一遍，问最短路径–为旅行商问题那要怎么搞呢，看了别人的题解发现，其无非就只有两个关键点，一个为当前走过了哪些点，而为目前是哪个点 (f[i][j])走过了哪些点，n最大为20，不难想到可以用二进制的位来模拟，1则走过，0则还没走，关键在于转移：考虑上一步？哦吼，走了哪个点？那是不是就是i 中 二进制表示下为1的位都有可能为上一个点？那现在又准备走那步勒？不就是i 中 二进制表示下为0的位都有可能为当前准备走的点？？？那不就出来拉~if ( ( i >
2020-09-18 15:09:09
121
原创 进阶指南---a*b
本质和快速幂的思路是一毛一样的，b还是老规矩化成那个式子，我们就会神奇的发现，和快速幂相比不过是把a^–>a***** ,把 a^(2) * a^(4) --> a^(2) + a^(4) 罢了，因为刚开始不是直接一直乘，而是加，所以res = 0即可代码如下：#include <cstdio>#include <iostream>using namespace std;typedef unsigned long long ULL;U
2020-09-18 13:33:14
331
原创 进阶指南 - a^b (快速幂取模)
取模有一个性质 ： （ab）%p = ((a%p)(b%p))%p (改为+或者-都可)本题采用倍增，将b转化为公式 c020+c1*21+…cn2^n放于a^b中就变成 a^( c02^0 ) * a^( c12^1 ) *…a^( cn2^n )那么只要循环把c 不为0 的乘进式子就行来需注意的就只有取模的时候res本来为1 考虑p 为1，b为0 则循环进不去，要返回0！！！代码如下：#include <cstdio>#include <iostream> us
2020-09-18 13:19:30
525
2
原创 poj 1703 听说叫种类并查集
又是默默看题解的一天唉目前对它的理解在于两个队伍，给的人物是告诉你不同队的，而不是一个队的那咋搞，它的想法是通过一个媒介n，其实个人感觉n是多少无所谓，只要不要和原来的n个人有交集就可以了，一样的找爸爸思路，但这个时候因为是不同队的，找爸爸的孩子不开心了，硬要一个爸爸，例如a,b就给a分配了b+n做爸爸，b就分配a+n做爸爸，这样子就假装有了爸爸咯，但是这个样子确可行，在找哪些孩子是一个爸爸的时候就可以成功，就很神奇，还有可以用a和c+n看看是不是一个爸爸，如果是，则二者对立关系就可以确定，相反则不行
2020-07-17 17:35:52
104
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人