wxyww

题解

未归档(12) 精品(28)

/ 注册

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

【每日一题】NC14704 美味菜肴

solution 贪心+dp。做这个题我们需要处理两个问题。第一个是如何确定这些菜的顺序，第二个是确定了菜的顺序之后如何计算答案。先来确定菜的顺序。仔细观察之后，发现其实这个问题贪心思路和“国王的游戏”一样。如果只考虑两种菜。我们如果让在前，那么选这两种菜的答案就是，否则就是。发现都有，所以我们...

贪心 dp

2020-04-27

2 876

【题解】 NC5205E 水灾

solution 首先可以发现，这张图其实可以转化为一棵最大生成树。我们按权值从大到小加入边，如果新加入的边所连接的两点，已经可以通过其他权值更大的边相连，后面的询问中只删除这条边起不到任何作用。所以我们考虑建出重构树。具体建立方法:对于在生成树中的一条边，新建一个节点，并且从向所在的集合...

生成树

2020-04-25

1 743

【每日一题】Removal

solution 用表示前个元素，删掉了，所能得到的不同序列的数量。如果先不考虑不同序列的话，那么就有。也就是种方案。然后考虑减去不合法的方案。对于一个位置，如果上一个和相等的位置为,那么以结尾的每个序列，都可以通过删掉这个区间变成以结尾的序列。这显然是重复的，所以只要让就行了。 code /*...

动态规划dp

2020-04-25

1 780

【每日一题】子序列

solution 我们大胆猜测：如果当前已经选择了一些位置，加入新位置时只要与已选的最后一个位置满足题目条件，那么肯定与前面的每个位置都满足条件。下面给出证明。证明:设已有。对于第一个不等式，同时变为，因为底数为正数，所以不等式符号不变。即变为,对于第二个不等式，同时变为，即变为。然后将这两个新...

数学动态规划

2020-04-23

1 710

【每日一题】K-th Number

problem 题意搞了很久才搞懂233.给出一个序列，对于每个长度的子段，会将其中第大的元素放进集合中。最后询问集合中第大的子段。 solution 首先二分一个答案。然后一下区间第大大于等于的区间个数，如果，那么说明还可以再放大并且可以成为答案，否则说明需要缩小。然后考虑函数如何写。维护两个指...

二分答案

2020-04-21

1 531

【每日一题】糖糖别胡说，我真的不是签到题目

solution 对于每个糖糖考虑计算他是不是会被消灭。一个组的糖糖会被消灭仅后面存在一个组的糖糖满足，表示前秒总共增加的能量值。移项得。所以把每个糖糖的能量值都变为。然后从后向前枚举的过程中分别统计两个后面的最大值。判断当前点是否会被消灭。 code /* * @Author: wxyww * @...

思考题

2020-04-20

1 556

【题解】 NC5157E 牛牛与序列

solution 考虑求答案的补集。也就是计算有多少个序列不是反复横跳的。这样的序列肯定是单调不降序列或者是单调不升序列。又因为所有数字不超过k。以单调不降序列为例（单调不升序列个数与其相等）。我们枚举最后一个数字的大小。然后对这个序列做一下差分，也就是令。这样就转化成了有多少个满足条件的序列...

组合计数

2020-04-19

2 620

【题解】 NC5157C 牛牛的等差数列

solution 用线段树维护即可。考虑线段树的懒标记如何维护。我们维护两个懒标记，添加到当前位置的数列在该区间开始位置的首项之和，表示这些添加的数列公差之和。因为如果往一个位置添加了一个等差数列。其中某个位置可以看作，那么再添加一个等差数列，那么该位置就可以看作，相当于添加了一个首项为公差为的等...

线段树

2020-04-19

4 1107

【题解】 NC5157B 密码系统

solution 其实本题只要解决一个问题，剩下的就是模拟了。这个问题就是如何快速的比较两个字符串的字典序。这是一个非常经典的思路。我们对这两个字符串都哈希一遍，然后二分一下这两个字符串最长的公共前缀长度。然后比较最长公共前缀的下一位上的字符就行了。因为所有要比较的字符串都在同一个母串上。我们只要...

字符串

2020-04-19

4 531

【题解】 NC5157A 聚会

solution 显然答案具有单调性，所以二分一个答案，也就是最后一个人到达的时间。这样距离原点小于等于的点就都不用考虑了。然后目标就是放置一个传送门，使得其他的点与传送门之间的距离小于等于。显然将传送门放在这些点的中间最优秀。所以只要找到最靠右和最靠左的两个点，看他们之间的距离是不是小于等于即可...

二分答案

2020-04-19

2 685