C

一个凸包,以速度v从右向左运动
一个人站在(0,0),以速度u径直走向(0,w),可以停顿
求到达w的最少时间

就是算凸包每个点经过后,走完剩下的距离的最大值

复杂度 $O(n)$

D

长度为n的序列,m个询问
每个询问为 [l,r] 之间的出现偶数次的数的异或和

将询问按r排序
用树状数组维护到r为止
一个区间出现过的数的异或和(只算一次)
答案就是区间异或和 异或 区间出现过的数的异或和

复杂度 $O(nlogn)$

E

给出n个数$a_i$和一个数k
在n个数中选择最少的数使得它们的乘积是k的倍数,且和最小

DP

首先将每个数与k取gcd,生成$b_i$
$d[i][j]$表示前i个数中取数的乘积为j的最小个数以及最小和
显然j是k的因子
$d[i][j] = min(d[i-1][j],d[i-1][j/gcd(j,b[i])] + (1,a[i]))$

注意判断 k = 1 和 $k/\prod gcd(k,a[i]) \not{=} 1$ 的情况