- 博客(52)
- 收藏
- 关注
RSS订阅原创 Apollo源码注释
目录结构介绍cyber 消息中间件，替换ros作为消息层data 地图等生成好的数据放在这里（其他数据待补充）docker 容器相关docs 文档相关modules 定位，预测，感知，规划等自动驾驶模块scripts 脚本third_party 第三方库tools 工具目录，几乎为空Cyber模块Cyber main函数中先根据命令行信息解析dag参数，然后利用解析的参数，动态的加载对应的模块输入：命令行数量+命令行内容输出：加载状态关联模块：Allmainbo
2023-10-11 18:34:50
286
原创 Apollo源码安装的问题及解决方法
在进行git clone时，会报错Failed to connect to github.com port 443: Timed out，经过实践后推荐以下两种方法。
2023-09-14 10:22:23
443
原创 Educational Codeforces Round 115 E. Staircases
题目链接思路题目的三种状态相对固定，所以在全部方格都处于自由的状态下，很容易想到用简单的dp[i][j][k]dp[i][j][k]dp[i][j][k]进行转移并求出所有的阶梯数。其中dpdpdp方程表示以坐标为i,ji,ji,j的方格为阶梯的末尾，存在多少种情况，kkk为000时表示当前方格在下方，111表示当前方格在右方。不过由于初始的dpdpdp值设定为111(单独的方格符合题意)，不难发现单个的方格会被重复计算，所以可以使用cntcntcnt表示当前自由的方格数量，用总的方案数减去cntcn
2021-10-14 21:12:28
173
原创 Codeforces Round #627 (Div. 3) F. Maximum White Subtree(树形DP)
题目链接题意给定一棵树，树上的n个节点有黑白两色，需要你计算出各节点的子序列中白点总数减黑点总数的最大值。思路其实很容易想到以某一结点为根节点，当其子节点的值可以使其更大时，则进行更新，否则保持不变。用DP维护该点下方的子序列的最大值即可获取答案的一部分，即除根节点外，其他节点以下部分子序列的最大值。此时若要获得所有节点的答案，则要进行自上而下的维护。再由之前的根节点出发，若其答案减去当前遍历到的子节点的贡献依然大于零，则其可以对子节点上方序列的答案进行补充，依次向下直到更新完毕即可获取答案。代
2021-05-07 15:56:52
108
原创 HDU1814 Peaceful Commission(2-SAT输出字典序最小的解)
题目链接题意现在有n个党派，每个党派拥有两个候选代表，第i个党派的候选代表为2i-1和2i，两个党派候选人只会有一个去参加会议，此外还有m对候选人互相看不顺眼，只能去其中一个，求字典序最小的代表人选。思路一个比较明显的2-SAT问题，但是需要输出最小解，所以似乎不可以用传统的拓扑排序寻找可行解，于是采取了DFS解法，复杂度O(nm)，其能选取出最小解的原因应该是采取了顺序的遍历方式。代码#include<bits/stdc++.h>using namespace std;con
2021-05-01 10:30:23
128
原创 Educational Codeforces Round 105 B.Berland Crossword
题目链接思路根据题目对U,R,D,L的定义，可知关键为四个边角的状态，于是考虑遍历四个边角的状态，0为白色，1为黑色并进行判断即可获得结果。代码#include<bits/stdc++.h>using namespace std;const int mod=3;const int inf=0x3f3f3f3f;string s;stack<char>st;int n,u,r,d,l;bool judge(int x,int y,int z,int w){
2021-03-04 18:57:27
114
1
原创 2021牛客寒假算法基础集训营5 B.比武招亲（上）
题目链接思路这题多列举一些样例会发现，可取的情况数量与差值实际为排列组合关系。比如当前有n个数，一次选取m个，差值的范围显然为1至n-1。而对于每种差值，我们可以确定它的前两位，比如差值为1的开头两位必定是相邻的两个数，此时如何确定组合数呢？为了不改变当前确定的差值，即不可以改变序列中的最大值与最小值，所以在当前差值所取得的两数之间的数都是可取的，假设当前枚举的差值为i，我们可以从i+1(包括当前取得的两个数，比如差值为1，那么可取的数为差值为1的两个数本身)个数中任意选取m-2(初始两个已确定)个出
2021-02-23 15:03:16
158
1
原创 Codeforces Round #703 (Div. 2)(A-C）
A. Shifting Stacks您有n叠积木，第i个堆栈包含hi块，其高度是其中的积木块数。一次移动可以从第i个堆栈中取出一个积木（如果至少有一个）并将其放入第i + 1个堆栈中。您可以使堆栈高度严格递增吗？注意:堆栈数始终为n，即使堆栈中积木数量为0也不会消失。思路显然我们在构造的过程中使堆栈以0，1，2……n-1的数量排列为最优的方案，只要在过程中检验是否可以达成即可。代码#include<bits/stdc++.h>using namespace std;const i
2021-02-19 12:00:48
172
原创 POJ3579 Median(两次二分)
题目链接DescriptionGiven N numbers, X1, X2, … , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as
2021-02-11 12:22:46
210
1
原创 POJ2976 Dropping tests(二分+01分数规划)
题目链接DescriptionIn a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be.Given your test scores and a positive integer k, determine how high you can make your cumulative average
2021-02-10 16:16:37
138
原创 Gym - 101194 D Ice Cream Tower(贪心+二分答案)
题目链接题目描述熊猫先生非常喜欢冰淇淋，尤其是冰淇淋塔。一个冰淇淋塔由K个冰淇淋球堆叠成一个塔。为了使塔稳定，下面的冰淇淋球至少要有它上面的两倍大。换句话说，如果冰淇淋球从上到下的尺寸是A0, A1, A2，···，AK 1，那么A0×2 ≤ A1, A1 × 2 ≤ A2，等等。有一天，熊猫先生在街上走着，发现一家卖冰淇淋球的商店。冰淇淋球共有N个，大小分别为B0、B1、B2、··、BN−1。熊猫先生想知道这些球最多能做出的冰淇淋塔数量。Input输入的第一行给出了测试用例的数量，接下来是T ，
2021-02-09 19:28:42
130
原创 Codeforces Round #700 (Div. 2)C. Searching Local Minimum(交互+二分)
题目链接Input532145Output? 1? 2? 3? 4? 5! 3NoteIn the example, the first line contains an integer 5indicating that the length of the array is n=5The example makes five “?” queries, after which we conclude that the array is a=[3,2,1,4,5]and
2021-02-08 15:24:04
106
原创 2021牛客寒假算法基础集训营3 F.匹配串
题目链接题目描述一个模式串指仅包含小写英文字母和至少一个’#‘的字符串，其中’#‘可以匹配一段任意长度的任意小写字母字符串。一个匹配串指待匹配的只包含小写字母的字符串。一个模式串和一个匹配串相匹配当且仅当把模式串里面的’#'全部分别替换成空或一段小写字母字符串后，两个串完全相同。现在给出n个模式串，问有多少不同的匹配串与这些模式串全部相匹配。如果答案有无穷多个，输出-1。输入描述:第一行一个正整数n。接下来n行每行一个只包含小写字母和’#‘的模式串。(1≤n≤1e6)保证输入模式串的长度
2021-02-08 09:24:02
87
原创 2021牛客寒假算法基础集训营1 D.点一成零
题目链接题目描述牛牛拿到了一个n*n的方阵，每个格子上面有一个数字：0或1行和列的编号都是从0到n-1现在牛牛每次操作可以点击一个写着1的格子，将这个格子所在的1连通块全部变成0。牛牛想知道，自己有多少种不同的方案，可以把全部格子的1都变成0？所谓连通块，是指方阵中的两个正方形共用一条边，即(x,y)和以下4个坐标的数是连通的：(x-1,y)、(x+1,y)、(x,y-1)、(x,y+1)这个问题对于牛牛来说可能太简单了。于是他将这个问题变得更加复杂：他会选择一个格子，将这个格子上的数字修改
2021-02-07 17:07:59
174
原创 2021牛客寒假算法基础集训营1 C.红和蓝
题目链接题目描述你拿到了一棵树，请你给每个顶点染成红色或蓝色。要求：每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。“周围”的定义：某点周围的点指通过邻边直接连接的点。所谓树，即没有自环、重边和回路的无向连通图。输入描述:第一行一个正整数 n，代表树的顶点个数。(1≤n≤100000)接下来的n−1行，每行两个正整数u和v，代表点u和点v有一条边连接。 (1≤u,v≤n)保证输入的一定是一棵合法的树。输出描述:如果可以达成染色的要求，请输出一个长度为n的字符串，第i个
2021-02-07 10:37:45
1223
原创 2021牛客寒假算法基础集训营3 I.序列的美观度
题目链接思路这道题可以用DP来解决，我们首先需要考虑的是转移状态。若我们用DP[i]表示从1到i之间的最大序列美观度，则可以推导出若当前整数与前一个不同，则直接继承前一个的DP，或者也可以从上一个与当前数相同的位置转移而来，只要将其美观度加一即可。于是我们可以在输入时预处理好各个数字在序列中所对应的前一个相同位置并用数组sit进行记录即可。代码#include<bits/stdc++.h>using namespace std;const int mod=1e9+7;const
2021-02-06 09:24:20
97
原创 2021牛客寒假算法基础集训营2 I.牛牛的“质因数”
题目链接思路比赛的过程中想到了先筛出所有质数，然后通过相互之间的关系进行DP状态的转移，观察题目所给的样例不难得出，一个数的结果就是其因子结果的结合。例如6可以被分解为2和3，其结果便是2*10+3=23。但此处我选择了选出每个数的最小质因子，然后将这个最小质因子的结果扩大至可以将另一个因子的数值合并。可这样的写法存在一个弊端，即过程中不可取模，因为一旦取模就会影响到最小质因子所对应的因子的位数，结果自然就会出现问题。正确的写法应当与此相反，寻找其最大的质因子，然后将最大质因子所对应的因子扩大至可以将
2021-02-04 17:16:39
139
1
原创 2021牛客寒假算法基础集训营1 J.一群小青蛙呱蹦呱蹦呱
题目链接题目描述有n个格子，每个格子里有一个数，1,2,3,4…n牛牛放出无穷只青蛙。第一只青蛙的路线是：1->2->4->8…第二只青蛙的路线是：1->3->9->27…第三只青蛙的路线是：1->5->25->125…第四只青蛙的路线是：1->7->49->343……用数学语言描述，第i只青蛙的路线是首项为1，公比为p(i)的等比数列，其中p(i)代表第个素数。当青蛙跳到一个格子上，如果这个格子上面有一个数，青蛙就会
2021-02-02 20:44:51
90
原创 HDU1255 覆盖的面积(扫描线+离散化+线段树)
题目链接Problem Description给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.Input输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.注意:本题的输入数据较多,推荐使用scanf读入数据
2020-11-21 10:54:12
105
原创 Codeforces Round #372 C.Plus and Square Root
题目链接input3Output141646Input2Output99999999999999999844500000000Input4Output2174697
2020-11-19 18:46:40
102
原创 Codeforces Round #683 B. Numbers Box
题目链接Input22 2-1 11 13 40 -1 -2 -3-1 -2 -3 -4-2 -3 -4 -5Output230思路题目要求变换使得矩阵的和最大，由于变换次数不限，所以推断可知当负数数量为偶时，一定可以将所有值都变换为正数，此时结果为所有数的绝对值之和。当负数数量为奇时，至少会有一个数仍为负数，所以此时的结果为所有数的绝对值之和减去绝对值最小的数的两倍。代码#include<bits/stdc++.h>using namespace std
2020-11-16 16:53:11
153
原创 Codeforces Round #679 C（尺取）
题目链接思路由于琴弦序列仅有六种，所以可以将每一个音符与其的差值用结构体记录，排序后在进行尺取即可寻找到符合条件的最值。代码#include<map>#include<stack>#include<queue>#include<string>#include<math.h>#include<stdio.h>#include<string.h>#include<iostream>#inc
2020-10-27 11:39:16
177
原创 Codeforces Round #678 (Div. 2) C
题目链接思路按照题目所给程序，将a[mid]<=x等价转化为mid<=pos，即可求出需要小于和大于x的数量。则答案转化为在x-1个数中任意选取small个小于x的数×在n-x个数中任意选取big个大于x的数×剩余的(n-big-small-1)个数任意组合。代码#include<map>#include<stack>#include<queue>#include<string>#include<math.h>#i
2020-10-26 14:17:47
147
原创 HDU1272 小希的迷宫(并查集判正环)
题目链接思路选用并查集判断是否形成环与是否全部连通即可，如果两个点父节点相同，则必定成环，连通则可以通过i==pre[i]的数量进行判断。代码#include<map>#include<stack>#include<queue>#include<string>#include<math.h>#include<stdio.h>#include<string.h>#include<iostream&
2020-10-24 23:14:00
94
原创 ZOJ3261 Connections in Galaxy War(逆向并查集+删边)
题目链接Sample Input210 2010 15query 0query 1destroy 0 1query 0query 1Sample Output1-1-1-1思路题意在此就不赘述了，相较寻常并查集增添了删边的操作。怎样才可以在并查集中实现删边的操作呢？我们可以选用逆向的方法。首先我们将所有应删边去除后的其余边进行连接，然后从后往前对操作进行实现。当需要查询时，就查询当前情况是否符合题目要求，对结果进行记录；当需要删边时将此边恢复，则可以回到上一次查询时
2020-10-22 15:31:42
110
原创 POJ1733 Parity game(并查集+Map离散化)
题目链接DescriptionNow and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) an
2020-10-17 12:21:47
52
原创 Educational Codeforces Round 96 D(贪心+双指针)
题意给定一个长度为n且只包含0和1的字符串，每次执行两个操作:删掉字符串中任一字符，再去除连续的前缀，询问使字符串为空的最多操作次数。思路对于这样的字符串，我们可以思考如何取才可以达到最优解。例举一些数据可以看出对于字符串开头部分单个非连续的字符，我们可以将其加入非连续子串。若遇到连续子串，可以按照非连续子串的长度与连续子串长度的关系选择将子串留下一个与剩余非连续子串合并或者将非连续子串清空并利用剩余部分再进行一次操作。代码#include<map>#include<sta..
2020-10-13 13:36:47
172
原创 Codeforces Round #673 (Div. 2) C
思路对于每个数，考虑相同数之间最少需要多长的k才能将其涵盖。枚举一个数与序列开头、中间数之间的差和序列结尾，过程中记录长度k范围内最小的数值。代码#include<map>#include<set>#include<stack>#include<queue>#include<string>#include<math.h>#include<stdio.h>#include<string.h>.
2020-10-02 14:39:39
1791
1
原创 HDU4614 Vases and Flowers(线段树区间更新维护+二分)
题目链接Problem DescriptionAlice is so popular that she can receive many flowers everyday. She has N vases numbered from 0 to N-1. When she receive some flowers, she will try to put them in the vases, one flower in one vase. She randomly choose the vase A an
2020-09-29 14:04:21
91
原创 POJ1182 食物链(并查集好题)
题目链接Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是"1 X Y"，表示X和Y是同类。第二种说法是"2 X Y"，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真
2020-09-25 19:50:09
126
原创 洛谷P3386 [模板]二分图最大匹配(网络最大流)
题目链接题目描述给定一个二分图，其左部点的个数为 nnn，右部点的个数为 mmm，边数为 eee，求其最大匹配的边数。左部点从 111 至 nnn 编号，右部点从 111 至 mmm 编号。输入格式输入的第一行是三个整数，分别代表 nnn，mmm 和 eee。接下来 eee 行，每行两个整数 u,vu, vu,v，表示存在一条连接左部点 uuu 和右部点 vvv 的边。输出格式输出一行一个整数，代表二分图最大匹配的边数。输入 #11 1 11 1输出 #11输入 #24 2
2020-09-25 17:01:00
177
原创 洛谷P1343 地震逃生(网络最大流板子)
题目链接题目描述汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领x名学生逃跑，整个学校可以抽象地看成一个有向图，图中有n个点，m条边。1号点为教室，n号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生，只有第一批学生全部逃生完毕后，第二批学生才能从1号点出发逃生，现在请你帮校长算算，每批最多能运出多少个学生，x名学生分几批才能运完。输入格式第一行3个整数n,m,x(x<2^31,n<=200,m<=2000)；
2020-09-24 16:58:02
171
原创 LightOJ1197 Help Hanzo(欧拉筛+区间素数)
题目链接Problem DescriptionAmakusa, the evil spiritual leader has captured the beautiful princess Nakururu. The reason behind this is he had a little problem with Hanzo Hattori, the best ninja and the love of Nakururu. After hearing the news Hanzo got extrem
2020-09-23 19:05:09
100
原创 LightOJ1214 Large Division(高精度除法求余)
题目链接Problem DescriptionGiven two integers, a and b, you should check whether a is divisible by b or not. We know that an integer a is divisible by an integer b if and only if there exists an integer c such that a = b * c.InputInput starts with an integ
2020-09-23 16:51:02
100
原创 LightOJ1236 Pairs Forming LCM(唯一分解定理)
题目链接题意用更加高效的方法计算图中所示程序的结果，要求i<=j并且LCM(i，j)=n,求满足条件的对数。思路根据lcm(a,b)=p1^max(a1,b1)×p2 ^ max(a2,b2)×…×pn ^ max(an,bn)可知当ai=ei时，bi可取[0,ei]范围内的任意数，bi=ei时同理，则共有2*(ei+1)种结果。但当三者都相同时，会出现重复的情况，所以需要减去。在所有剩余情况中，除了(n,n)外其余都出现了两次，所以先加一再除二即可得出结果。代码#include<
2020-09-22 10:49:00
104
原创 LightOJ1245 Harmonic Number (II)(整数分块)
题目链接Description题意求取图中的结果，但n会非常大。思路其实这是除法分块的板子题，由于除法运算时会出现许多结果相同的数，所以将这些数进行分块计算就可以提高运算的效率。代码#include<map>#include<set>#include<stack>#include<queue>#include<string>#include<math.h>#include<stdio.h>#in
2020-09-21 17:32:50
116
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人