2020-team1-052

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 7/12  dirt: 46%

rank: 6

[[Image(Rank.png,800px)]]


== 总结 ==



== 题解 ==

A: 如果x<y且x在y左边，那么x和y可以合并为2个(x+y)/2，然后贪心

@Grammy 咋维护凸包dp啊

B: 推式子，ntt快速幂

C: 先判INVALID，需要满足cnt[i]>=cnt[i+1]，差分后转化成若干条链，从长到短插入，用线段树维护目前每种长度还可以插入多少，如果不够则在根以上再加入一个点作为新的根，这样可以统计出最少需要多少点才能是二叉树。

对于给定的n，满二叉树只有一种

DEFINITELY当且仅当n=2**k-1且除了根以外所有点的高度都给定

其余情况比较每种高度的个数和需求量，都<=则POSSIBLE，否则IMPOSSIBLE

D: 类似逆序对

E: 

F: 

G: 差分，枚举差的gcd的约数更新答案

H: 按位枚举，后面两串不同的位置数为最大贡献

I: 

J: 拓扑排序求每堆至少有多少石子，游戏结果和策略无关

K: 

L: 几何与分类讨论

[/wiki/2020-team1 返回]

概述

solved: 7/12 dirt: 46%

rank: 6

总结

题解

A: 如果x

@Grammy 咋维护凸包dp啊

B: 推式子，ntt快速幂

C: 先判INVALID，需要满足cnt[i]>=cnt[i+1]，差分后转化成若干条链，从长到短插入，用线段树维护目前每种长度还可以插入多少，如果不够则在根以上再加入一个点作为新的根，这样可以统计出最少需要多少点才能是二叉树。

对于给定的n，满二叉树只有一种

DEFINITELY当且仅当n=2**k-1且除了根以外所有点的高度都给定

其余情况比较每种高度的个数和需求量，都<=则POSSIBLE，否则IMPOSSIBLE

D: 类似逆序对

E:

F:

G: 差分，枚举差的gcd的约数更新答案

H: 按位枚举，后面两串不同的位置数为最大贡献

I:

J: 拓扑排序求每堆至少有多少石子，游戏结果和策略无关

K:

L: 几何与分类讨论

附加文件