wxyww

题解

未归档(12) 精品(28)

/ 注册

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

【每日一题】旅游

solution 以为根进行。设表示以为根的子树中，是()否()选择了这个点，这个点是()否()被游览过的方案数。答案就是考虑如何转移。对于，既然这个点没被游览过，那么他的儿子就肯定不能选择，而且因为没选这个点，所以他的儿子就不能通过选择来被游览，所以就只能从转移过来。对于，可以覆盖他的儿...

树形dp

2020-06-01

2 828

【每日一题】Contest

solution 先从三个排名中选择两个，假设是，就是要找对于每个队伍，满足a比他大并且b比他小的队伍有多少个。这就是一个二维偏序的问题，先按照a从大到小排序，这时每个位置左边都满足a比他大，所以从左向右扫的过程中维护一个权值树状数组，每次将一个元素的b***去，并且在树状数组上查询小于当前这个b的...

2020-05-29

1 993

【每日一题】管道取珠

solution 我们可以将问题转化为进行两次游戏，最终输出的序列相同的方案数。为什么可以这么转化呢？我们尝试用式子表示这个新问题，对于一种序列，如果在一次游戏中取到他的方案数为，那么根据乘法原理，在两次游戏中都取到他的方案数就是，那么所有可能序列的方案数之和自然就是了。那这个问题怎么做呢？我们...

动态规划

2020-05-28

1 612

【每日一题】Protecting the Flowers

problem 有n头牛在吃花，第i头牛每分钟吃的花，John每次可以运走一头牛，运走第i头牛需要的时间是。设计一种运牛的顺序，使得被吃掉的花最少。 solution 非常经典贪心题。先考虑只有两头牛的情况。如果先运走，那么被吃掉的花就是，同理如果先运走被吃掉的花就是。所以我们按照排序，然后统计答...

贪心

2020-05-27

1 652

【每日一题】货币系统

solution 想起当年noip赛场上没做出来这道降智题就来气。。。这个题目其实讲的也就是去掉最多的元素，使得剩下的元素可以组成原来可以组成全部数字。仔细想一下，其实就是将原数组排序之后，如果比较大的那个可以被比较小的表示出来，那么这个元素我们就可以删去了。所以我们用表示前i个元素是不是可以组...

背包动态规划

2020-05-26

1 559

【每日一题】[JSOI2007]建筑抢修

solution 显然的，越小的就应该越优先考虑。所以我们先按照从小到大排序。然后我们用记录下现在已经选择的建筑所需要花费的时间。如果加上当前建筑的不大于当前建筑的。那么就直接将这个建筑修复即可。那么如果应该怎么办呢？有两种选择，一种是从前面选的里面踢掉一个(只会踢掉一个，因为每个建筑的贡献都是...

贪心

2020-05-25

1 631

【每日一题】小AA的数列

solution 先对求一遍前缀异或和。首先肯定要按二进制位处理，假设处理到了第x位，然后枚举一个位置，我们就想要查询所有满足且为偶数的中满足，其中表示第i个位置的第个二进制位上的值。所以我们只要根据奇偶性分一下类，然后做前缀和就可以求出所有满足条件的的个数了。 code /* * @Autho...

二进制

2020-05-22

1 717

【每日一题】中位数图

solution 处理出一个数组t，如果那么，否则。然后我们只要找到一个包含b所在位置的区间满足就可说明这个区间内的中位数为。所以对求一遍前缀和，记录下所在位置左边的所有前缀和值的数量。然后枚举所在位置的右边，统计答案即可。 code /* * @Author: wxyww * @Date: ...

思考题

2020-05-21

1 606

【每日一题】图的遍历

solution 我们从1号点开始染色，标记为0的点表示可以从1号点走偶数步到达，标记为1的点表示可以从1号点走奇数步到达。最后就是想要所有点都可以标记为0。如果存在一个奇环，那么这个环上的点既可以标记为1，也可以标记为0，所以所有与这个奇环相连的点都可以标记为0和1。所以我们只要保证最终连接成一...

搜索

2020-05-20

1 781

【每日一题】简单瞎搞题

solution 用表示前k个区间能(1)不能(0)组成这个数字。然后枚举一下第个区间所选的数字x，就有转移最后数一下有多少数字可以被组成就行了。但是这样复杂度爆炸，发现f的值只有和所以可以用进行优化，复杂度 code /* * @Author: wxyww * @Date: 2020-05...

背包 bitset

2020-05-19

2 0