2019-team2/Sp094

从 Trac 迁移的文章

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

原文章内容如下：

在外面走了一会就被风吹到冻傻了。
开场写G,不想思考写数位DP结果WA(赛后发现是爆long long),然后换成贪心'''G48(-2)'''.J不知道是什么题'''J63(-1)'''.发现H是个凸包,交完发现没过样例,再来一次'''H75(-1)'''.发现A是个科学的随机,'''A147(-1)'''.然后想起来线段树可以求mex,'''I(171)'''.发现F可以随便搞搞,不过样例也往上交几下,最后'''F199(-4)'''.K在瞎搞,剩30多分钟想起来可以暴力.然后T飞.尝试把set改成priority_queue,结果晚了几秒.
A. 记F[i][j][k]表示到第i位,3部分和的差.可以证明随机顺序后极大概率是对的.
F. 显然要满足A是公约数倍数和不超过最大值两个条件,构造只需要把水留在最大的杯子中即可.
G. 对每个n求小于等于b且末位n位是9的数,答案一定在这些数里.
H. 裸的凸包.
I. 求区间mex,线段树二分即可.
J. 二分
K. 每个点作为根跑次DP,然后枚举每个点作为另外一个端点.去掉log需要每个点的子结点搞个前缀后缀最大值.也可以log强行卡过去.

在外面走了一会就被风吹到冻傻了。

开场写G,不想思考写数位DP结果WA(赛后发现是爆long long),然后换成贪心G48(-2).J不知道是什么题J63(-1).发现H是个凸包,交完发现没过样例,再来一次H75(-1).发现A是个科学的随机,A147(-1).然后想起来线段树可以求mex,I(171).发现F可以随便搞搞,不过样例也往上交几下,最后F199(-4).K在瞎搞,剩30多分钟想起来可以暴力.然后T飞.尝试把set改成priority_queue,结果晚了几秒.

A. 记F[i][j][k]表示到第i位,3部分和的差.可以证明随机顺序后极大概率是对的.

F. 显然要满足A是公约数倍数和不超过最大值两个条件,构造只需要把水留在最大的杯子中即可.

G. 对每个n求小于等于b且末位n位是9的数,答案一定在这些数里.

H. 裸的凸包.

I. 求区间mex,线段树二分即可.

J. 二分

K. 每个点作为根跑次DP,然后枚举每个点作为另外一个端点.去掉log需要每个点的子结点搞个前缀后缀最大值.也可以log强行卡过去.