ZROI 19.08.10模拟赛
写在前面:为了保护正睿题目版权,这里不放题面,只写题解。
- A
\(20pts:\)
枚举操作序列然后暴力跑,复杂度\(O(6^n)\)。
\([50,80]pts:\)
枚举改成dfs,每层操作后还原。复杂度\(O(3^n)\)。
全0或全1可以直接返回。
写法优秀可以过\(80pts\)。
\(100pts:\)
类似非递归fft的写法,bitrev后可以位运算优化。
最下面四层可以预处理,复杂度\(O(3^{n-4})\)。
然后疯狂卡常就完事了(
然而由于swk人菜常数大,明明所有剪枝都加上了仍然挂掉了qwq
破案了,原来swk太菜了,在递归的每一层都重构了一遍结构体,结构体里还用了vector,于是多了\(12\)倍常数,就死掉了。
- B
\(80pts:\)
枚举最小差,设为\(d\)。
统计最小差大于等于 \(d\) 的集合最大差之和,发现对于一个最小差为\(x\)的集合,它的最大差刚好被统计了\(x\)次。
直接dp,设\(f_i\)表示前\(i\)个元素,且第\(i\)个元素必选的最大差之和。转移时需要一堆前缀和。我代码写的特别诡异
\(100pts:\)
仍然枚举\(d\),对每个\(d\)枚举集合元素个数\(x\),发现\(dx\leq n\),所以枚举复杂度为\(O(n\log n)\)。
然后随便组合数一下就可以了。
发现集合中的最大值和最小值是对称的,可以分开算。
考虑枚举最小值为\(c\),则方案数为\((^{n-c-x(d-1)}_{~~~~~~~~x-1})\)。即选中\(x\)个元素,在它们后面附带\(d-1\)个额外的空格,其中位于位置\(c\)的元素必须被选中,且前面不能有任何被选中的元素,可以直接把这个元素删掉。
设\(a=n-x(d-1),b=x-1\),则总贡献为\(\sum_{c=1}^{a-b} c\cdot (^{a-c}_{~~~b})=\sum_{c=b}^a (a-c)\cdot (^c_b)=\sum_{c=b}^a (a+1)\cdot(^c_b)-(c+1)\cdot (^c_b)\)。
将后半部分拆开,得到\((c+1)\cdot (^c_b)=\frac{(c+1)c!}{b!(c-b)!}=(b+1)\frac{(c+1)!}{(b+1)!(c-b)!}=(b+1)\cdot(^{c+1}_{b+1})\)。
代回上式,得到\(\sum_{c=b}^a (a+1)\cdot(^c_b)-(b+1)\cdot (^{c+1}_{b+1})=(a+1)\cdot(^{c+1}_{b+1})-(b+1)\cdot(^{c+2}_{b+2})\)。可以\(O(1)\)计算。
- C
swk完全不会做找观察题所以光荣爆零了。然而大家都切了这道题,所以swk菜死了。
一个很重要的结论就是每个点只会往上走。
感性理解下就是越往上边就越稀疏。
于是每个点只有\(O(\log)\)个点与它相关,建出边直接跑就可以了。
上面的写法比较麻烦。好写一点的方法是,两个点必然在lca附近相遇。对每个点可以算出向上不经过桥最近的祖先,贪心地找最高的祖先即可。需要特判两个点在祖先的两侧相遇的情况。
最新文章
- Oracle获取干净的建表DDL语句,不含其它存储、表空间、段属性
- 作业三:PSP记录耗时情况
- unity3d引擎的学习
- 数据存储--sqlite总结
- Cordova for Android(Windows)环境配置
- Xcode_5
- objective-C运算符和表达式
- 会吓人的概念证明病毒: Chameleon
- C#WinForm中在dataGridView中添加中文表头
- 02 - Tomcat配置
- 实现Android半透明Menu效果的开发实例
- zDialog无法获取未定义或 null 引用的属性“_dialogArray”
- JavaScript的this简单实用
- Map 对象
- window7 64位安装Python
- Eclipse Rcp
- 修改、设置root密码
- Core 中文文档
- Java语句语法
- requests库下载图片的方法
热门文章
- 阶段3 2.Spring_08.面向切面编程 AOP_5 切入点表达式的写法
- 【HTML】---HTML语义化
- 【ABAP系列】SAP BOM反查
- 浅谈 MySQL的预编译
- 【神经网络与深度学习】caffe+VS2013+Windows无GPU快速配置教程
- Python xlsxwriter库 图表Demo
- Mac 如何将apache的这个默认目录更改到用户目录下
- Springg MVC 中文乱码处理
- Nmap 在 WSL 中工作不正常
- Two Merged Sequences CodeForces - 1144G (暴力)