2014ACM-ICPC广州站题解(摘自闭幕式)
第39届ACM-ICPC亚洲区广州站题解
Ltysky摘抄自闭幕式题目分析
Problem A
满足px+qy=c的点(x,y)在一条直线上,而c的值由直线的截距确定,所以最大化c,就要在糖果(x,y)点集的凸包上根据斜率确定一个顶点,所以本题需要动态凸包算法,但是动态凸包只能处理加点,要删点的话需要结合陈丹琦分治。
Problem B
坑题,栅栏可以套另一个,这种情况下面积是大的。
Problem C
将字符串建trie图,然后满足条件的字符串分为以下两类:
- 它是一个前缀,同时也是一个后缀。这样的话这个前缀对应节点的fail指针应该指向非根节点
- 它不是一个前缀,这是用一个简单的动态规划算法,用dp[i][j]表示后面前缀长度是i,然后j表示从根节点开始沿trie图走完两个前缀之后所在节点,i>=1
首先枚举所有前缀p,如果p在trie树中没有儿子c,则dp[1][p->c]+=1,其中p->c表示从p开始走字母c所到达的节点。
之后,对于dp[i][j],枚举一个字母c,如果j->c所在节点在trie树中的深度不小于i+1,则dp[i+1][j->c]+=dp[i][j]。j->c的深度表示后一个前缀最长可以为多长,所以自然应该不小于i+1。
最后累加所有的dp[i][j]即为答案。
Problem D
由Apollonius圆定理,区域的边界是一个圆。求圆与简单多边形的面积交即可。(模板题)
Problem G
(P/Q)^2的范围可以用两个有理数确定,也就是P/Q的范围可以用两个二次根式确定。求两个二次根式连分数展开序列,在序列的公共前缀后面进行讨论确定P/Q。
Problem H
首先,如果不上高速,可以覆盖的区间显然是一个圆,然后,如果可以上高速公路,肯定沿着一条与高度公路称定角的线段上高速,再沿着同样的角下来是最优的。所以,可以简单地得出沿着高速公路走能覆盖的部分是一个菱形,求圆和菱形的面积并即可。
Problem J
考虑直径的中点(如果直径长度是偶数,可以假设在正中间增加了一个点,它的度数固定为2),则它有两棵(直径为偶数)或三棵(直径为奇数)二叉子树,其中应有两棵的高度为d/2,然后转化为有限制的有根数奇数的问题。首先预处理H_i表示高度为i的不同构的有根二叉树的数目。如有两棵子树,答案为C(H[d/2],2),否则为C(H[d/2],2)*(H[1]+H[2]+…+H[d/2-1])+C(H[d/2],3)
Problem K
水题
最新文章
- stm32 usb error : identifier ";bool"; is undefined
- uexQQ插件学习心得
- JavaScript学习(2):对象、集合以及错误处理
- php配置
- bash脚本编程之二 条件判断and 逻辑运算
- css.day01
- save与 merge与 saveOrUpdate的区别
- HDU 5046 Airport(DLX反复覆盖)
- css的选择器的优先级
- 基于Dubbo的http自动测试工具分享
- Salesforce 超大量数据导入优化策略
- JAVA多线程-内存模型、三大特性、线程池
- OpenGL——外部读档+异常报错
- react.css
- 使用netty编写IM通信界面
- Commons工具包的使用
- PPT-常用快捷键
- HDOJ题目分类
- SAP NUMBER RANGE维护配置object FBN1 Deletion only possible if status is initial
- Java并发编程--6.Exchanger线程间交换数据