C2. Skyscrapers (hard version) 题意： 求一个新的序列，使得其合最大，要求新的序列满足该序列的最大值左右两边（可以只有一边）呈非升序列。 思路： 单调栈 C1 n小模拟暴力O(n^3)也过了 C2是在C1的基础上优化。 我们遍历i，默认i为最小值，求左侧的面积（假设宽都为1） 再反向遍历求右侧每个i对应点的面积 将两个面积加起来-掉i那块的面积(不然的话会算两个i那块的面积，这是个坑点） 然后找出最大的面积所对应的下标，给其左右分别取min，得出新序列并输出即可。 还有一个坑点是：栈可能为空 #include<bits/stdc++.h> using ...

B. Homecoming 题意：  A->B 花费a元 B->A 花费b元 有p元 求要走到点i，从i上车能在p内到终点。 思路： 1.二分答案 2.倒着模拟 3.dp dp其实也是倒着模拟 比赛的时候我两种都想到了，问题在于代码实现能力过弱，有必要加强模拟的训练了。 //二分答案： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll mod = 1e9 +7; const ll MAXN = 1e6 + 5; l...

D - Three Integers 题意： t组样例每组输入a,b,c;你可以任意给某个数+1 或-1记为一次操作，求满足b能被a整除，c能被b整除的条件下，操作次数最少。 思路： 暴力出奇迹，打表过样例~，这道题直接暴力就能过。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll mod = 1e9 +7; const ll MAXN = 1e6 + 5; const int N=10500; int main(){ ios...

D - Pairs 题意： 给你n个数，一共有n(n-1)个乘积，求第k大的数是多少。 n最大有2e5 思路： 二分里面套二分 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll mod = 1e9 +7; const ll MAXN = 1e6 + 5; ll n,k; ll a[MAXN]; //判断在当前的数之前有多少个数 ll check(ll x){ ll res=0; for(int i=0;i<n;i++){...

D - Maze Master 题意： 从’.‘到’.'的最大距离。 思路： BFS 这道bfs无起点无终点，数据范围小，所以遍历所有的bfs取bfs结果的最大值即可。 思路很明确，但是自己因为太久没做bfs的题代码实现能力有点弱，太慢了，要做一个优秀的Acmer不仅要头脑清楚，还要有fast coding的能力。 #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algor...

POJ3009 题意： 冰壶游戏从2开始到3，直线走，出格子算输，打到障碍物才停下来，到终点也会停下来，<=10步到终点则算胜利，记录最小步数，失败输出-1. 思路： dfs 于之前一步一步走的dfs不同的地方是，需要判断是否能走该方向，然后套一个while循环来一直走下去直到碰到1停下来或者碰到3记录答案。 反思： 我一开始做成了bfs，想嘛步数最小。 但实际上dfs也可以实现最小步数，每次到终点的时候对结果取min即可。 dfs所谓的一步不是代表只能走一格，而是代表可以走到下一个状态。 #include <iostream> #include <cstdio>...

二进制枚举： void binary_enum(int n){ for(int i=0;i<(1<<n);i++){//枚举0到2^n-1的状态 for(int j=0;j<n;j++){ if(i&(1<<j)){ }else{ } } } }  __builtin_popcount(i) 统计i二进制中1的个数 牛客练习赛58 C-矩阵消除游戏 思路： 二进制枚举 优化： 这里要注意不能枚举所有的行和列，枚举完行的个数为tot，接下来选剩下(k-tot)个最大的列的和即可，否则会TLE。 #include <bits/stdc++.h&gt...

牛客练习赛58 D-迷宫 思路： 棋盘dp #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <map> #include <stack> #include <set> using namespace std...

2020牛客寒假算法基础集训营5 F-碎碎念 思路： 数位dp + 前缀和 #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <map> #include <stack> #include <set> usi...

B - Journey Planning 思路： 找规律 当时想了很久想了个O(n^2)的dp，然后想如何优化，其实这些数减去他们下标的差值是一样的。 Ci+1-Ci=Bi+1-Bi Ci+2-Ci+1=Bi+2-Bi+1 Ci+1-Bi+1=Ci-Bi构造同一个数组存放即可 #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include &l...

C - Guess The Number 思路： 特判 模拟 #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <map> #include <stack> #include <set> using name...

2020牛客寒假算法基础集训营6 B-图 思路： 记忆化搜索dfs 分析可知图为出度为1的基环内向树森林，从一个点出发，沿着出边一路走下去，一定会走到一个环。 所以我们选择dfs，当遍历到一个已在dfs栈中的节点时，就说明找到了环，可以结束统计。 但这样是会超时的，于是我们选择带“记忆化”的dfs，从一个点开始沿着出边走下去，每当走到一个在之前某次dfs中经过的点时，就可以利用上一次的答案完成求解。 #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib&gt...

2020牛客寒假算法基础集训营5 G-街机争霸 关键点： 僵尸的坐标需要三维 平面+时间 利用僵尸移动的周期性检查是否存在僵尸 思路： BFS 这和之前做的BFS最大的区别在于，有僵尸干扰，且僵尸会动，但我们不难发现僵尸的移动是有一定的周期的，周期为2k-2，且人要一直跑不能停，那人跑的步数就可以等效为时间，我们要在原先BFS的基础上加上一维坐标表示时间，因为僵尸的移动是符合周期的，我们可以取余，初始化僵尸移动的周期。 #include <iostream> #include <cstdio> #include <cstring> #include <...

C. Kuroni and Impossible Calculation 题意： ∏1≤i<j≤n|ai−aj| 范德蒙行列式的值为多少？ 心得： 我这个人是一个很马虎的人，这样是不对的，以后读题要快准狠，抓住关键点。 这道题就是这样，关键点在于1≤m≤1000，我觉得慢了一个多小时才写出来这题的原因就在于读题没抓住要点，作为一个好的ACMer以后读题不仅要快，还要找寻不一样的烟火（key）。 思路： 鸽巢原理（抽屉原理） 当n>m 直接输出0 因为取模后必有重复 检验是否取模后有重复，若有则输出0，若无则暴力输出结果即可。 WA了一发 实在是不应该 以后要学一下怎么写对拍 随机数...