A - Balloon Robot

忘了

B - Expected Waiting Time

不是我过的，待填坑

C - Crusaders Quest

暴力枚举消除顺序从而得到消除步数即可

D - Graph Generator

给定一个$n$个点$m$条边的无向图，要你去构造这个图，构造方法如下：

先将1~n号点选定一个处理顺序，依次处理每个点，对该点进行连边

每次选择的点可以选择和一个联通块连边或者不连边，如果和一个联通块连边，那么必须和联通块中所有点都连边。

问是否能构造出解，如果能将解输出。$n,m\leq100000$

考虑如果只有一个联通块，倒着操作，那么肯定是一个点连所有点，剩下会拆成若干个联通块，对每个联通块再递归处理即可，那么如果按度数大小顺序处理肯定不会有问题。于是将所有点按度数升序，加边时并查集合并判断是否连接了联通块中每个点即可。

E - String of CCPC

给定一个由C和P组成的字符串$s$，你可以改变其中的若干个字符，第一次改变代价为$0$，第二次代价为$1$，第三次代价为$2$，以此类推。$s$中每有一个子串CCPC收益加$1$，求最大收益。$|s|\leq 200000$。

明显最多改一次，那么记一下前缀和后缀出现之和，枚举改哪个位置就好了。

F - Getting Lost

二维平面上给你一个起点$S$和一个终点$T$，并有不超过$2$个障碍圆。找到从$S$到一满足条件的点的最短路径，不能穿过障碍圆。满足条件的点指距离$T$不超过$R$，且该点和$T$的连线上没有障碍。

先把关键点抠出，关键点包括起点、终点、起点和障碍圆的切点、终点和障碍圆的切点、障碍圆的内公切线交点、障碍圆的外公切线交点，然后将关键点之间连边，那些不经过障碍的边形成关建边，将关建边两两求交得到新的关键点建新图，在新图中跑最短路即可求得答案，注意特例，还没写。

G - Numbers

给定$n$和$m$，令$n=\sum_{i=1}^ma_i,S=a_1\ or\ a_2\ or ...or\ a_m,a_i\geq0$，求$S$的最大值。$n\leq10^{1000},m\leq10^{100}$。

从高位到低位判断，能填$1$就填$1$，否则填$0$，用JAVA写就好了

H - Prime Set

有$n$个数$a_i$，如果$a_i+a_j$是一个质数的$i\neq j$，那么$(i,j)$是一个pair。现在你可以选择最多$k$个pair，一个数一旦被选择一次就被消去，问最多消去多少个数。$n\leq3000,k\leq \frac{n(n-1)}{2},a_i\leq10^6$。

先不考虑$1+1=2$的情况，那么将奇数放在左边，偶数放在右边，跑二分图求出最大匹配，一开始两个两个消除，然后一个一个消除就好了。

然后考虑把$1$加入的情况，那么$1$要不然自我消化，要不然和放在左边和一个偶数结合，那么把$1$一个一个加入并实时更新答案就好了。时间复杂度$O(n^2)$。

I - Triangulation

三角剖分

J - Tree Equation

给定两颗树，求两颗树的gcd

K - Diversity and Variance

给定$n$个数，在其中选$m$个数，使得他们的方差最大。方差公式$S=\frac{1}{n}\sum_{i=1}^n(a_i-\frac{1}{n}\sum_{j=1}^na_j)^2$。$n,m\leq100000$。在方差相同的情况，输出编号的字典序最小的答案。

方差是很好算的，即$S=\sum_{i=1}^na_i^2-\frac{(\sum_{i=1}^na_i)^2}{n}$，容易发现当$m>1$时，选择的数一定是最左边某一段+最右边某一段。特殊处理$m=1$的情况，如果不考虑字典序，直接扫一遍将答案更新即可。

现在考虑字典序，那么对于方差相同的我们通过比较一下两种方案中另一种方案不存在的一段中的最小值来得到大小，那么大力讨论一下用线段树求一发就好了。

L - One-Dimensional Maze

要么往左要么往右，判一下就好了

M - Safest Buildings

绝地求生大逃杀中目前有$N$个建筑物，大圈半径为$R$，新刷圈半径为$r$，现在随机刷圈，找到最有可能是安全点的若干建筑。$N\leq100$

如果$2*r<R$，那么半径在$R-2*r$以内的点最有可能是安全点；如果$2*r>R$，那么半径在$R-2*r$以内的点最有可能是安全点。如果没有这样的点，那么离原点最近的点最有可能是安全点。

OJ炸了代码找不到

• 相关文章推荐
• 全局相关文章