20201006 单峰,积木,同余

2021/5/2 18:29:16

本文主要是介绍20201006 单峰,积木,同余,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

考场

今天的题面比昨天正常多了...

T1手玩了 \(n\le3\) 的情况,发现答案似乎是 \(2^{n-1}\),暴力打表验证后一遍码过,大约用了1h。(但大部分人都只用了30~40min)

T2感觉是DFS+剪枝,40min打完暴力开始寻找优化,尝试将每个积木的棱长排序后按积木最短的棱长排序,这样DFS时就只需考虑两条棱,但很快就拍出了问题:

2  
3875 1802 15404   
29169 3603 2698   

当时并没有立即意识到,手玩了好久才发现问题,一激动把给每个积木棱长排序的部分也删了,剩1h写T3,最后交了裸暴力。

T3\(O(mn^2)\) 的暴力显然,但并没有给 \(n\) 的数据规模。短暂思考发现 \(a_i\le1\) 即 \(a_i\in\{0,1\}\) ,前缀和维护 \(0,1\) 的个数,\(0\) 特判。没有对拍,针对数据规模合并两个程序就交了(当时不知道没有给 \(O(mn^2)\) 部分分)。

T1

期望

\(O(1)\)
100pts

实际

20pts

题目说 \(n\le10^{18}\),但我直接 1<<(n-1),于是只拿了暴力分。(全场就我一个挂掉的)

题解

峰顶一定是 n,因此考虑 1 ∼ n-1 分别放在 n 的左边还是右边,一一得出相应的唯一方案。所以答案就是 \(2^(n-1)\)。

T2

期望

\(O(15!\times3^{15})\) (貌似是)
40pts

实际

60pts

数据过水,暴力可以拿40pts~80pts,只要将每个积木的棱长排序就剪掉了一半的枝,可以卡过去了。

正解

显然是状态压缩 DP。设计状态 f[S][i][0/1/2] 表示已经⽤了集合 S 内的积木,最顶上是编号为 i 的积木,它的哪个面朝上。转移时枚举不在 S 内的积木,以及朝上的面判断即可。时间 复杂度 O(2n · (3n) 2 )

考场上根本没往状压DP上想...
果然还是太弱了

T3

期望

\(O(n+m)\)
20pts

实际

10pts(莫名T掉了第2个点)

题解

观察到,其实要求的是某一范围内 kp + q 的个数,当 p 较小时,k 的取值范围很小。不妨 设“较小”的界限是 > K。 考虑将问题拆开来并排序,这样每个问题就变成了询问 1 ∼ r 中有多少个 kp + q。维护一 个哈希数组,h[i] 表示 i 有多少个;以及一个模数数组 g[i][j],表示模 i 为 j 有多少个。 每次指针向右移,直到移动到当前询问的位置,每移一次就将这个数分别在两个数组内标 记,复杂度总体是 O (nK)。 每次询问时,对于较小的 p 直接在 g 中查询,对于较大的 p 枚举 k 并在 h 中查询,复杂度是 O(m ai/K )。 可以看出 K = √ ai = 100 时最优。

实际上只用h数组即可。

总结

  • Python!!!
  • T1一看就是数学题,但我对自己推式子的十分自信,直接打了暴力。。。以后还是要打暴力
  • DFS剪枝前要手模数据。把似乎能用的版本存一份。删代码要想清楚具体哪里出问题。
  • T3的前缀和做法可以推广到 \(60%\) 的部分分,但没仔细想,反而浪费了大量时间在T2。应该先把T3的暴力打了,最后再考虑优化T2。


这篇关于20201006 单峰,积木,同余的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程