Praying_cqf

分类

训练总结(1) 题解(1)

/ 注册

全部文章（共14篇）

电带切队训练实录5.9

训练题目集链接https://ac.nowcoder.com/acm/contest/16092过题数：7 签到题是G，是一个模拟除，直接淦了。然后看榜，过题比较多的是H，是一个dp，非常简单。一开始mle了一发，然后改成滚动数组就过了，有惊无险。 D题我没看，栋哥说他切了，他上了，他过了。然后...

2021-05-12

0 588

所有区间最值问题

这里有一种分治的做法。考虑当前分治区间[L,R]，区间中心为mid，我们需要解决的问题是求出所有跨越mid的区间的答案。首先枚举右端点r(左端点也是一样的，这里只是举个栗子)，对于所有左端点l和最大值(最小值)，可能的情况有三种：1、max(l,mid)>max(mid,r)2、max(l,m...

2021-02-01

0 524

价格的可能性题解

【前言】非常简单的动态规划题。【暴力】搜索，搜出所有可能性。【不完美的超时做法】设f[i][j][k]表示，只买前i种商品，共买了j件，能否达到价钱k。可以转移到f[i+1][j][k]和f[i][j+1][k] 复杂度是O(nm^2*max(v))极限是500^4 【...

2021-01-16

0 482

最大价值问题题解

【前言】无。【暴力】枚举每种物品的选择与顺序。复杂度显然很大。【正解】假设我们知道了一个最优解的集合，但不知道顺序。最优顺序显然是按照代价从小到大排序后依次选择。因此，我们可以把物品先按代价排序，然后进行动态规划。设f[i][j]表示在前i个物品中选择了j个的最优答案，注意，这里的物品是按代价排好序...

2020-09-04

0 553

奇怪的排序问题题解

【前言】无。【暴力】搜索O(2^n)【正解】对于一个位置，如果这个位置后面有比它小的数，那这个位置肯定是要动的，这显然是答案的下限。我们来证明一下这个下限是可以达到的。有一种很显然的排序方法可以达到这个下限。从后往前看每个位置，如果该位置的身高大于后面的位置，则进行一次选择，这样就达到了下限。这种方...

2020-09-01

0 689

挑选方案问题题解

【前言】无。【暴力】直接搜索方案数。【打表】通过对小数据的暴力很容易得知答案就是(n+1)(n+2)/2【正解】我们将盘子2和4看做一类，盘子3和5看做一类，这样是可行的，对于任意正整数m，都可以表示为2x+a或5y+b的形式，这里的x和y分别就是在4和5号盘里面取的件数，a和b分别是是小于2的正整...

2020-08-31

0 601

集中问题题解

【前言】一道简单题。【暴力】枚举坐标系上的点，统计答案即可。【正解】可以发现题目中距离是切比雪夫距离，这样计算距离和非常不方便。我们知道切比雪夫距离和曼哈顿距离是可以相互转化的。切比雪夫距离相同的点可以围成一个与坐标轴平行的正方形，而曼哈顿距离相同的点则可以围成一个与坐标轴成45°的正方形。考虑曼哈...

2020-08-08

0 596

共鸣问题题解

【前言】简单题。【暴力】可以有2^n的暴力。还有其他暴力方式，不赘述。【正解】假设答案为ans，初始时，我们把ans设为所有额外共鸣的和的相反数。并且将额外共鸣分别加到两个音符的优美程度上，得到一个新的价值。最后，只有音符的价值大于0我们才将它加入答案。这样显然是正确的。具体请参照代码理解，非常简单...

2020-08-04

0 929

羁绊计算问题题解

【前言】充满欺骗意味的题目。【暴力】记录每个羁绊是否出现，根据打法不同，复杂度亦不相同。【比较厉害的暴力】我们有一个稍微奇妙一点的做法。用f[i]表示i与i+1到f[i]都建立了羁绊，可以发现f[i]具有单调性，那么在暴力的过程中，f[i]>=r则可以退出了。这样的话可以优化不少，但还不够。【...

2020-07-24

0 859

均衡题解

【前言】非常简单的题目。【暴力】枚举起点和终点即可。复杂度O(n^2)【正解】我们把0看成-1，然后求出前缀和数组s[]，可以发现，如果区间[i,j]满足条件，那么s[j]-s[i-1]=0，即s[j]=s[i-1]，那么对于每个s[]中可能的取值，保留最前面的那一个，用来更新答案即可。用桶来实现。...

2020-07-22

0 883