2019-Sp3-team5

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

 [[Image(img.png,700px)]]

== 总结 ==[[br]]
   开场挺不顺利的，读到了G签到，我上去把G写了，因为方便对拍，而且属于乱搞题，稳一点写了个暴力判断比较了一下，确认无误交G，G51(1)，之后换pb去写H一个二分+凸包，写了之后wa，这个时候[[br]]
  我想到了J的二分，所以先换我上，写的时候发现二分里面的模拟没那么简单写的慢了点，最后还好一发过了，J120(1)，这时候我发现pb的凸包可能炸了，加上Miner两个人一起在看那个凸包。交了几发还是wa[[br]]
  开始对拍，找到了几个错交过后，H149(4)。之后我发现K的输出与Miner给我讲的题意不一样，miner开始BG了奶茶，结果最后K想了个假的算法还没过。我们的A题是一直被卡的，正解的做法是想到了，维护插值转移[[br]]
  但是确实忘了状态转移插值不会太大，定着开就好了，很多时候就是没想着能去试一下，赛后知道正解想起了以前可能也碰到过这种转移，中间过程一定不会差值过大，在val<=30的情况下是很特殊的，遂A就这么GG了。[[br]]
  剩下一个I算我背锅，题意读完我就知道是mex,居然不知道怎么区间求mex一度自闭，想到了线段树但是树上放的东西放错了导致想歪了。后来pb想到了，写了个线段树过了I。[[br]]

  以及赛后回顾K题，我也想到过枚举两个点树形dp，但是当时可能被自己另外一个错解影响太深没有继续想下去，gg。[[br]]


zx:[[br]] G J写慢了,A太畏畏缩缩，K太鲁莽了，H题他们卡的时候我不该在边上自顾自的看其他的，过去帮忙看一眼，那个错我能找到的，这种时候救出队友的效益显然很高。I题这种线段树上的维护没想到也是我的锅。[[br]]
总结：无能狂怒。[[br]][[br]]

lyc: 自己的debug能力还是不行啊，为什么看不出来凸包写错了呢。还是要尽早把队伍的一个模板整理出来，不然每次一到用的时候翻开校版，然后发现自己看不懂，最后手模一个错误百出的模板出来。我的读题还是要再加强 [[br]]

pb:开场看了看H，很快想出了做法，但是没有凸包的板子，凸包出现了手误居然一直没有看出来，小数据debug完全不起作用，这种还是需要打印出来然后眼查，然后求区间mex这种数据结构常规操作只要类比一些操作就行了，还是思维比较窄，想的太慢了，最大的失误还是一直卡了H吧，不能太依赖GDB，毕竟要占着机子。


= 补题 ==[[br]]

== 题解 ==
'''A''' 


'''C'''

'''D'''

'''E'''



'''F''' 


'''G'''



'''H'''

将所有的二元组抽象为二维平面上的一个点，发现代价即为以原点为起点、以该点为终点的向量的点积。考虑点积的意义是向量的投影的乘积，发现可以在点组成的凸包上二分。

'''I'''
首先发现可以从前往后处理，对于(x,i)这样的限制，只有x最小的有用，然后就是要满足求区间mex，那么对于每个数维护它上一次出现的位置，上一次出现位置在[l,r]中如果没有出现过，就说明这个数对mex有贡献，直接权值线段树维护即可

'''J'''
尽量满足优质插头（支持多级排插的），二分满足的数量，插头都放其最大能放的层数，其他地方全部放排插，排插从大到小放。

'''K'''
暴力枚举两个端点，以其中一个作为根，考虑此时树的直径在哪儿,树形dp

'''L'''


'''M'''

Contest Information

== 总结 ==[[br]]

开场挺不顺利的，读到了G签到，我上去把G写了，因为方便对拍，而且属于乱搞题，稳一点写了个暴力判断比较了一下，确认无误交G，G51(1)，之后换pb去写H一个二分+凸包，写了之后wa，这个时候[[br]]

我想到了J的二分，所以先换我上，写的时候发现二分里面的模拟没那么简单写的慢了点，最后还好一发过了，J120(1)，这时候我发现pb的凸包可能炸了，加上Miner两个人一起在看那个凸包。交了几发还是wa[[br]]

开始对拍，找到了几个错交过后，H149(4)。之后我发现K的输出与Miner给我讲的题意不一样，miner开始BG了奶茶，结果最后K想了个假的算法还没过。我们的A题是一直被卡的，正解的做法是想到了，维护插值转移[[br]]

但是确实忘了状态转移插值不会太大，定着开就好了，很多时候就是没想着能去试一下，赛后知道正解想起了以前可能也碰到过这种转移，中间过程一定不会差值过大，在val<=30的情况下是很特殊的，遂A就这么GG了。[[br]]

剩下一个I算我背锅，题意读完我就知道是mex,居然不知道怎么区间求mex一度自闭，想到了线段树但是树上放的东西放错了导致想歪了。后来pb想到了，写了个线段树过了I。[[br]]

以及赛后回顾K题，我也想到过枚举两个点树形dp，但是当时可能被自己另外一个错解影响太深没有继续想下去，gg。[[br]]

zx:[[br]] G J写慢了,A太畏畏缩缩，K太鲁莽了，H题他们卡的时候我不该在边上自顾自的看其他的，过去帮忙看一眼，那个错我能找到的，这种时候救出队友的效益显然很高。I题这种线段树上的维护没想到也是我的锅。[[br]]

总结：无能狂怒。[[br]][[br]]

lyc: 自己的debug能力还是不行啊，为什么看不出来凸包写错了呢。还是要尽早把队伍的一个模板整理出来，不然每次一到用的时候翻开校版，然后发现自己看不懂，最后手模一个错误百出的模板出来。我的读题还是要再加强 [[br]]

pb:开场看了看H，很快想出了做法，但是没有凸包的板子，凸包出现了手误居然一直没有看出来，小数据debug完全不起作用，这种还是需要打印出来然后眼查，然后求区间mex这种数据结构常规操作只要类比一些操作就行了，还是思维比较窄，想的太慢了，最大的失误还是一直卡了H吧，不能太依赖GDB，毕竟要占着机子。

= 补题 ==[[br]]

题解

A

C

D

E

F

G

H

将所有的二元组抽象为二维平面上的一个点，发现代价即为以原点为起点、以该点为终点的向量的点积。考虑点积的意义是向量的投影的乘积，发现可以在点组成的凸包上二分。

I

首先发现可以从前往后处理，对于(x,i)这样的限制，只有x最小的有用，然后就是要满足求区间mex，那么对于每个数维护它上一次出现的位置，上一次出现位置在[l,r]中如果没有出现过，就说明这个数对mex有贡献，直接权值线段树维护即可

J

尽量满足优质插头（支持多级排插的），二分满足的数量，插头都放其最大能放的层数，其他地方全部放排插，排插从大到小放。

K

暴力枚举两个端点，以其中一个作为根，考虑此时树的直径在哪儿,树形dp

L

M

附加文件