Codeforces Round #502
Codeforces Round #502
C. The Phone Number
题目描述:求一个\(n\)排列,满足\(LIS+LDS\)最小
solution
枚举\(LIS\),可证明\(LDS\)的最小值为\(\left \lceil \frac{n}{LIS} \right \rceil\)。
证明:
假设\(LDS<\left \lceil \frac{n}{LIS} \right \rceil\),令\((a_i, b_i)\)为\(i\)为结尾的\(LIS\)和\(LDS\),可知\((a_i, b_i)\)二元组两两不同(假设\(a_i=a_j, b_i=b_j, i<j, \because a_i=a_j,\therefore p_i>p_j\), 则\(b_j=b_i+1\)矛盾)
则有\(1\leq a_i \leq LIS\),
\(1\leq b_i \leq LDS \leq \left \lceil \frac{n}{LIS} \right \rceil -1 < \frac{n}{LIS}+1-1=\frac{n}{LIS}\)
所以二元组的个数小于\(LIS \cdot \frac{n}{LIS}=n\),根据鸽巢原理,必定有两个二元组相同,矛盾。
因此\(LDS\)的最小值为\(\left \lceil \frac{n}{LIS} \right \rceil\)。
根据这个可构造答案,从大到小排,然后每\(LIS\)个一组,剩余的一组,然后每组从小到大排。
时间复杂度:\(O(n)\)
E. The Supersonic Rocket
题目描述:题目看得很过瘾,竟然可以把判断两个凸包是否相同描述得如此得复杂。。。
solution
以边长和角度(可以用相邻边的点乘代替)的顺序作为凸包的特征值,把第一个凸包的特征值看成一个字符串,第二个凸包的特征值复制两遍,跑一次\(KMP\)即可。
时间复杂度:\(O(nlogn)\)
F. The Neutral Zone
题目描述:定义\(exlog_f(p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k})=a_1f(p_1)+a_2f(p_2)+\cdots+a_kf(p_k), p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}\)是一个数的质因数分解,\(f(x)=Ax^3+Bx^2+Cx+D\), 求\(\sum_{i=1}^{n} exlog_f(i)\)
solution
其实就是求
\[\sum_{i=1}^{n \text{以内质数个数}} f(p_i)\sum_{j=1}^{\infty} \left \lfloor \frac{n}{p_i} \right \rfloor\]
但是空间只有\(16M\)
方法一:
质数中除了\(2, 3\)其它质数模\(6\)为\(\pm 1\),以此可以将线性筛的数组控制在十几\(M\)。
方法二:
将\(\sqrt{n}\)的质数求出来,然后将\(n\)分块,每一块分\(3\times 10^6\),然后每一块用\(\sqrt{n}\)的质数筛,筛剩的就是质数。
时间复杂度:\(O(nln\sqrt{n})\)
G. The Tree
题目描述:有一棵以\(1\)为根的树,一开始所有点都是白色,现要支持三种操作:
- 选择一个节点,如果这个节点是白色,则将它变成黑色,否则对它的所有儿子进行同样操作。
- 选择一个节点,将这个节点的子树全部变成白色。
- 询问一个节点的颜色。
solution
题解给的方法是对操作分块\((\sqrt{n})\),然后每一块的操作只涉及\(\sqrt{n}\)个点,然后不知道怎么搞。。。
下面一个小哥给了一个树剖的做法,感觉好理解一些。
首先将所有点标记为\(-1\),
对于操作\(1\),将那个点\(+1\),
对于操作\(3\),就是询问该点到根的后缀和最大值是否非负,如果非负,则这个点为白色,否则就是黑色。
对于操作\(2\),先询问父亲到根的最大后缀和\((x)\),然后将子树全部变成\(-1\),最后如果\(x>0\), 则询问的那个点要加上\(-x\),以消除前面操作对该子树的影响。
时间复杂度:\(O(nlogn)\)
最新文章
- CentOS 安装Paramiko模块
- AngularJs项目实践总结
- SLAM拾萃(3):siftGPU
- magento搜索属性值的设置方法
- [LeetCode 111] - 二叉树的最小深度 (Minimum Depth of Binary Tree)
- MVC4.0 Controller和View重复加载
- docker for windows &; dotnet core app
- selenium自动化测试学习(一)
- 正则替换replace中$1的用法以及常用正则
- Servlet--创建和配置Servlet
- Canny 边缘检测及相关应用
- pandas 导入导出
- 为了好好看球,学霸们用深度学习重建整个比赛3D全息图
- Word Ladder II leetcode java
- python正则表达式re库(自用)
- 前端之css笔记1
- 《Spring 2之站立会议3》
- 图灵社区 书单推荐:成为Java顶尖程序员 ,看这11本书就够了
- OpenStack Object Storage(Swift)概述
- 在Cocos2d-X中使用xml
热门文章
- BZOJ 1975 魔法猪学院(A*求K短路)
- 【bzoj1430】小猴打架 Prufer序列
- 使用Runtime.getRuntime().exec()方法的几个陷阱
- 【Java】全站编码过滤器GenericEncodingFilter代码与配置
- 【刷题】BZOJ 3238 [Ahoi2013]差异
- javascript的解析顺序
- LUCAS定理简述
- MyBatis openSession(),close(),和commit() 底层代码剖析
- hihocoder[Offer收割]编程练习赛19 D 相交的铁路线(树上路径交)
- Codeforces Round #419 (Div. 2) A B C 暴力 区间更新技巧 +前缀和 模拟