p_b_p_b的博客

博客

Public NOIP Round #6 题解

2023-10-15 13:04:18 By p_b_p_b

倒腾

来源:

直接模拟即可。

探索

来源:

深度优先搜索每一步是否有碰到障碍,并且不能与之前已经定下来的状态冲突,即可 $O(2^n)$ 搜出所有可能的路径。

抉择

来源:

算法一

设 $dp(i)$ 表示 $a[1\dots i]$,其中 $i$ 必须处于子序列中,的答案。转移为 $dp(i)=\max_{j\lt i}dp(j)+(a_j\&a_i)$,时间复杂度 $O(n^2)$,期望得分 $45$。

算法二

对于 $a_i\le 511$ 的数据,可以设 $f(i,j)$ 表示 $a[1\dots i]$,选择一个子序列,子序列最后一个数是 $j$ 的答案。转移为 $f(i,j)=f(i-1,j),f(i,a_i)=\max_{j}f(i-1,j)+(a_i\&j)$。期望得分 $20$。

算法三

如果 $a_i$ 随机,大部分 $a_i$ 肯定都要选。在算法一中强制 $j\ge i-500$ 就可以了。

算法四

考虑如何用类似算法三的思路(大部分时候多选都比少选优)优化算法一。

注意到如果 $i$ 之前选的最后一个数是 $a_x=y$,而存在 $x\lt j\lt i$ 满足 $a_{j}$ 和 $a_x$ 的最高位都是 $2^w$,但是最优解在 $i$ 之前没有选 $j$ 而是选了 $x$,则 $(a_x\&a_i)\ge (a_x\&a_j)\ge 2^w$,说明 $a_i$ 也有 $2^w$ 这一位。那 $(a_x,a_j,a_i)$ 一定比 $(a_x,a_i)$ 优,矛盾了(前者权值至少是 $2^w\times 2$,后者权值至多是 $a_x\lt 2^{w}\times 2$)。

所以可能转移到 $i$ 的 $x$ 只可能是每种最高位出现的最后一个位置。

时间复杂度 $O(n\log V)$。期望得分 $100$。

解法不唯一,本题还有很多形式类似的结论都是对的。

重生

来源:

在路上了!

遍历

来源:

在路上了!

排序

来源:

solution by Wu_Ren

考虑操作变成,把序列 $A$ 划分成 $D_1+D_2+\dots+D_m$,把 $A$ 变为 $rev(rev(D_1)+rev(D_2)+\dots+rev(D_n))$。

因为可以用两步进行一次相邻元素的交换,有一个 $n(n-1)$ 的做法。同时有很多简单的 $n-1$ 的做法。

还有一个分治排序的做法,归并两段有序的 $a_{1,\dots,p},b_{1,\dots,q}$ 时,找到这些数的中位数 $w$,进行一次 reverse 把比 $w$ 小的数放在左边,大的放在右边,显然两个部分还是分别能分成两个有序的段,可以分治并行,总操作数精细实现可以做到 $1+\sum\limits_{j=1} \lceil\log_2(\lceil\frac{n}{2^j}\rceil)\rceil$。当然,也有很多其他 $O(\log n)$ 归并的方法。

正解考虑排序 01 序列,那么把相邻的 0 和相邻的 1 合并,最后有 ...0101...,那么我们划分为 ...|01|0|10|1|01|0 或者 ...01|0|10|1|01,那么操作一次后,段数都会变为原来的 $1/3$ 上取整。

我们从高到低考虑每个位,假设我们对于高的位都排序完了,那对于这一位我们把高位相同的数看作一个序列,相当于对若干个序列进行上面的过程,可以并行,所以对于每个位我们的操作数都是 $\lceil\log_3n\rceil$。

精细实现的话总操作数为 $1+\sum\limits_{j=0} \lceil\log_3(\lceil\frac{n}{2^j}\rceil)\rceil$,在 $n=20000$ 时为 $78$,能过。

评论

[+3]
[在路上了](https://qoj.ac/blog/znstz/blog/729) 两边题解的并正好是全集(
  • 2023-10-15 17:44:39
  • Reply
[+1]
刚注册的傻逼过来康康
  • 2024-01-23 20:50:31
  • Reply
[+1]
新的赛季到了,我们的题解还在路上吗?
  • 2024-10-17 14:05:16
  • Reply
[0]
  • 2024-01-23 20:49:50
  • Reply
[0]
@
  • 2024-01-23 20:50:06
  • Reply
[0]
看明白抉择那个不等式在说什么了。。 某个子序列末两位是 ai 和 aj,对于 i
  • 2024-08-23 09:53:53
  • Reply
Comment replies
maka_baka:这是打不了长评论吗算了

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。