题号 NC14683名称  储物点的距离来源 牛客练习赛8戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 因为在数轴上，求任意两个点的距离只需要先维护一个距离的前缀和就行了。同理求某个区间内物品数量也可以前缀和。如果我们固定了目标点是很简单的，再求个前缀和就行。但是这里的目标点显然需要枚举——我们并不希望枚举的时候在每一个目标点都算一遍整个区间。我们来考虑目标点从i右移一位到i+1的时候会发生什么变化——如果[l,r]在i和i+1右边，显然[l,r]当中的每个物品都少移动了i到i+1的距离，只需要在i点的答案基础上减去[...

题号 NC15665名称 maze来源 2018年湘潭大学程序设计竞赛戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 这是一个很直接的题。如果没有传送带的话这显然是一个广搜，有了传送带之后，因为传送过程花费3秒，继续使用广搜的话先搜到的点未必是到达的，这样就会出错，一个很简单的方法是——把广搜的队列换成优先队列，保证出队的点都是当前距离起点最近的。然而还有个更直接的方法是直接建图然后上最短路板子。 看完邓老师的题解，记得自己去做题提高呀~欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！ 活动奖励：  在牛客博...

比赛名称：牛客算法周周练6   赛后补题可以让自己变的更强   活动具体内容    5月12日21:30-5月19日中午12:00，写牛客算法周周练6题目的题解，即可获得牛币~   建议将题目分开写，在发表博客的时候类别选择题解，并输入本题地址，这样在题库刷题的小伙伴也可以看到你的题解~   发放牛币的数量取决于题目难度，题目数量，题解质量   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在5月19日下午审核，并给参与活动的同学发放10-80牛币     PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@...

题号 NC16681名称 加分二叉树来源 NOIP2003提高组复赛戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 我们知道，中序遍历中根的左边是左子树，右边是右子树，那么我们对每一颗子树都可以枚举根节点在哪里。f[i][j]表示中序遍历中第i个点到第j个点是一颗子树，这棵子树的最大加分。枚举这棵子树的根k，显然然后循环或者记忆化搜索都可以。注意边界，k==i或者k==j的时候的情况。关于本题的复杂度，递归似乎不是很好算，有个比较简单的计算方法是这样的：最后所有区间f值都要算出来，这个的显然就已经了，而算每个区间的时候还...

题号 NC14698名称 模拟战役来源 中国矿业大学（北京）第二届ACM程序设计公开赛（决赛）戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 首先我们要知道，如果a会引爆b那么b也会引爆a，也就是说我们可以把大炮分成若干个连通块，每个连通块内部只要一个被引爆找个连通块肯定就都炸了。这个用dfs/bfs/并查集都可以实现。现在，我们求出来了齐齐和司机的每个连通块的大小和连通块个数，如果齐齐能摧毁司机的所有大炮那么他的联通块个数不能比司机的少。那么在齐齐在能摧毁所有司机的情况下能最多剩下几门大炮呢？显然齐齐会有限选择损失少的...

比赛名称：“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛   赛后补题可以让自己变的更强      活动具体内容    5月10日17:00-5月16日12:00，写 “科大讯飞杯”第十七届同济大学程序设计预选赛题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在5月18日下午审核，并给参与活动的同学发放10-100牛币     PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@王清楚 会减少获得其获得的牛币  ...

题号 NC24158名称 Moovie Mooving来源 USACO英文版-2015 January Contest-Gold戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 题意：有 N 部电影，每部电影有不同的放映时常，和若干个放映起始时间。Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。每部电影她最多看1次且她不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。Bessie 能不能从0到L分钟连续不断地观看电影？如果能，计算她最少看几部电影。 ()英文题大家都不想做？看到N这个范围，大概...

比赛名称：牛客练习赛63    出题人：四系智乃   戳我进入官方题解， 有问题可以回帖询问出题人~    赛后补题可以让自己变的更强      活动具体内容    5月8日19:00-5月15日12:00，写牛客练习赛63题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量       比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下       活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在5月15日下午审核，并给参与活动的同学发放10-100牛币        PS:     如果题解...

题号 NC16655名称 过河来源 NOIP2005提高组复赛戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 先不考虑开不下数组的问题如果我们用f[i]表示走到i这个位置的最小的踩石子的次数话i这个位置没有石头：f[i]=min(f[i],f[k])i这个位置是石头：f[i]=min(f[i],f[k]+1)(k是上一步的位置，)现在我们来解决桥太长了数组开不了的问题，我首先仔细看数据范围，相对于桥长度L，石头个数和青蛙跳跃范围S，T都是很小的，也就是说总是存在一些石头离得非常远，从前一个石头到这个石头需要跳很多步才能到...

题号 NC14844名称 codeJan与旅行来源 Wannafly挑战赛7戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 这题中，我们不难证明，那么最后我们一定会在两个点直接徘徊或者直达某个点。证明如下：若不在两点间徘徊有最短距离，设我们走的点的序列为: (对于)那么走的距离就是: 那么，对于其中的最小的那个来说我们如果一直在和两个点间徘徊直到走的点的个数等于这个策略用的距离就是: 明显的这个距离是小于等于上面的距离的，与我们假设不符合，所以，我们最后一定是在两点间徘徊的（若k=t的话，就是直达某个点了）所以，我们可以考虑枚...

题号 NC53683名称 「火」皇家烈焰来源 牛客小白月赛19戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 显而易见的dp，你会发现，转移和前一位、当前位还有下一位是不是烈焰有关，而前一位是什么可以在转移中题现，所以：f[i][0/1][0/1]表示前i位，当前位和下一位是（1）不是（0）烈焰的方案数 转移方程分情况讨论： 当s[i]='*'时， 该位是1，上一位和下一位都随意（所有组合都可以）:f[i][1][0]=(f[i-1][0][1]+f[i-1][1][1])f[i][1][1]=(f[i-1][0][1]...

比赛名称：牛客算法周周练5   赛后补题可以让自己变的更强   活动具体内容    5月5日21:30-5月12日中午12:00，写牛客算法周周练5题目的题解，即可获得牛币~   建议将题目分开写，在发表博客的时候类别选择题解，并输入本题地址，这样在题库刷题的小伙伴也可以看到你的题解~   发放牛币的数量取决于题目难度，题目数量，题解质量   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在5月12日下午审核，并给参与活动的同学发放10-80牛币     PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@王...

比赛名称：武汉工程大学2020GPLT选拔赛（重现赛）   戳我进入官方题解~   赛后补题可以让自己变的更强      活动具体内容    5月3日17:00-5月11日12:00，写 武汉工程大学2020GPLT选拔赛（重现赛）题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在5月11日下午审核，并给参与活动的同学发放10-100牛币     PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@王清楚 会减少获得其获得的牛...

题面描述 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 题解 如果已知以位置$结尾的子数组的最大和，怎么求以位置i结尾的子数组的最大和呢？  一种情况是把这个位置的数和前面的子数组加起来 另一种情况是不要之前的子数组。只要位置上的这个数  这样遍历一遍之后就可以得到以每个位置结尾的子数组的最大值了，然后这里面最大的那一个就是题目所找的具有最大和的连续子数组。 #include<iostream>...