ByteDance - Moscow Workshops ICPC Programming Camp 2019. Day 2, Div A.

ABCDEFGHIJK

复盘人：yjn

一开始散开来看了题。

A是个瘠薄，直接跑了，gt看了BCDEF，R爷看了GJ，我看了HK。

R爷和我讨论了下J，我表示这个直接RHO，但gt说rho很慢要T，就先放着了。

我看K是个傻逼几何计数，就让R爷先写。R爷在写的时候我在旁边看着，理了一下大框架，把计数分的几类和算的方法顺了清楚。但是\(O(n^3)\)数三角形内的点个数因为我没搞清楚细节花了一些时间。

H是给55对距离，让你还原11个点，和gt讲了下感觉不可做，就扔了。

gt和我讲了F，讨论了下感觉坐标两维独立，可以平衡树xjb搞，gt就去想细节了。

这个时候我简单看了下BC，都没什么想法。看了下D，感觉是个傻屌积分题，就开始推公式。

0:52:18 K(+0) 这个时候R爷过了K。

然后旁边的敦爷F狗带了，说不独立，我们不明觉厉，就先放着了。这时候gt已经会了E，开始写。一段时间以后R爷说G是个二分斜率，他们两个就轮流上。

然后gt没过样例，R爷写完输方案发现不能输方案，我D数分没学好，郭希特的积分板子还是错的，手撸积分积了一万年，大家一起gg。

然后gt E PE了，输方案错了，我推完自信上D，没过样例。lu了半天，开挂打开mma，发现没推错，才知道是公式抄错了，然后TLE 1忘记去文件，之后又WA 5，然后开了long double就过了。

3:09:12 D(+2)

gt E又dirt了两发以后过了。

3:24:30 E(+3)

之后我和R爷讨论了下J，打算特判掉一个质数的情况，筛掉小质数，然后搜一下大质数乘几个小质数的情况。R爷开始写。

此时gt和我说了F为什么不独立，他一个人去fix了一会儿说搞不出来。

R爷这边，抄了我的rho板子。这个板子表面上是处理LL的实际上是处理int的，miller rabin因为题目性质偷懒所以是没有判2的。快速乘，random之类的问题都没处理好，爆交了两三发。然后改杜教板子，罗干半天，才开始线下拍。

最后发现rho里的一个优化R爷写疵了，改了就过了。这段时间我和R爷两个人一直在一起弄这个J，gt也没怎么看别的题一起在看J。

4:32:24 J(+4)

然后还有二十多分钟，不知道哪里听来小道消息说B还是C很好写。然后我看了下C突然会了，但是做法比较吃屎，就让gt去吃。然而也没报什么希望，最后也没过。

A：瘠薄

B：智商题。以V为底，C/V为高作矩形。把这些矩形按照高排序在x轴上挨个排开。然后要做的就是找一段长度为\(\sum V_i/2\)的区间\((l,r)\)，使得\((l,r)\)这段里面的图形面积是\(\sum C_i/2\)。根据介值定理一定有解，两刀就切在对应的两个矩形那里。

      upd(by fz):写的有点吃shit.写了一个先确定左端点块,然后再枚举右端点块用方程解右端点,height相同的时候有各种情况要讨论.以后万不得已一定写二分(+N)

C：看正多边形的周围一圈。如果整圈都是同色，就done了。否则找一个点\(y\)，他左边右边分别是点\(x,z\)，使得\((x,y),(y,z)\)这两条边不同色。然后删去\(y\)这个点递归n-1边形求解原问题，\(y\)可以根据求出来的生成树颜色而选择连哪一条边。

     补题：拿个循环链表搞下，用个set维护前后不同色的点，递归搞就行了。函数里的n和函数外的n混淆了dirt了一发。用时没记。+1。

D：手撸积分，以后靠R爷了。

E：沙比树形dp,但是要输出一个方案,保存所有合并前的数组,然后一个一个子树倒推回去,空间比正常写*2.

F：

G：不输方案直接\(O(n \log ans)\)凸优化即可。输方案好像只能\(O(nk)\)大力一下。

H：不会，说是暴搜。

I：

J：见前文。

K：随便count一下。

小结：

1、rho板子要好好搞个，优化厘清。比如线性筛预处理，当分解质因数分到n比较小的时候直接用预处理的东西暴力罗干。然后rho板子要注明什么数据范围能跑多快。

2、积分表要弄一个，郭希特那个是错的。

3、\(O(n^3)\)预处理所有三角形内部的点个数的板子要补一个。

4、B这个题主要没时间想了。要是花时间手撸一下$n=3$的情况，这个题还是能想到的。

5、C最后我提出的是在周围一圈不断加一种颜色的边，然后想办法维护。标算是删边。逆向思维还是要考虑下（smwy）。