苟且的狮子

CF

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

/ 注册

全部文章 / CF （共25篇）

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

E. Number of Simple Paths

tarjan，找环比赛时先看错了题，然后，想出来方案再到编码没赶上。coding还是太慢了。要刻意练习。关键信息在于n个节点n条边。我们注意到了，这其实就是一棵树再加上一条边。树中形成了一个环。我们把这个环单独拿出来，将其他节点视作有这个环上的节点向外的延申。也就是以这个环的每一个节点为根生成了...

tarjan 找环

2020-11-25

2 620

E - Two Editorials

没做出来，上网看人家的题解后终于明白了。其实做的时候也发觉了，这应该是一道差分题。但是究竟应该如何差分呢？对什么进行差分呢？搞不明白。在这道题中，我们可以O(n^2)的计算出所有的一个区间的覆盖。但是，两个区间的话怎么比较他们的最大值呢？总不能O(m)的一一对照吧！那样的话就O(n^2m)不行！所以...

差分

2020-11-21

2 665