😭😭😭😭😭周一约的一面，面试官说应该两三天通知结果

许愿美团优选三面，滴滴三面，明天华子二面过！

http://60.179.32.89:2811/e/file/download?code=9d7486fc9c41a5f4&id=210283

随机算法+套路思维 第一次遇到随机算法也不能说没有像那个方向去想 因为我们有n个移动方案然后组合一共有个所以，对于一个点大概室友的概率被抓到 然后我们就可以靠这个随机枚举个点，然后判断是否可以抓到 就好了。。。。。 #include<iostream> #include<algorithm> #include<vector> #include<ctime> using namespace std; const int max_n = 1e5+100; typedef pair<int,int> pii; pii G[max_n]; i...

贪心+思维 这一题我本来也是可以做的经过一段时间的思考后我们可以发现，最先撞击的两个无人机一定是相邻的两个无人机 我们可以用一个优先队列维护所有的相邻的两点撞击的时间然后贪心地取撞击时间小的点，然后更新 这个撞击时间是一个小数，在比较时有精度误差，因为精度误差我一直错 在涉及小数比较的时候，优先考虑是否可以进行ll比较，避免除法，转化为乘法 #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; typedef pair...

背包 其实就是一个背包 是一个数据范围超大的背包 一开始我就意识到了，在数据范围非常巨大的情况下，他一定是会在一个很边界外只选性价比最高的那个原子 而在在这个边界之内我们就要用背包来解决了！ 这个边界我们无从得知，可以根据数据范围和允许时间进行估计。 但是我的基础的dp转移方程写复杂了，所以我边界在一开始估计小了然后WA了好多发 #include<iostream> #include<algorithm> using namespace std; typedef unsigned long long ll; ll dp[10500]; int n,q; int mai...

瞎搞题 刚开始没有反应过来想着有没有什么正解。但是WA了一发之后，思考了很久突然意识到妈妈组这个条件的和一定不会很多！！！然后抱着试试的心态，交了一发 #include<iostream> #include<algorithm> #include<map> #include<cmath> using namespace std; typedef long long ll; const int max_n = 1e6+100; const int bo = 1000000; ll query(int x,int y) { cout&l...

构造题 我们从中间开始取元素，然后左右来回取最近的元素，一定可以保证范围不断地变大 #include<iostream> #include<algorithm> using namespace std; const int max_n = 1e5+100; int a[max_n]; int n; int main() { ios::sync_with_stdio(0); cin>>n; for (int i=1;i<=n;++i)cin>>a[i]; sort(a+1,a+1+n); int id...

D题因为细节错误，最后一分钟才A出来。。。。。。。 首先，我们有一个很明显的贪心。就是，我们从左到右去枚举边的话，肯定是尽量囊括边 到濒临阈值的情况下 即，我们从最左端一直向右取边，取到极限，算作一组然后以当前位置为最左端，向右取边取到极限，算作一组以此类推。 但是我们是无法这样做的，因为我们无法做到动态的查询强连通分量 那么二分可不可以呢？首先我们以最左端编号1开始二分，找到他可以取到的最右端的编号l2然后再次二分。。。。每次二分都使用一次tajan算法验证一遍 但是这样行不行呢？没试，但是预计会T 我们可以大致感觉到这个复杂度是有点高的 这时，我看了下数据 然后我们可以意识到一个重要的结...

数论+分组背包打表找一找规律就发现了，我们不过是求这一个数组的最小公倍数，想办法让其最大然后我们运用分组背包的想法，肯定里面的数互素的情况下才好。 #include<iostream> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int max_n = 31000; int a[max_n]; double dp[3500][max_n]; bool used[max_n]; int tot=0; double b[3500]; v...

思维+建图 首先，万物起源：对于这种两个变动的题目，我们相对的看可以给金的每次移动向前增加一位 然后我们在草稿上画出一个金可以走到的所有格点会发现，正好以斜线为界限的范围是这个金可以走到的地方 但是，还有一个问题，这里是一轮过后，即金和步都走一步后但是还有可能步还没走就让金吞了 因此，为了避免这种情况下的漏算，我们不妨拆点，对于每一个点我们拆一个点正好在他头上。 然后我们遍历，连边对于拆的点，我们原来的点不和他连边 但是，这样有一个问题：即，如果出现了两个原来的点他们正好连着，即点b在点a的头上那么我们就尴尬了 为了解决这个问题我们换统计点权为统计边权我们事先排序，在此之后我们再判断是否存在这...

思维+二进制+递归分治 首先一个重要的策略我们先对数据从小到大排序 然后如果一个前缀和，比后面的阶数要小那么，我们此刻就可以将这个数组分开单独看 这里就是分治了 答案是两边结果的乘积 然后对于一个没有被分开的数组，我们该如何求解他的答案呢？答案就是将他的每一阶数全都转化为当前区间的最小的那个阶数 统计这个数目即可！ #include<iostream> #include<algorithm> #include<map> using namespace std; typedef long long ll; typedef pair<int,int>...

决策的单调性和分治 这一题有两步转化 第一步是：将原式看作为矩形的面积 其实，即使我们不做这个转化，我们也是能够看出来的我们可以知道，如果 且那么作为右端点一定比优这样就维护了一个单调减的序列同样，方向反过来，我们也可以找到作为左端点的单调增的序列 我赛时分析到这里，然后走不下去了。 但，我们既然将左右端点的可能性成功处理成了单调的那么就一定有什么性质，这里是二分分治 第二不是，对于单调处理后，左端点第mid个，假设和右端点第pos个最优，那么我们可以断定对于所有的索引 他们的最优右端点对于所有的索引他们的最优右端点 可以利用反证法证明，也可以找规律甚至是猜！！！因为单调性一定会给我们带来什...