比赛名称：牛客OI周赛15-普及组 出题人：Evenifeverything 戳我进入官方题解~ 有问题可以回帖询问出题人 赛后补题可以让自己变的更强 活动具体内容 4月3日21:00-4月10日中午12:00，写牛客OI周赛15-普及组 题目的题解，即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 活动奖励： 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在4月10日下午审核，并给参与活动的同学发放10-80牛币 PS...

题号 NC13886名称 Shortest Path来源 西南交通大学第十三届ACM决赛戳我进入往期每日一题汇总贴~ 简单说一下汉语题意： 给你一棵 个节点的树（保证 是偶数），你需要将 个节点分为 个点对，使得每个点对的两个点的距离的和最小。 首先我们可以通过观察得到以下几点： 首先，在最短的距离和之中一条边一定不会被覆盖两次，如图，我们一定可以找到一种方法来交换配对，把重复的边去掉（其他的边是不会变的）。也就是说对于一条边来说，其实只有选和不选两种可能。 第二，对于一个点x，它子树中的点一定会尽量在子树中找到匹配的点内部消化掉（要么连父亲要么连兄弟），只有根是有可能会往上...

题号 NC23053名称 月月查华华的手机来源 牛客小白月赛12戳我进入往期每日一题汇总贴~ 暴力的话是但是这样也太暴力了。 这就是个简单的枚举优化，不要认为有多么的复杂高深（学算法最忌讳自己吓唬自己，你怕了就已经输了）。 我们可以观察，比如主串（华华的昵称）是，子串（小姐姐的昵称）是 ，那么当 匹配上了之后，再去枚举主串中的 其实是没有意义的，如果我们能做到在 之后跳到 后面第一个 然后在 之后跳到后面的第一个 （如果有的话），直到子串遍历完或者跳不动了，就能出结果了。（如果主串中有两个一样的字母，我们肯定会选前一个，因为是子序列，如果选前一个不可以，那么选后面的同一个字母...

题解赛后在本贴更新~ 本场比赛出题团共有7位不愿意透露姓名（怕被毒打）出题人 （所以可能就由我代发题解了， 希望大家玩的开心~ 出题人1：某不知名的J姓出题人：我只出了一个题，别打我。 出题人2： 出题人3： 出题人4：不愿意透露姓名 出题人5： 出题人6：我答疑就全问的正式问题 想和选手聊天 出题人7：可爱即正义！ 以下是题解~ A rand36 欧皇概率检测（坑罚时题 下面是各数字的概率 0-9 10/37 10-19 10/37 20-29 1...

题号 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++) { ...

三月比赛公示 比赛名称 比赛时间 出题人 牛客OI周赛14-提高组 3月7日  18:00-21:30 恋恋天下第一 牛客OI周赛14-普及组 3月7日  18:00-21:30 deco 牛客练习赛59 ...

签到题 说明：本分类是比赛中较多人做出的题目，萌新可以从本分类开始练习 练习赛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 「水」滔天巨浪 数列 ...