rk_no

题解

/ 注册

全部文章 / 题解（共71篇）

Growth(预处理+记忆化搜索)

题目：弱弱有两个属性a和b，这两个属性初始的时候均为0，每一天他可以通过努力，让a涨1点或b涨1点。为了激励弱弱努力学习，我们共有n种奖励，第i种奖励有xi，yi，zi三种属性，若a≥ xi且b≥ yi，则弱弱在接下来的每一天都可以得到zi的分数。问m天以后弱弱最多能得到多少分数。数据范围：第一行...

2020-06-30

0 776

队伍配置(背包dp)

题目：给n个人物m个装备，d是最大花费。每个人物和装备都有一个攻击力a和花费b。满足如下条件情况下选出一些人物和装备得到最大的攻击力：（1）人物数量>=装备数量（2）人物花费+装备花费<=d（3）人物数量<=5数据范围：0<n,m≤300，25≤d≤138，1000≤a1≤...

2020-06-24

1 940

旅游（树形dp，树上最大独立集）

题目：给一个树形城市网络。一开始住在s城，第一天游览距离s城≤1的城市，然后住进另一个未游览的城市，第二天重复游览步骤。问最多能游览多少天。做法：题意转化一下，让你选尽量多的城市，使城市之间两两不相邻。这就是树上的最大独立集问题。树形dp，dp[u][0/1]表示点u选/不选时，子树u下的最...

2020-06-12

0 639

德玛西亚万岁（状压dp）

题目：给一个n*m的01矩阵。1代表可以安放士兵，0代表不能。士兵不能安放在相邻的位置（上下左右）。问有多少种安防士兵的方案。答案对1e8取模。n，m最大12 做法：看n，m的数据范围，这是状压的数据范围。题目只问士兵的方案数，没有限制士兵的数量。所以我们直接对每一行的状态进行枚举，一行一行转...

2020-06-12

0 641

[CQOI2010]扑克牌(二分)

题目：你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 ...

2020-06-12

0 689

Protecting the Flowers（套路贪心）

题目：花园里有n头牛，每头牛有ti和di。代表将它迁回家要花2*ti时间，而呆在花园里每单位时间消灭di朵花儿。问你按什么顺序牵牛使被消灭的花儿总数最小。输出最小总数。做法：相邻两头牛的顺序不影响除它们之外的所有牛的贡献，这是典型的贪心。若牛A排在前面比牛B排在前面优，可以列出如下式子：移...

2020-05-27

0 659

货币系统（完全背包）

题目：给你n个数的正整数集合。让你挑选最少的数，使两个集合等价。集合等价，即两个集合能表示的数的集合相同。做法：由于给的都是正整数。题目就是让我们求给定的n个数中，哪些数是不必要的。所谓不必要，即某个数能被集合中的其他数表示。我们将集合a[]排序。若a[i]能被前i-1个数中的某个子集表示，...

2020-05-27

0 679

[JSOI2007]建筑抢修（贪心，优先队列）

题目：有n个建筑待修理。修理第i个建筑用时，修理它的截止日期是。只有在截止日期前修好某个建筑才算修好。现在问最多能修好多少个建筑。做法：这题是个贪心。我们将截止日期排序。从前往后处理。当前修建筑的总用时时，选择修第i个建筑，而当时。我们就看需不需要用当前的建筑替换之前修过的建筑。很显然如果之...

2020-05-25

0 657

图的遍历(二分图)

题目：小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历...

2020-05-21

0 567

[CQOI2009]中位数图（思维+前缀和）

题目：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。对于 1100% 的数据中，满足n≤100000,1≤b≤n。做法：第一时间想着stl暴力搞搞，但写着写着发现没必要写这么麻烦。后来补了个简单写法。（但是时间居...

2020-05-21

0 667