题号 NC19997名称 [HAOI2016]字符合并来源 [HAOI2016] 题目描述 有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 样例 输入 3 2 101 1 10 1 10 0 20 1 30 输出 40开始字符串为101 将前两个字符"10"合并成1，获得的10分，当前字符串为11 接着将”11“合成1，获得30分，当前字符串为1已经不能再合并了 总得分为40算法 (区间dp + 状压dp) ​首先答案要求的是最大的收益，且分数w[i]都是正值，而如果一个...

题号 NC19989名称 [HAOI2012]容易题(EASY)来源 [HAOI2012] 题目描述 为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下： 有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i]不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 mod 1000000007的值，是不是很简单呢？呵呵！ 样例 输入 3 4 5 1 1 1 1 2 2 2 3 4 3 输出 90样例解释 A[1]不能取1 A[2]不能去2、3 A[4]不能取3 所以可能的数列有以下12种 数...

题号 NC200214名称 石子搬运来源 牛客练习赛59 题目描述 有n堆石子，第i堆石子的石子数量是ai，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是k，那么这堆石子将对牛牛产生k^2的负担值。牛牛最多只能搬运m次，每次搬运可以从一堆石子中选出一些石子搬回牛客，每次搬运不能同时从两堆石子中选取石子，每次只能搬运整数个石子。牛牛是一只聪明的牛，他想出了一种搬运计划可以最小化他搬运完这些石子的负担值的总和，但是突然牛牛的死敌牛能出现了，牛能每次可以施展以下的魔法： ​ x v将第x堆石子的数量变为v 这打乱了牛牛的计划，每次牛能施展一次魔法，...

题号 NC24623名称 Tree Decoration来源 USACO 题目描述 给你一棵有根树，根节点为1，第i个节点有ci，ti两个值ci表示以第i个节点为根节点的子树装饰物的数量至少为ci，ti表示往第i个节点挂上一个装饰物需要ti的时间，问在满足所有ci的条件下，最少的花费时间是多少？ 样例 输入 5 -1 9 3 1 2 2 5 3 2 5 1 4 2 3 3 输出 20 1 | 2 | 5 /...

题号 NC106586名称 The Cow Lineup 题目描述 给定一个长度为n的序列A，和数值范围k，找到一个最短的在A中不存在的子序列，并输出长度 样例 输入 14 5 1 5 3 2 5 1 3 4 4 2 5 1 2 3 输出 3原序列：[1 5 3 2 5 1 3 4 4 2 5 1 2 3] ,其中长度为1的所有可能的子序列[1,2,3,4,5]在原序列中都能找到, 长度为2的所有可能的子序列 [11,12,13,14,15, 21,22,23,24,25, 31,32,33,34,35, 41,42,43,44,45, 51,52,53,54,55] 在原序列中都能找到 而长...

题号 NC25044名称 Tallest Cow来源 USACO 题目描述 有N头牛站一排 ，只有当两头牛之间的牛的身高都比他们矮是这两头牛才能相互看见，已知n个牛中最高的牛的高度h，以及r组可以相互看见的牛，问这n牛每一头牛最高是多少，并且保证满足这r组牛可以相互看见。 样例 输入 9 3 5 5 1 3 5 3 4 3 3 7 9 8输出 5 4 5 3 4 4 5 5 5算法 (差分 + 贪心) 假设r = 0，则最优的情况就是所有牛的身高都为h，假设r = 1，则第i头牛和第j头牛可以相互看看见，则最优的情况就是[i + 1,j - 1]这个区间内的牛的身高，都变成h-1，在r = 1...

题号 NC200195名称 区区区间来源 牛客小白月赛20 题目描述 给定一个序列，有两种操作： 1 l r k:将区间[l,r]变成[k,k + 1,...,k + r - l] 的序列 2 l r:将区间求区间[l,r]的区间和 样例 输入 5 5 1 1 1 1 1 2 1 5 1 1 5 1 2 1 5 1 1 3 3 2 1 3 输出 5 15 12 算法1 (线段树维护区间和 和 覆盖问题) 很容易观察到操作1是将一段区间变成一段等差数列，因为等差数列的通项为：a[i] = a[i - 1] + d（1），也可以写成:a[i] = a[1] + (i - 1)d（2）,如果将等差数...

打卡