sdfz两个队都进金线了/se
但是非正式只有三个金，我们是守门员/cy
收录一下正常水平队伍应该切掉的八个题。B不包含在内。
A. Space Ship
三维空间中有\(n\)个球，\(n-1\)个棍，连成一棵树。支持把一个棍沿着一个球在某一维上转90度，或者查询两个球的距离。\(n,q\leq 10^5\)。
对于一根棍，转两边都可以转化成转深度更大的一边。用树剖维护变换复合，这里矩阵即可。
B. Monitored Area
多边形内有若干光源，求有光部分的面积。多项式复杂度即可。
据说有个trick叫 有限simpson?
我感觉可能指的是CF1086F那个trick之类的东西。
C. Optimal Strategy
有\(n\)个数排成一排，两个人轮流拿，每次可以拿任意一个，他们都希望拿到的总和尽可能大，并且都会按照最优策略来拿，求最优策略的数量。两个策略不同当且仅当有一步拿的数的编号不同。\(n\leq 10^5\)。
枚举几个扫描线方向之后发现，考虑最大的，如果它是奇数个那么上来就会被拿，否则它会被两两配对打包，一个人拿了一个，另一个人就会拿另一个，然后把这些包塞进前面的操作里，可以用隔板法计算。
输麻了的题。最后10min胡了没写出来。
D. Arithmetic Sequence
有一个序列，你每次可以给一个数\(\pm 1\)，求最少多少次变成等差数列。\(n\leq 10^5,a_i\leq 10^9\)。
枚举了斜率之后，截距是个中位数。
强行猜测单谷，打表验证确实，于是三分一发冲了。
E. Insidemen
有\(n\)个人围成一圈，有若干条线段连在两个人之间，如果线段\((a,b),(c,d)\)相交(不在端点处)就会产生\((a+b)(c+d)\)的贡献。有两个人是拖拉机，和他们中至少一个相连的线段会被删掉，求对于任意两个人是拖拉机的情况中，贡献和的最大值。\(n\leq 10^3,m\leq 10^5\)。
我们枚举这两个人\(i,j\)，此时和\(i\)相连的线段会被删掉，这些线段上的交点会被减去。和\(j\)相连的线段会被删掉，这些线段上的交点会被减去。两条分别和\(i,j\)相连的相交线段，它们之间的贡献被删了两次，需要加回来。
前两项是好算的，因为每条线段只会枚举一次。但是第三项不好算。
考虑这个 相交 是什么东西。讨论一下，我们现在拿着\(i,j\)，于是对于\(i<k,j<l\)，\((i,k),(j,l)\)相交当且仅当\(i<j<k<l\)或者\(j<i<l<k\)，并且这两个只可能有最多一个成立，于是可以分开算。我们再枚举一个\(k\)，所有的\(l\)就是一个区间，于是前缀和即可搞定。复杂度\(O(nm)\)。
不太懂怎么\(n^2+m\)（
J. Determinant
给一个矩阵和它行列式的绝对值，求它行列式的符号。这个行列式的绝对值可能非常大。\(n,a_{i,j}\leq 100,\det(A)\leq 10^{10^4}\)，\(100\)组多测。
考虑取5e3个1e9级别的大素数，只要行列式膜这个素数不是\(0\)，我们膜这个素数做行列式就能判断符号了。直接做即可。
K. Search For Mafuyu
树，A从\(1\)出发，B等概率的在\(1\)之外的一个点，求最优策略下A期望多少步找到B，输出实数。\(n\leq 200\)，\(1000\)组多测。
发现所有的dfs序的答案是相同的。随便模拟一个即可。
L. Strange Series
给出\(n\)次多项式\(P\)，求\(S=\frac{1}{e}\sum_{m=0}^\infty\frac{P(m)}{m!}\)，答案膜\(998244353\)，可以证明答案存在。\(n\leq 10^5\)。
拆开每一项，打表可以发现\(\frac{1}{e}\sum_{m=0}^\infty\frac{m^k}{m!}=B_k\)，其中\(B\)是贝尔数。\(O(n\log n)\)求贝尔数即可。
M. Coloring Rectangles
平面上有若干个矩形，你需要给每个选一个角，把这个矩形的\(\frac{1}{2}\)染黑，要求被染黑超过一次的面积为\(0\)。选左上，右上，左下，右下分别标记为\(3,2,1,0\)，构造方案使得字典序最大，或报告无解。\(n\leq 200\)。
考虑把矩形的两条对角线画出来，两条对角线把矩形分成四个区域，你发现上下两个和左右两个需要各选一个，并且两部分独立，于是2-sat。
最大字典序的话，我们拆区域的时候先尽量选上面，再尽量选左边。现在问题是如何判断选一个是否可行。这好像是经典trick?
先判断无解。然后我们直接贪心选，选了一个之后就标记所有可以到达的点，如果标记出了一个矛盾那就不行，如果两种选择都矛盾那应该是不可能的。这样做复杂度是\(O(nm)\)，看起来很高，实际上很不满。
还是算一下复杂度?图中有\(200*4=800\)个点，边数是满的\(800^2\)，最后算量大概是\(800^3\)，所以dfs常数必须小，它也确实小（
另外用上这个爆搜你就不需要缩scc的技术了，所以好像变得更好写了。
最后一个问题 : 怎么判断三角形有没有交?如果两个三角形有交，那么要么一个的某个端点在另一个里面，要么一个的某条边跨过另一个的某条边，这个对多边形也是成立的。第一种是经典问题，第二种可以用叉积，于是爆力判断即可。