wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

【每日一题】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

hdu1085 Holding Bin-Laden Captive!

solution 有两种解法。解法一：分组背包，相当于有3种物品，分别有个，重量分别是。问不能组成的最小的重量。用表示这个重量能不能组成。然后将分组背包拆成01背包做。枚举一下重量，看是否能组成。解法二：生成函数。用表示选择1能组成的方案。用表示选择2能组成的方案。用表示选择5能组成的方案...

生成函数背包

2020-04-16

1 626

hdu1028 Ignatius and the Princess III

solution 此题有两种解法。第一种解法就是裸的完全背包。就相当于有n种物品，第i种物品的重量是i。每种物品有无限多个，问恰好填满一个容量为n的背包的方案数。第二种解法是生成函数。用生成函数表示拆分出的的数量。用表示拆分出的的数量。剩下的同理。最终的系数就是答案。 code 解法1 /*...

生成函数背包

2020-04-16

1 718