非常抱歉，这场比赛没有签到题，又在题面和数据上出现了问题，希望大家多多谅解……后两题题解仍在施工中。

多边形与圆

A题数据曾经有问题，会导致一部分做法得到90分，现在经修改数据合法了

一道高中几何题……考虑以𝑖号点为轴旋转的时候，1号点的运动一定是一段圆弧，于是我们只需要求出 圆弧的半径和弧角即可。

显然每次旋转都是等价的，我们不妨以图示为例，以2号点为轴旋转时为例，按下图作辅助线。

根据余弦定理，，而𝑎, 𝑏, 𝑐的值可根据多边形初始各 点的坐标直接求得，因此我们可以直接求得∠(1,2,3)的值。也可以使用向量点积。

根据余弦基本性质和圆上一条弦的基本性质，显然有cos∠𝑘1 = (𝑎/2)/𝑟， cos∠𝑘2 = (𝑏/2)/𝑟，其中𝑟为圆的半径。因此我们可以直接求得∠𝑘1和∠𝑘2的值。

显然有∠(1,2,3) + ∠(3,2,3′) = ∠𝑘1 + ∠𝑘2，因此∠(3,2,3′)的值已经可以求出。

根据弧长公式，显然𝑙𝑒𝑛 = ∠(3,2,3′) ∗ 。问题就此得到解决，时间复杂度为。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43186973

子串翻转

这个题std做法复杂度，本可以完全不让平衡树通过，但是我在出题时觉得正解比平衡树更方便去想，也没有去故意卡平衡树。

由于翻转操作的下标是单调增的，这道题可以使用deque去做，代码比较短。用deque维护一个滑动窗口，记录一个翻转标记，表示窗口是否翻转。每次只能翻转整个窗口，一开始窗口为。这样我们只需要处理三种操作即可

第一种操作：将当前的窗口向右移动一。我们只需要根据标记，在头或尾弹出一个字符，并在另一端插入一个字符即可，同时维护窗口外的字符。

第二种操作：翻转窗口。直接更改翻转标记:0->1/1->0。

第三种操作：输出一个字符。如果不在窗口内，直接输出。不然根据是否翻转，在窗口的deque内查询正确位置输出。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43186989

圆桌聚餐

由于圆桌的对称性，第一个人做在哪里，是哪国人其实是无关紧要的。但是在第一个人坐下之后，整个圆桌就变成了一个序列而不是一个环。考虑使用动态规划解决此题：记录dp[n]为长度为n的无人段，两边都有人就座，期望能够坐下多少人。选座机的设置使得每个段之间是互不影响的，枚举第一个坐在此段的人的位置和国家那么我们可以得出：

可以使用前缀和加速，就达到的复杂度。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43186992

突击检查

首先，我们将就寝的点，和其连接的边去掉，得到一个未就寝点的森林。现在我们需要求出其中联通块数目平方的期望。首先，一个森林中联通块的数目就是点数减去边数。然后我们只需要得到(点数-边数)^2的期望=点数^2-2点数边数+边数^2。又已知点数=X，边数的期望可以用每条边两边都是未就寝的寝室的贡献来求,。边数平方等于可重的有序边对个数，然后就需要求出两条边的边对的个数期望，分别讨论没有公共点的和有公共点的。取无公共点的边对数目期望为 。有一个公共点的边对期望可以根据每个点的度数分别求其为中间点时的贡献，为，有两个公共点的边对期望就同边数的期望时一样的。

答案便为

其中.
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43186993

七星阵

将所有的边按照弧度排序，而后枚举一个起点，按照每一条边的顺序进行动态规划。设代表当前在i号红色点，这是凸包上的第j个点，在前j个点的区域内选取k个蓝色点的方案数。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43186996

市政交通

简要题解：使用LCT，对于每一个节点开一个大小为2000的bitset，对于每一个公交路线随机三个bitset上的位置，在对应节点上异或。对于每次询问，可以证明只要有公交线路，异或为0的可能性可以忽略，然后对于第一个为1的bit，暴力在另一个不维护异或和的LCT上进行询问所有包含这个bit的公交线路。

复杂度
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43187000