竞赛讨论区 > 【题解】牛客IOI周赛26-提高组
头像
王清楚
发布于 2021-06-10 10:29
+ 关注

【题解】牛客IOI周赛26-提高组

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) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐