这真是一场毒瘤的 $\mathrm{Edu}$ ...

不过为什么要unr,我应该能涨一点的


比赛地址

Inscribed Figures

简单分类讨论。

如果你 WA on #3 ,建议测一下 3 1 2 ,答案应该为 6

代码

Ugly Pairs

考虑一种奇妙的构造方案。

把所有的奇数字符(ace、…)拿出来,从小到大排序,形成字符串 $A$ 。

把所有的偶数字符(bdf、…)拿出来,从小到大排序,形成字符串 $B$ 。

那么如果 $AB$ 可行就输出 $AB$ ,如果 $BA$ 可行就输出 $BA$ ,如果都不可行就无解。

代码

Match Points

二分答案。

二分一个答案 $mid$ ,考虑怎么 $\mathrm{check}$ 。

把所有 $x$ 从小到大排序后,显然前面 $mid$ 个和后面 $mid$ 个配对是最好的。

那么直接检查这 $mid$ 个配对是否全部合法即可。

代码

0-1 Tree

点分治裸题 点分治做法右转xzz的blog

并查集。

考虑所有答案点对有哪几种情况:全 $0$ 、全 $1$ 、一段 $0$ 接一段 $1$ 。

只保留树上所有 $0$ 边,形成一个森林,我们把这个森林称为 $0$ 森林。

那么对于 $0$ 森林内的每个连通分量,会产生 $sz(sz-1)$ 个全 $0$ 对。

用并查集维护连通分量,这样子就处理完了所有全 $0$ 点对。

全 $1$ 点对和全 $0$ 点对是类似的。

现在考虑一段 $0$ 接一段 $1$ 怎么做。

对于一个一段 $0$ 接一段 $1$ 的点对 $(u,v)$ ,显然会存在一个点 $t$ ,使得 $(u,t)$ 全 $0$ 、 $(t,v)$ 全 $1$ 。

那么枚举 $t$ ,它的贡献就是 $(sz_0-1)(sz_1-1)$ ,这里的 $sz_0$ 指的是 $t$ 在 $0$ 森林中所属连通分量的大小, $sz_1$ 类似。

那么这题就做完了。

代码

Special Segments of Permutation

枚举+单调栈。

先预处理出每个 $i$ 左边第一个大于它的位置(记为 $L[i]$ )和右边第一个大于它的位置(记为 $R[i]$ )。显然可以单调栈 $O(n)$ 求出。

枚举最大值的位置,那么左端点只会落在 $(L[i],i)$ ,右端点只会落在 $(i,R[i])$ 。

那么在小的那个区间中枚举一个端点,在另外那个区间中查有没有对应的值。

这样子看上去是 $O(n^2)$ 的,实际上是 $O(n\log n)$ 的。具体证明戳这里

代码

Card Bag

DP。

如果赢的话,那么拿出来的牌形成一个单调递增的序列,最后一个数重复两次。

设 $f[i][j]$ 表示抽了 $i$ 张卡(没有重复),最后抽到的是 $j$ 的获胜概率。

直接转移是 $O(n^3)$ 的,前缀和优化一下就能做到 $O(n^2)$ 了。

代码

Optimizer

咕咕咕

最后修改:2019 年 09 月 26 日 01 : 28 PM