CCPC2020秦皇岛站总结
Day0
开幕式
就听了一大堆发言，就这么过去了。
热身赛
拿到题面，队友果断切了D题和C题，接下来我们就开始看B。
B题是一个博弈，就是有 n n n堆石子，每堆 A i A_i Ai个，每个回合可以从1~2堆中取任意多个。然后问 L i ≤ A i ≤ R i L_i\le A_i\le R_i Li≤Ai≤Ri的条件下先手必败局面的数目。
于是开始分析，起初以为取2堆的话必须取一样多，然后猜想是3进制的“异或”，对照一下样例发现不对，又重新读题。
后来开始从简单情况一步步分析：
1堆先手胜
2堆先手胜
3堆相等时后手胜，否则先手胜
4堆没推完
莫非，，3堆相等的可以消去？
发现不太行。。。
又去看A
A题是给定1个圆 O O O和2个圆外的点 A , B A,B A,B，求两点之间，一条经过圆周但不进入圆内的路径的长度。
开始又看错题了（以为不一定经过圆周），好在影响不大。
于是根据 A B AB AB是否与圆相交分类：
相交时，最短路径是两条切线+一段圆弧
否则是两条线段。
于是我们做法如下：
记 θ = ∠ A O B = arccos O A ⃗ ∙ O B ⃗ O A ∙ O B \theta=\angle{AOB}=\arccos{\frac{\vec{OA}\bullet\vec{OB}}{OA\bullet OB}} θ=∠AOB=arccosOA∙OBOA∙OB
α = arccos r O A , β = arccos r O B \alpha=\arccos{\frac{r}{OA}},\beta=\arccos{\frac{r}{OB}} α=arccosOAr,β=arccosOBr
若 θ ≤ α + β \theta\le \alpha+\beta θ≤α+β
a n s = r ( θ − α − β + tan α + tan β ) ans=r(\theta-\alpha-\beta+\tan{\alpha}+\tan{\beta}) ans=r(θ−α−β+tanα+tanβ)
否则
记 a = O A , b = O B a=OA,b=OB a=OA,b=OB
求 f ( x ) = a 2 + r 2 − 2 a r cos x + b 2 + r 2 − 2 b r cos ( θ − x ) f(x)=\sqrt{a^2+r^2-2ar\cos{x}}+\sqrt{b^2+r^2-2br\cos{(\theta-x)}} f(x)=a2+r2−2arcosx+b2+r2−2brcos(θ−x)的最小值。
WA了十几发，调了半天没找到bug。。
真：签到五分钟，自闭三小时
Day1
A
签到
C
矩形中有一个特殊点和许多普通点，要构造一个角，角内只有特殊点没有普通点，角内的矩形周长最大。
计算几何，题假了，我们也想了假做法（就是角顶点与特殊点重合，再极角排序），歪打正着233
G
签到
F
从一个无向图中选一个子图，子图边权1，点权-1，子图中的点与外界的点之间的连边权值-1，求最大权值。
每个连通块全删或全留（否则一定不会更优），用带权并查集维护（开始题意理解错了，忽略了子图中点与外界的连边，想了个删叶子的假做法，WA了又回头读题）
E
没看，队友过了
K
一棵有根树，根节点有无数军队，每秒可以移动一个军队到相邻点，求军队访问所有点的最短时间。
我们做法是优先访问深度较浅的子树。除最浅的子树外，其他子树可以选择从前一棵子树（最深军队）回来的军队和根节点的军队。过了，但不会证明。
I
维护一个类似“线性空间”的东西。
即判断
[ x 1 x 2 . . . x n y 1 y 1 . . . y n ] [ w 1 w 2 . . . w n ] = [ x y ] \left[\begin{matrix}x_1&x_2&...&x_n\\y_1&y_1&...&y_n\end{matrix}\right] \left[\begin{matrix}w_1\\w_2\\...\\w_n\end{matrix}\right]=\left[\begin{matrix}x\\y\end{matrix}\right] [x1y1x2y1......xnyn]⎣⎢⎢⎡w1w2...wn⎦⎥⎥⎤=[xy]
是否有整数解。
不太会。。
格力公司福利 356人发布