Codeforces 题目集锦

1601A

这道题目乍一看很花哨,但和位运算有关的题目,手玩一下就可以把原题的操作换作一个很简单的操作。

本题中其实就是在同一位上选择k个1,使这k个1都变成0,若要使一位上的1都变成0,那这一位上1的个数需是k的倍数,所以我们对每一位上的1的个数取gcd,得到k,若k成立,则k的因数也一定成立,输出k的所有因数即可

1601B

青蛙爬井问题
在初学OI时也有一道这样的青蛙爬井的题目,当时a和b都是固定的,推出数学式子即可

而这道题的a和b都不固定,且向上爬的高度也不一定是a。可以想到最暴力的做法直接去bfs,找出爬出井的最短时刻,但显然由于向上爬的高度不确定,bfs的复杂度会极大

对于上述问题,有两种解决方法

用并查集来维护一下,将跳过的点和它上面的点合并在一起,因为这个点既然已经跳过,那之后再跳到这个点,答案一定会更劣,所以我们枚举向上跳的时候就可以跳过这个点,用并查集搞下来每个点只会访问一次,复杂度是O(n)的。
这个思路与前几天模拟赛中的一个扫雪的题思路很类似,也是通过并查集来优化掉冗余操作,从而使时间大大增加

另一种解决做法就是依然是正常的bfs,但在建图时用倍增或线段树来优化建图即可

这个题目的一个小trick:青蛙最后一个白天直接就跳出井了,而不会再往下掉,所以我们将今天白天与昨天晚上一起进行处理,而不是将今天白天与今天晚上一起处理

1601C

考虑暴力的做法,用树状数组维护逆序对个数,把每一个b放到a中找它最合适的位置,复杂度为 O ( m n l o g ( n ) ) O(mnlog(n)) O(mnlog(n)),显然过不去

设 p i p_i pi​表示 b i b_i bi​在 a a a中的位置,即当 b i b_i bi​恰好在 a j a_j aj​之前时, p i = j p_i=j pi​=j

存在一个性质,即将 b b b从小到大排序后, p i p_i pi​单调递增。证明的话考虑反证法,将两个 b b b调换顺序,答案显然会更劣

根据这个性质进行整体二分,先处理出 b m i d b_{mid} bmid​的位置,即 p m i d p_{mid} pmid​,然后将 b b b从 m i d mid mid处划分开,将值域也从 p m i d p_{mid} pmid​处划分开,继续进行处理

这样即可高效的优化上述暴力过程,得到每一个 p i p_i pi​后,构造出最终的序列 c c c,树状数组+离散化 求一下逆序对个数即可

总复杂度为 O ( ( n + m ) ∗ l o g ( n + m ) ) O((n+m)*log(n+m)) O((n+m)∗log(n+m))

看大部分神仙们这道题写的都是线段树做法,蒟蒻没读懂代码,只好啃官方英文题解

1602A

一道水题,要 a a a的字典序最小,那长度越小越好,所以我们找到字典序最小的一个字母,将它从原串中剥离出来作为 a a a串,剩下的部分作为 b b b串即可

1602B

观察一下这道题数据范围和样例,不难猜测到序列变化到一定次数就不会再发生改变了,貌似是每一次变化都会少一组数,所以变化次数最多是 n n n次,所以就可以存下每一次变化的每一个值, O ( 1 ) O(1) O(1)回答即可

上一篇:P4380 [USACO18OPEN]Multiplayer Moo S 题解


下一篇:二叉树的BFS&打开转盘锁详解 -- 转载