A
算法一:()
暴力修改求逆序对即可。
时间复杂度 。
期望得分 40pts。
算法二:(保证对于任意操作都有 )
发现所有操作都变成了交换相邻两个数。
容易证明,如果交换相邻的两个数,那么逆序对的奇偶性就会改变。
考虑这两个数之外的所有数与他们的相对位置都不变。
因为排列中没有两个数是相同的,这若原来是逆序对,那么交换后就变成了一对逆序对,反之亦然。
故此结论得证。
那么就可以直接维护了。
时间复杂度 。
期望得分 10pts,结合算法一可以拿到 50pts。
算法三:(保证输入中仅存在操作 1)
显然交换两个数 可以通过 次交换相邻两个数得到。
通过算法二可以知道交换相邻两个数奇偶性会改变。
又因为 显然是个奇数。
所以交换任意两个数奇偶性就会改变。
最开始求一遍逆序对即可,对应的模拟即可。
时间复杂度 。
期望得分 10pts,结合算法二可以拿到 60pts。
算法四:
可以发现所有操作都可以通过若干次交换得到。
通过算法三可以知道交换一次奇偶性就会改变。
相应的处理即可。
时间复杂度 。
期望得分 100pts。
B
Subtask 1
爆搜然后模拟。
Subtask 2
考虑什么时候会算错。
对于 位置,当它与后面的 位置交换时, 是交换前 中的最小值,。
因此,如果 中所有数都不相同,那么交换后逆序对总数只会减少 ,是算对的,也就是说排列能算对。
进一步可以发现,只要 中不存在与 相同的数,逆序对数量就只会减少 ,反之肯定会少算。具体地,大于 的数与 的贡献不会变,等于 的数原先与 能构成逆序对,现在全没了。
那么结论就出来了,如果存在 满足 就会少算。
有人可能会提出疑意:如果 在之前就被换到前面去了呢?
这是没有关系的,因为换过来的只可能是更大的数。所以 或 其中的一个肯定在某次越过中间的那个与后面更大的数交换。
把模拟换成 判断即可通过该档部分分。
Subtask 3
看到数据范围,想到状压。
令 表示到第 个位置,填过的数的集合为 ,出现过至少两次的最大的数为 。
转移枚举下一位填什么即可,时间复杂度 。
Subtask 4
给一些奇怪的做法。
Subtask 5
考虑从大到小填。
枚举最后一位填的数 ,于是前面所有大于 的数最多只能填一次。
那就枚举大于 的数填了 个,用组合数计算。发现当前填的数对剩下的位置没有影响。
于是原问题转化成了一个子问题,具体地,令 表示 个位置可以填 的方案数:
预处理阶乘和逆元就做完了,注意初始化 ,用于转移到所有初始状态。
时间复杂度 。
Subtask 6
观察到组合数很难优化,考虑换种方式填数。
不妨从小到大填,这样只有一个数可以不填在末尾。
令 表示 填了 个位置的方案数,枚举 这个数填几次:
和
时间复杂度 。
Subtask 7
发现对于同一个 可以前缀和优化,然后再用滚动数组优化空间即可通过。
时间复杂度 。
C
对于 的数据
怎么做都可以吧
对于 的数据
对于每个位置维护前 大的数,在扫的过程中同时维护这前 大的数。
时间复杂度 。
对于没有 操作
直接在线段树上对于每个区间维护前 大值即可。
对于 操作
所有数都是一直变大,懒标记处理相对简单。
对于 操作
等同于区间最大值。
对于 的数据
也是在区间上维护前 大数,但是在维护懒标记的时候不能只记录当前的加标记,还要同时记录这个懒标记上的那些操作所构成的历史加标记中的前 大值,而这些标记与当前区间中的前 大值合并后可能可以得到新的历史前 大值。直接暴力合并的复杂度是 的,并不能被接受。于是可以转化为一个相对简单的问题:给出两个有序序列 ,要在 中各选一个数,需要求出前 大的数。先把 扔到堆中( 单调下降),每次取出堆顶的值,如果堆顶的值为 ,那么就把 扔到堆中,这样可以保证复杂度为 。可能需要一定的常数优化。
时间复杂度 。
全部评论
(2) 回帖