「CF1254X」Codeforces Round #601 (Div. 1)

2019年11月20日2650

A. Feeding Chicken

记 R 的数量是 tot 个,则有 tot % k 只鸡的地盘是 tot / k + 1, 其它是 tot / k,蛇形对方格进行染色,把连续的若干个 R 以及它们之间的方格染成一个颜色

B2. Send Boxes to Alice (Hard Version)

求和,枚举和的所有质因子 p,从左到右依次贪心,每个箱子里的巧克力数调整为最近的一个 p 的倍数,差的部分从下一个箱子拿

C. Point Ordering

难得见到计算几何题。把 1 看作原点,先找出 1 逆时针方向的下一个点,做法是先选一个弦,通过询问 2,不断找出弦逆时针方向的点 y,把 1,y 看作新的弦。

接下来以 1,y 为底边,询问以其它所有点为第三个顶点的三角形面积,逆时针看,这些三角形的面积是先递增后递减的。面积最大的那个三角形顶点向 1 连边,再次用询问 2,判断其它所有点在这个弦的哪个方向。分开这两部分的点后,各自按面积排序,就能找出所有的点顺序。

avatar
  Subscribe  
提醒