题号 NC15748名称 旅游来源 牛客小白月赛3戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 这是比较典型的树型dp，因为是从s开始走，我如果把s看成根节点的话，可以知道如果父亲节点住了，那么他的儿子节点就一定不能住，如果父亲节点没有住，那么儿子节点可住可不住。所以我们用f[i][0/1]表示第i个点住/不住的在这棵子树上能呆的最长时间。 j是i的儿子。由于根s是必须住的，所以答案就是f[s][1]。这个问题其实是典型的树的最大独立集，与此类似的还有树的最小点覆盖、最小支配集问题，希望有兴趣的学有余力的同学能自行探索...

请在比赛结束以后在发布题解，欢迎提前占坑~   比赛名称：“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)    官方题解；https://ac.nowcoder.com/discuss/434243   赛后补题可以让自己变的更强      活动具体内容    5月31日18:00-6月10日12:00，写“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量       比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下       活动奖励：    在牛客博客中写题解，并回...

请在比赛结束以后在发布题解，欢迎提前占坑~   比赛名称：2020年第十四届山东大学程序设计竞赛（重现赛）   赛后补题可以让自己变的更强      活动具体内容    5月30日18:00-6月9日12:00，写第十四届山东大学程序设计竞赛（重现赛）题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量       比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下       活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在6月9日下午审核，并给每篇题解发放5-40牛币        PS: ...

请在比赛结束以后在发布题解，欢迎提前占坑~   比赛名称：厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛）   官方题解：https://ac.nowcoder.com/discuss/435384   赛后补题可以让自己变的更强      活动具体内容    5月30日18:00-6月8日12:00，写厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛） 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量       比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下       活动奖励：    在牛客博客中写题解，并回复地址，如果写...

牛牛有两个字符串（可能包含空格）,牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。 输入描述:输入为两行字符串（可能包含空格），长度均小于等于50. 输出描述:输出为一个整数，表示最长公共连续子串的长度。 示例1输入  abcdeabgde  输出  2  设第一个字符串为a，第二个字符串为b，dp[i][j]表示a以i结尾的子串和b以j结尾的子串的最长公共连续子串的长度则，如果a[i]==b[j],那么dp[i][j]=dp[i-1][j-1]+1 #include<iostream> using namespace std; int main() { strin...

题号 NC13947名称 contest来源 牛客练习赛2戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 这个题我看很多同学写cdq分治，也是一个很好的方法（学有余力的同学去看看哦），但是这里给大家讲一个简单一点的。我们先考虑如果只有两场比赛：x自己觉得比y强，y自己也觉得比x强其实就是一场比赛x的排名搞另一场y的排名高，如果我们把所有的队伍按照一场比赛的排名排序，那么显然答案就是对应的另一场比赛的排名组成的序列的逆序对的个数。那么现在有三场比赛，我们只需要按照比赛1排序求比赛23的逆序数，再按比赛2排序求比赛3的逆序数...

题号 NC17621 名称 管道取珠 来源 NOI2009比赛真题 戳我进入往期每日一题汇总贴~ 往期每日一题题单   如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情   题解   这个题的难点或者说关键点究竟在哪里呢？ ——弄清楚究竟是什么意思！因为是肯定不能直接算的！（我们考虑把数学式子弄出一个物理意义或者说实际操作的意义） 表示：如果有两个相同的装置同时进行取珠子的操作，两个装置取得相同的序列的方案数有多少。 想想哈：ai是组成第i个序列的方案数，那么 是两个装置都取得第i个序列的方案数是理所当然的哈！ 这样就简单了，f[i][j][k] 表示已经取了i个珠子，第一...

题号 NC25043名称 Protecting the Flower来源 USACO英文版-2007 January Contest-Silver戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 题意：一共有n只牛在花坛旁边，第i头牛每分钟破坏di朵花，把第i头牛带回牛棚需要2 \times ti这么多时间，每次只能带回一头牛，请问怎样能使得被破坏的花最少。思路：这是非常经典（套路）的贪心（国王游戏就是这么做的呀！）首先我们知道，交换相邻两头牛的顺序既不影响前面的牛破坏的花的数量也不影响后面的人破坏的花的数量。那么假设如果...

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

题号 NC21228名称 货币系统来源 2018NOIP复赛-提高组Day1戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 首先我们要想到，最后的最小的货币系统应该是原货币系统的一个子集，原因也很简单——如果a能够用其他一个或若干个面值表示那么它显然不必要，而如果你去引入一个原来不存在的数那么要么是多于的（能被原来货币系统里面的一个或多个数表达）要么就会引入新的东西。所以现在我们要做到就是在刚刚的集合里面求所有必要的无法被替代的货币数量。显然，最小的数肯定要留下，因为其他数字肯定表示不了它。然后第二大的数，如果是最小的数...

请在比赛结束以后在发布题解，欢迎提前占坑~   比赛名称：2020年牛客算法入门课练习赛1   出题人：邓丝雨   赛后补题可以让自己变的更强      活动具体内容    5月25日21:30-6月1日12:00，写2020年牛客算法入门课练习赛1 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量       比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下       活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在6月1日下午审核，并给每篇题解发放5-30牛币       ...

题号 NC20154名称  [JSOI2007]建筑抢修来源 [JSOI2007]戳我进入往期每日一题汇总贴~往期每日一题题单 如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情 题解 这是一个典型的“给程序留一个后悔机会”的贪心。我们按照任务的截止时间排序，通过之前的维修时间+这个建筑要修的时间是不是小于等于规定截至时间来判断能不能修好，但是这样的话会出现一个最晚截止时间早但是维修时间长的占了太长时间，比如：有三个任务最晚截止时间和维修时间分别是：A：10，9 ；B：11，6；C：12，4，显然我们去完成BC就比去做A要好，这种情况怎么办呢？我们先还是去尝试完成A，然后这个...

请在比赛结束之后再发布题解，欢迎提前占坑~   比赛名称：第十五届中北大学算法与程序设计竞赛（公开赛）   赛后补题可以让自己变的更强      活动具体内容    5月24日18:00-6月3日12:00，写 第十五届中北大学算法与程序设计竞赛（公开赛） 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下~      活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在6月3日下午审核，并给参与活动的同学发放10-100牛币     PS:...

请在比赛结束之后再发布题解，欢迎提前占坑~   比赛名称：西安邮电大学第五届ACM-ICPC校赛（同步赛）   赛后补题可以让自己变的更强      活动具体内容    5月23日18:00-6月3日12:00，写 西安邮电大学第五届ACM-ICPC校赛（同步赛） 题目的题解，即可获得牛币~   发放牛币的数量取决于题目难度，题目数量，题解质量   比赛结束之后点击每题后的进入题解->写题解，博客会被收录在每道题目之下~      活动奖励：    在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~ 我们将在6月3日下午审核，并给参与活动的同学发放10-100牛币    ...