A、最短路
两点之间，线段最短，考虑最短路径一定是先走切线，再走圆弧，再走切线（可以通过反证法证明）
所以我们只要求出 
的坐标就做完了。
以 A 为例子，我们需要求 A 到 圆O 的切线
我们先由 %7D)
得到 %7D))
然后将向量 
固定点 A 顺时针旋转 
并且等比例缩放就得到了 D1 的坐标
同理可以得到 D2 的坐标，现在就剩下圆弧了，将D1，D2的极角相减，并令它小于 180°，然后就可以直接求出圆弧的长度了
注意到我们并不知道 A B 在 圆O的哪个方向，所以需要求出AB的各两条切线，枚举走那条切线
B、组队
要求人数最多，一定是取一整段区间，所以考虑使用滑动窗口
首先将所有人按照能力值排序，然后维护一个最大能力值与最小能力值的差值小于等于 
的“窗口”
若当前满足差值小于等于 ，则窗口向后再加入一个人，反之，删掉前面一个人，然后每次更新最大人数
即可在 )
的复杂度下算出最多人数，算上排序的复杂度，所以复杂度是 )
二分最大人数也可通过此题
C、十面埋伏
本意是让大家求出包围并且紧挨牛可乐士兵的最少陷阱数的方案
那么我们只需要对士兵外围 bfs 一下，然后对所有 bfs 到的节点，判断他周围四个方向是否有士兵，若有士兵，则说明这个点需要放置陷阱。
D、牛妹吃豆子
二位前缀和，由于修改操作、求和操作是分开的，考虑用修改四个点来维护修改一个区间的修改，然后求一次前缀和得到真正的矩阵，再对这个矩阵求前缀和，使用四个点来容斥得到一个区间的总和。
如果大家不会二维前缀和的话，建议大家看一下上面的博文或者百度一下，这一块经常会用到。
BONUS：如果是三维前缀和呢？
E、旅旅旅游
先求出以 1 为起点单源最短路（
）和以 n 为起点的单源最短路（
），然后枚举每条边 
，若满足 
，（其中 
指 
的最短路）则说明这条边在最短路上，否则不在最短路上
之后我们用并查集来维护所有不在最短路上的边（即将这条边的两个点放在一个集合中），若所有点都在一个集合内，则说明牛妹可以将所有城市走一遍，反之，不可以。
F、斗兽棋
签到，注意输出描述，平局或者赢了输出“tiangou yiwusuoyou”
G、做题
贪心，考虑到先做花费时间最少的题目，可以做更多的题目
WA在这里一般都是没开long long，或者没有判断能做0个题目和能做所有题目的情况
H、人人都是好朋友
注意到朋友的朋友是朋友，敌人的敌人不是敌人
考虑先将所有的朋友关系利用并查集放在同一个集合中，再判断具有敌人关系的两个人是否在同一个朋友集合中即可。
由于范围太大，记得离散化。（^-^)
I、求和
考虑利用dfs对整棵树重新编号，编号后，可以使得任意一颗子树的序号连续
然后使用树状数组或者线段树维护单点修改和求和操作即可
J、建设道路
实际上需要求的东西就是 %5E2)
从上一步变成下一步的方法：对于每个下标 ，它在位置 
产生贡献的次数是 
（枚举每一个小于 的 
），在位置 产生的贡献次数是 
（枚举每一个大于 的 ）
第二个式子算一个前缀和即可，时间复杂度 ，记得取模
全部评论
(13) 回帖