https://ac.nowcoder.com/acm/contest/5758B：减成一 分析：1.如果前面那个数比这个数大，那直接跳过，因为前面一个数可以带它躺成1。2.如果前面那个数比这个数小，那区间是只能扩到前一个数这么大，因此还要进行多余的操作使自己变成1，于是产生了(a[i]-a[i-1])代价。代码： #include "bits/stdc++.h" using namespace std ; typedef long long ll; ll t,n,sum; ll a[100005]; int main(){ cin>>t; while(t--){ cin>&...

https://ac.nowcoder.com/acm/problem/15748题意：有n个节点n-1条边，由s节点开始，之后每次选择的节点不能选择之前的选择过的节点及其相邻节点。 分析：n个节点，n-1条边，由s节点开始选择，很明显是一颗以s节点为根节点的树，这是一道树的最大独立集问题，由于n数据有5e5，显然根据数进行暴力搜索可能不太行，我们要用dp对它进行优化，这就是所谓的树形dp了，对树进行动态规划，对此题而言，由子节点推到父节点，即根的子节点传递有用的信息给父节点，最终由父节点再求出最优解。而每一步的状态只有选择住宿还是不住宿（取或者不取），因此状态转移方程为：dp[u][0/1]...

题意：有n支队伍参加n3场比赛，一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高，也就是互相赢过对方，这样算一组（x,y），试问存在多少组？ 分析：我们首先想到的思路是将第一场比赛进行排序，保证i自认为比i+1强，然后寻找后面比赛存在多少组j比j+1强，这样暴力下来复杂度要O（n^2），常熟还很大，显然会TLE,那么我们想一想怎么优化这种暴力。我们先从总情况上考虑，符合队伍的x，y三场比赛后可能两种情况：rankx>ranky2次或者是rankx<ranky2次，那么我们统计这些情况出现的次数cnt，因为满足情况的（x,y）两种情况都会统计一次，存在重复，所...

https://ac.nowcoder.com/acm/problem/25043题意：有n头牛要***漂亮的花朵，已知每头牛迁回牛舍的时间以及每分钟***花的数量，问最少要损耗多少花才能遏制这种行为。 分析：出于保护美的渴望，这种止损的行为下意识贪心了起来，脑瓜不够用先简化一下问题，假设只有2头牛，如果我们牵第一个回去，那么损失花朵数量=第一个迁过去来回的时间*第二个每分钟***花的数量，如此看来，我们要比较排序每头牛迁回牛舍的时间与之后牛吃花的速度，如此进行贪心选择。 代码： #include<stdio.h> #include<algorithm> #includ...

https://ac.nowcoder.com/acm/problem/21228题意：有n种货币，每种货币数量无限，问能否删掉几种货币，使得原来能组成的数现在仍能组成。 分析： 想要去掉某种硬币，说明它可以被一种或多种面值比它小的货币所组成，一个或多个的和能组成某一个数，明显的背包问题，而且每个类型的货币数量无限，因此这题是一个完全背包问题。由于每个货币只能由面值比它小的共同组成，所以我们应该先对给定货币面额进行正序排序，然后一个个判断拿还是不拿，如果发现当前面额能被组成，我们直接不管即可，如果发现不能组成，则进行状态转移把它范围内能组成的所有数标记一下即可。状态转移方程为：dp[j] = ...

https://ac.nowcoder.com/acm/problem/20154题意：已知每个建筑的报废时间和维修时间，只有一个人去维修，问最多能维修多少建筑？ 分析：典型贪心题，我们要在规定时间内维修尽可能多的建筑，大体上先贪心一下，先维修截止时间迫在眉睫的建筑，那么怎么判断当前是否可以进行维修呢（别瞎忙了一阵子发现时间不够），所以我们应当先计算之间花费的时间+维修该建筑所需要的时间是否小于等于结束时间进行判断当前建筑是否能维修。可这样贪心下去，万一有个建筑迫在眉睫但却要占用你全部时间去维修，这样去做不是得不偿失吗？ 所以当有一个建筑判断为时间不够维修时，不要把它轻易放弃，前面的可能有些建...

https://ac.nowcoder.com/acm/problem/19913 题意：给你一个排列和一个数字b，问数组中有多少连续奇数子序列的中位数为b。 分析：我们首先想到的方法是找到数字b的位置，然后从该位置向两边左右枚举取数判断是否合法，但1e5的数据显然这么做会超时，所以我们适着转换一下思路，对于该题而言，我们只在乎数据相对于数字的大小，而不在乎其具体值多少，那么我们可以把大于b的数字都看成1，而小于b的数字都看成-1，等于b的数字取中看成0，因为b为中位数，所以它左右两边数个数相等，因此该合法区间和为0. 那么我们可以找出b的位置，向左计算数据和，开个桶存放一下数据和的个数（数组...

https://ac.nowcoder.com/acm/problem/52275 题意：需要加多少条边才能使从1开始遍历整张图？ 分析：先从简单的问题进行考虑，假设每次都只能走1步，那么需要加多少条边才能遍历完呢，显然要把全部点都连通起来，因此需要加的边数就是（连通块的数量-1）条边。如果每次只能走2步，在图刚好全部连通的基础上作图发现，无论从那个点出发都无法遍历全图，总会剩下一半的点遍历不到，某些点（偶数或者奇数点）给跳过去了，这种情况下我们加一条边形成奇数环可以把点转移到另一种性质的点上（奇数偶数转化），从而能遍历整张图了，不太明白的自己画图看看就知道了。因此，只要我们发现，只要图连通且...

https://ac.nowcoder.com/acm/contest/5713/A题意：给定物品坐标与初始坐标，求收集完所有物品再回来的最短路径 分析：看一下题目数据，最多只有10张卡片，数据很小直接枚举就行了，用dfs全排列搜索，记录每个方式的路径，取最小值即可。复杂度O(10!) #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<map> #include<queue> using namespace ...

https://ac.nowcoder.com/acm/problem/14585 题意：只能通过移动到相邻位置的汉诺塔问题。 汉诺塔讲解：有三根A,B,C相邻的柱子，A柱子从上到下按递增方式摆放了n个不同大小的圆盘，现在要把A中所有的盘子移动到柱子C上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，盘子只能移动到相邻的柱子上。（比传统汉诺塔多了最后一个限定条件）具体移动实现方式还是一样用递归的思想： 1：当只有一个圆盘时，移动方式为：A->B,B->C2：当只有两个圆盘时，移动方式为：把最上面的盘子1移动到B，再把盘子1移动到C。把下面的盘子2移动到B，然后把盘子1移动回...

https://ac.nowcoder.com/acm/problem/14266 题意：找出某种电脑内存和速度比另一台电脑都低的数量 分析：枚举模拟一下题意就行了，锤爆牛客评测机，n^2都能过1e5。 代码： #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<map> #include<queue> using namespace std; typedef long long ll; int i,j,cnt...

https://ac.nowcoder.com/acm/problem/14734 题目理解：题意很简单，就是给你12道题3种途径的概率，求解决0~12题的概率。 题目分析：正着求每道题解决的概率，显然有点困难，那么我们不妨逆向考虑一下每道题无法解决的概率，答案显然 fail[i]=(1-a[i])(1-b[i])(1-c[i]) ** (fail[i]表示第i题无法解决的概率)，之后就可以得知每道题成功的概率ac[i]=1-wa[i]。注意一下数据，总题数才12道，直接暴力dfs就行了，复杂度O(n^2)，稳过，放弃思考dp了。 代码： #include<stdio.h> int...

https://ac.nowcoder.com/acm/problem/53676题意：给定一个由01字符串矩阵，求包含1的k*k矩阵个数。 分析：地图大小为10001000，枚举kk矩阵即可，若矩阵数字和不为0，则ans++ 求区间和我们首先想到前缀和，可以O（1）查询区间和，感觉和昨天的题差不多，把字符数组转化为整形数组，前缀和预处理下然后查询即可，只不过这题要用到二维数组的前缀和。sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+b[i][j] 具体实现自己画个矩形图模拟下就可以理解了，本质上和一维数组差不多。 代码： #include&lt...

题意：走迷宫，有传送阵，移动花费1秒，传送花费3秒，求到达终点的最短时间。 思路：最短路问题，首先想到的是Dijkstra算法，但是题目数据不大，建图起来麻烦（其实不会），所以我们直接用bfs跑一便就行了，一个多了几个传送阵的迷宫问题，丢进优先队列里搜索时特判一下就行了，一些细节的说明在代码上有注释说明了。 代码： #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<queue> using namespace std; ...