提高省选讲课.pdfVIP

CF98CHelpGregtheDwarf

•给出L,a,b

•让一个长为L宽为W的矩形能通过宽度为

(a,b)的L型道路

•问最宽的W值为多少

•矩形可以移动或者旋转。

CF98CHelpGregtheDwarf

•(L=a)||(L=b)的情况答案是min(L,a,b)

•让矩形的一条长L的边两端点在“L型”的外壁上

滑动，此时该边中点路径是半径为L/2，圆心在左

下角的1/4圆

•宽W的最大值和“中点到圆心连线与底边的夹角”

呈单峰函数

•三分夹角，对于给定的角度我们计算出两端点位

置

•根据点到直线距离推算出此时矩形最长的宽，

得出最短宽对应的角度。

CF23ETree

•给定一棵树，问删去若干树边后，所有连通块大

小的乘积最大为多少

•数据范围：N=700。

CF23ETree

•答案中每个连通块必然不存在长度≥3的路径（否

则可以将该连通块在中间切断，答案更优）

•对于以一个点为根的该点所在连通块包括

的情况：只有该点，该点+其部分儿子结点，该点

+该点某个儿子结点+该儿子结点的部分儿子结点

•我们设f[t]表示以t为根的最大的答案，f2[t]表

示该点所有儿子结点的f值的积。

CF23ETree

•对于第一种情况：s=f2[t]

•对于第二种情况：将所有儿子结点的f2/f按值从大

到小排序，s=f2[t]*∏(f2/f的前i项)*(i+1)

•对于第三种情况：与第二种情况类似，枚举选择

的儿子结点以及选的儿子结点的儿子结点f2/f的前i

项，则s=f2[t]*f2[son]/]*∏(f2/f的前i项)*(i+2)

•不算高精度的时间复杂度为O(n^2)。

circles

•在平面直角坐标系中有n个点，其中1号点为特殊

点

•规定起点编号为c，每次可以走到得距离小

于等于r的另一个点

•从起点出发至多走k步

•在开始走之前，1号点可以移动到距离给定位置不

超过R的位置

•问走至多k步可以到达1号点时,1号点可选的目标

位置组成的面积。

circles

•有如下样例：

•n=4，c=2，R=4，r=3，k=2

•4个圆，圆心坐标分别为(2,3),(0,0),(3,0),(6,0)

circles

•数据范围如下：

•n=1000

•0=k=12

•1=c=n

•-10000=x,y=10000

•0=r,R=10000。

circles

•首先可以用枚举的方法轻松求出哪些圆可以在k-1

到

•将这些圆求圆并后再与1号点对应的大圆求交集就

是直观上的答案

•答案=大圆面积－(大圆和k-1步可达的圆的并－k-

1步可达的圆的并)

•可以使用圆并算法解决。

circles

•使用Simpson算法，可以用积分方便地求出二维

坐标系下一些图形的面积

•设f(k)表示图形在直线x=k上覆盖的长度，对于一

段区间[l,r]若图形在x等于该区间内的任意数值时

均有覆盖，那么可以将该区间一起计算

•设s(l,r)表示区间[l,r]的面积，d=(l+r)/2

•当|s(l,d)+s(d,r)-s(l,r)|=eps时即可近似的将[l,r]区

间内的面积当成s(l,r)

•其中s(l,r)=(r-l)*(f(l)+f(r)+4*f(d))/6。

Twostrings

•给定两个字符串A和B,有五种操作

•操作1为在A串开头添加一个字符

•操作2为在A串结尾添加一个字符

•操作3为在B串开头添加一个字符

•操作4为在B串结尾添加一个字符

•操作5为询问当前的B串在当前A串中出现的次数

•保证字符均为小写字母，且A、B串初始非空。最

终A串和B串长度之和小于等于200000，操作数

小于等于200000。

Twostrings

•ababc

•a

•7

•5

•4b

•5

•3a

•