题号 NC22598   名称 Rinne Loves Edges   来源 牛客小白月赛11   戳我进入往期每日一题汇总贴~      昨天的题似乎有点难，写题解的人都少了……今天来个简单一点的基础题。  注意备注里面说：M=N-1（读题一定要看备注！），题面说是个无向联通图，这就告诉我们实际上这就是一棵树。而题目中说到的度数为1的点实际上就的叶子节点。  现在问题就变成了：在以S为根的树上删掉权值和尽量小的一些边使得根和每一个叶子节点都不连通。  这是一个典型的树型dp，而树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。  不管是写dp还是写搜索其实都是要分析原问题...

题号 NC13331   名称 城市网络   来源 美团2017年CodeM大赛-复赛   戳我进入往期每日一题汇总贴~   首先给大家道个歉，最开始这题数据有点问题，把什么暴力都放过去了……现在数据锅已修，请之前使用暴力，最坏可能达到O(nq)的算法的同学去重测一下呀！真的十分抱歉！  我们来先说说大家都喜闻乐见的暴力，因为题目说保证 v 在 u 前往根的最短路径上，所以只要一遍dfs维护出每个点的父亲，然后每次顺着父亲一路走上去就可以了，这个的复杂度最坏情况是O(nq)的（退化成一条链的情况），是过不了的（出题人一般是不可能放这种复杂度过去的，但是赛场上如果你没有别的办法的时候其实试一下也...

题号 NC50528   名称 滑动窗口   来源 《信息学奥赛一本通》Part5.5   戳我进入往期每日一题汇总贴~      滑动窗口取最值问题是一个非常经典的问题，当然你可使用线段树树状数组ST表等等方法去求，我在这里呢给大家介绍一种时间复杂度，简单实在将来也有很多地方能用的方法——单调队列。  以求最大值为例：  区间的最大值为：  区间右移到后最大值为：  我们可以看到这两段区别仅仅在 和 上，扫一遍显然是很没必要的。而如果 ，那么当进入了窗口中，就不可能作为最大值存在了，如果我们记录当前区间中现在或者将来有机会成为最大值的数，那么就可以从这个记录中删掉了。如果, 当出了区间，还是...

比赛名称： 牛客练习赛60   出题人：Forsaken   戳我进入官方题解~ 有问题可以回帖询问出题人   赛后补题可以让自己变的更强       活动具体内容     3月27日22:00-4月2日，写牛客练习赛60 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量    活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月2日审核，并给参与活动的同学发放10-100牛币      PS:     如果题解写的非常好，@王清楚 将会增加其获得的牛币  如果题解写的非常水，@王清楚 会减少获得其获得的牛币  如果...

题号 NC15553   名称 数学考试   来源 2018年长沙理工大学第十三届程序设计竞赛    戳我进入往期每日一题汇总贴~     给大家提出几个变形的相关问题： 一：不限制长度——在一个数列里找两个不相交区间使得他们权值和最大 二：区间数目变多——找 个长度为 的不相交区间使得他们的权值和最大 () 三：区间数目变多且不限制长度——找 个不相交长度不限的区间使得他们权值和最大()  希望大家尝试思考并解决这个三个问题。      ————————————————以下是本题思路——————————————  因为长度已知，最暴力的办法肯定是直接枚举两个子区间的起点，然后求和，复杂度。 ...

题号：NC13230  名称：合并回文子串   来源：美团2017年CodeM大赛-初赛A轮   戳我进入往期每日一题汇总贴~      ------------------------------------以下是和本题还有点关系的相关知识讲解----------------------------- 首先，我们来复习一下区间dp的经典问题：最长回文子序列（如果你没有学过也不不要紧，我会努力写得容易看懂一些） ——给你一个字符串，求一个最长的回文子序列（可以不连续）。 一般情况下，动态规划的解题步骤是： 第一步：根据原问题和子问题来确定状态（我的dp数组要表示什么东西） 第二步：根据状态确定...

题号：NC50439   名称： tokitsukaze and Soldier   来源：练习赛50-C   戳我进入往期每日一题汇总贴~          题目精讲       ---------------------------------------------------------------分析-----------------------------------------------------------------  如果没有每个士兵的人数限制，显而易见的我们会直接按照武力值大小排序，但是每个士兵对人数的加以了限制，如果我们还是按武力值大小加人的话，每次加人和删掉人都会...

遍历一遍字符串，一位一位的比较即可 #include<iostream> using namespace std; int main() { string S; cin>>S; string s1="XiaoQiao"; string s2="XiaoHuiHui"; int len1 = s1.length(); int len2 = s2.length(); int index1 = 0,index2=0; for(int i = 0 ; i < S.length();i++) { if(S[i]==s1[index1]&&index1<...

三月比赛公示       比赛名称   比赛时间   出题人     牛客OI周赛14-提高组   3月7日  18:00-21:30   恋恋天下第一     牛客OI周赛14-普及组   3月7日  18:00-21:30   deco     牛客练习赛59   3月13日 19:00-22:00   小乔(☆_☆)     牛客挑战赛38   3月20日 19:00-22:00   nocriz     牛客小白月赛23   3月21日 19:00-22:00   ACoder_NWPU      牛客练习赛60   3月27日 13:00-18:00   Forsaken     欢...

签到题   说明：本分类是比赛中较多人做出的题目，萌新可以从本分类开始练习   练习赛58-A 牛能和宝石 贪心,排序   练习赛57-A Tic-Tac-Toe   练习赛56-A 小蒟和他的乐谱   练习赛55-A 等火车   练习赛54-A 乘积   练习赛50-A tokitsukaze and Connection 模拟   练习赛48-A 小w的a+b问题 构造，二进制      小白月赛22-E 方块涂色   小白月赛22-F 累乘数字   小白月赛22-J 计算A+B   小白月赛19-A 「水」滔天巨浪 数列     小白月赛16-B 小雨的三角形   小白月赛16-C 小石...

Nowcoder Contest Rating 系统说明   为了Rating制度的公平性，我们根据比赛的难度设置了分级   规则如下：       比赛类别   计分规则     牛客小白月赛   分数 1500 的选手不计 Rating     牛客练习赛   分数  2200 的选手不计 Rating     牛客OI周赛普及组   分数  1200 的选手不计 Rating     牛客OI周赛提高组   分数  2800 的选手不计 Rating     牛客挑战赛    全部参赛选手均记 Rating        祝各位大佬场场上分~   愿红名与你同在

The 2019 ICPC Asia Shanghai Regional Contest(重现赛)   The 2019 ICPC Asia-East Continent Final   2018 ACM-ICPC EC-Final    2016年        Asia Regionals Contests     The 2016 ACM-ICPC Asia Shenyang Regional Contest     The 2016 ACM-ICPC Asia CHINA-Final Contest     The 2016 ACM-ICPC Asia Dalian Regional ...

好久没写代码了，我太菜了。做一下签到题，结果写的又慢，脑子还转不过来。出题人的题解是排序做的，我没有排序。(其实也差不多判断一个题是签到题一共两个条件，  通过人数大于等于全场人数的80% 通过人数是所有题目前三多的题对于第一点，只需要判断 就好对于第二点，遍历一遍，记录一下有多少题目的通过人数比I题多这个数字小于等于2的话，这道题目就是签到题啦#include using namespace std; int main() { int n,m; cin>>n>>m; int a[20000]; for(int i = 0 ; i< n ; i++) { cin&...

2020牛客寒假算法基础集训营已经开始啦~   欢迎参赛的小伙伴来写出你的感受/建议！   你们的建议是我们改进的方向和动力~    建议回复格式：场次+内容 例：【第1场】感受:XXXXXXXX    我们将抽取6位回复的小伙伴赠送100牛币     开奖日期:2020年2月20日