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)回答即可