苟且的狮子

分类

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1) 题解(180)

/ 注册

TA的专栏 88篇文章 0人订阅

kuangbin题单刷题详解(最短路篇)

9篇文章 696人学习

kuangbin题单刷题详解(网络流)

10篇文章 648人学习

kuangbin题单刷题详解(匹配问题)

14篇文章 724人学习

kuangbin刷题题单详解(后缀数组)

8篇文章 588人学习

kuangbin刷题题单详解(博弈论)

8篇文章 736人学习

kuangbin刷题题单详解(连通图)

9篇文章 814人学习

Kuangbin刷题详解(AC自动机)

4篇文章 613人学习

Kuangbin题单详解(kmpManacher)

20篇文章 950人学习

Kuangbin题单详解(区间dp)

6篇文章 791人学习

全部文章（共229篇）

D. A Game with Traps

今天的一场虚拟竞赛就是一道贪心+模拟不难，但是wa了好多发。果然还是没有适应这个难度的题目啊题目让我们求最大可以带走的军队数量。很显然，我们能够想到二分。我们从属性值最高的兵开始带走，可以只考虑带的兵中属性值最低的那个人。所以，我们只需要排个序就行了。关键是二分中如何二分呢？如何判断，这个属性值可...

2020-12-08

0 625

D. Beautiful Array

动态规划并不是很难，就是情况稍显复杂。我峨嵋你要分两种情况1.x为正数2.x为负数如果为正数，那么我们直接求出这个数组初始的最大的美丽数然后乘x就可以了。注意这里的初始最大美丽数最小为0，因为如果全部是负数，那么我们一个也不取如果为负数，那么很有可能被会出现这样的一种情况[L,R]为答案区间 ...

2020-12-04

1 499

D. Recommendations

implement 贪心老实说，思路并不是很难。但是，实现起来是很有难度的。其实就是如果两个元素冲突了，那么我们就增加那个代价比较小的就可以了。很简单，但是我的实现超时了。懊恼。个人感觉实现起来真的是有一定的难度。推荐这个并查集实现的代码： #include <map> #inclu...

2020-12-03

1 427

B. Modulo Sum

dp 之前看了，雨神的关于dp优化的思路视频。感觉很神奇。就在cf上做了一做。磕磕碰碰。。但是，确实思路是雨神说的。首先对于这道题，我们要判断是否可以取出一些数其和能整除m直接设状态方程dp[i][j]即到第i个为止是否能够凑出符合要求的数。对于这种能否凑出来整除的题，我们往往有一个技巧就是先进行取...

2020-12-02

2 663

E. New Game Plus!

贪心这一题个人感觉倒不是多难。主要靠直觉。首先，如果没有k这个条件的话，我们肯定是从大到小的取元素。这一题最开始，我们也应该从大到小地取元素。同时此刻的cur即元素值也在不断变化。一旦cur变为负数的时候，我们break一下。然后问题来了，我们对于接下来的每一步都必然是负数的元素，该如何使用这k次...

2020-11-30

2 442

D. XOR-gun

思维题这题有个小陷阱，比赛时掉进去了。过了pretest但是没能Accept首先，最小的次数肯定就是1既然是异或，那么我们很容易就会按照位进行思考。我们想想，如果最高位为i的数字，总数超过3个。那么我们是不是一定能在1此操作中干掉这个数组。能的，对后两个进行异或，然后与前面的一个比较，一定小于前面...

思维

2020-11-29

1 557

E - Common Number

找规律我在打表后发现，这一题可以进行二分答案，来做。虽然整体并不呈现单调性但是偶数和奇数却呈现单调性。这就很方便了。我们可以分别在偶数和奇数上进行二分答案，然后取大即可。但是，有一个困难，那就是如何求解每次这个数出现的集合数如何求解呢？刚开始我是使用暴力的，因为我隐隐约约的感觉复杂度应该不算很高...

奇偶二分思维

2020-11-27

2 575

D. Portals

dp 我在一开始的时候也想要用dp去做，但是发现，对于占据一个节点我们可以在当前位置占据他，也可以在之后占据他。这一就意味着我峨嵋你的dp具有后效性，那么就不能dp了苦恼啊苦恼。后来发现，这里其实是一个简单的贪心。对于占据一个节点，很明显我们在能占据他的节点中的最后面占据他就好了！这个贪心至关重...

dp

2020-11-27

2 492

E. Array Shrinking

区间dp 虚拟比赛时没有做出来，看题解时，第一句话就让我反应过来了！可恶！！！！最终的答案假如[a1,a2,a3]那么a1,a2,a3一定是三个区间合并出来的也就是，我们给数组划分几个区间，这些区间都可以合并成一个数。找到划分区间的最小数。问题一下子就简化了！！定义dp[i][j]，如果[i,j...

区间dp

2020-11-26

2 562

Picnic Cows

斜率dp 斜率dp都不大好写啊，细节的边界处理感觉好麻烦啊。这里我们很容易就总结出状态和状态转移方程了。我们首先从小到大排序(在斜率dp中排序很重要，有利于保持决策的单调性)dp[i] 表示到第i个点为止的最小花费。dp[i] = min(dp[j-1]+sum[i]-sum[j]-(i-j+1)a...

2020-11-26

2 553