从acm退役到小马面试，只准备了20天左右，没项目不会八股，啥都不懂。年前投的，2月底面试完。 Pony.ai 电话面试 一小时（提前答完，提前结束了） 自我介绍 · 求一个最大的区间，最小值和最大值的差小于等于x（双指针维护合法区间O(n)，或者单调栈维护一个递增序列，然后二分(O(nlogn)） · 求一个字符串是不是另一个字符串的子串 还有什么想问的（没有准备，随便扯的） ...

解题思路：·如果只考虑往外扩张的车辆，发现只能扩展log层，猜想车辆的活动半径不会很大，打表发现是个类似圆形的图形，也就说明车辆的移动直径是根号n级别的，把横纵坐标都+500，可以直接用数组来模拟·会发现车辆的移动顺序是无关的，假如一个方格内有16辆车，一次移动8辆和一次移动16辆是等价的，模拟的时候就可以把尽可能多的车移动出去。 #include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;i++) #define pii pair<int,int> #define Please return #defi...

题意：询问[x,p,k]，找出比x大且与p互质的第k个数 解题思路： idea很简单 首先容斥原理可以算出某个范围内的与x互质的个数（oi-wiki上有介绍） https://oi-wiki.org/math/inclusion-exclusion-principle/ 二分范围 dfs比二进制快一点 #include <bits/stdc++.h> using namespace std; const int INF = 0x3f3...

题意：那是在一个n×m的矩阵里面有一些雷，要你根据一些信息找出雷来。这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。 解题思路：如果是dp的话，需要设置一个状态能同时表示3个位置，也就是dp[i][a][b][c]，a、b、c的状态分别表示i-1、i、i+1行有没有雷。根据经验只需要表示i和i+1行的状态就可以了。于是就分类讨论转移方程 #include <bits/...

初始化dp=INF，INF貌似只能是0x3f3f3f3f。（不知道为什么） 给出的点貌似是顺序的，不需要极角排序。

题目描述Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大Applese觉得这个题依然太菜，于是他把这个问题丢给了你当物品数量为偶数时，中位数即中间两个物品的价值的平均值 解题思路： 中位数取决于中间两个数的大小 先对物品根据价值进行排序 m为奇数时直接枚举中间的那个数，左边选m/2-1个体积最小的，右边选m/2-1个体积最小的 m为偶数时，考虑枚举右半部分的最小价值，这个最小价值对应了一个最小体积，然后多出来了部分体积，在这部分体积里...

题意：给定一棵 n 个节点的树，初始选择节点 s，第一天定居在s，并将s和与s相邻的节点染色。之后每一天选择一个未染色的点定居，将定居点和定居点相邻的节点染色。问最多能定居多少个节点。 题解每个点都会被染***r>考虑如何给叶子节点染色，发现要把叶子节点染色，定居在叶子处最佳，所以我们首先选择叶子节点定居。染色后把染色的点去掉，给新的叶子染色，直到所有节点被染色。 Code #include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i&g...

解题思路：只考虑一颗儿子全是叶子的子树时，那么最佳的匹配方案是这些叶子节点两两配对，多余的和根配对。直观感觉这个子树的边全被统计了，而且只统计了一次，如果叶子和非子树的点配对的话，这个子树的边仍然全被统计了，子树根到它父亲的边会被多次统计。按照这个思路，所有边最多只会被统计一次。 现在证明这个方案是最优的。如果一颗子树的节点数是奇数，多出一个和非子树的点匹配，所以这颗子树的根的父边一定会被统计，如果是偶数个点，按照上述思路一定不会统计，用其他方法可能会被统计。所以这个方法是最优的。 #include <bits/stdc++.h> using namespace std; #def...

dp[i][j]表示在s1中选择前i个字符，在s2中选择前j个字符，能够成合法序列的方案数（这里的合法指的是每个')'都能找到一个'('与之对应）。一个长度为i+j的括号序是从(i-1,j)和(i,j-1)转移过来的,所以dp[i][j]=dp[i-1][j]+dp[i][j-1]。判断dp[i][j]是否合法，只需要判断s1和s2中的'('的数量是否比')'多，其他不用管。假如s1是(,s2是))(,这样当然构造不出一个合法序，但是dp[i-1][j]和dp[i][j-1]一定也为0.就是说如果dp[i][j]不合法，它一定不能从合法的状态转移过来。另外需要注意的是，这题卡内存。