2020-team1-037

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 7/12  dirt: 65%
rank: 48
[[Image(Rank.png,800px)]]

== 流水账 ==

== 总结 ==
Grammy: 我好像还是在梦游，本来感觉这场大部分题都是我很会的题，但是还是打的稀烂，B出了个假做法，发现假之后就在几个假做法直接反复横跳，丢掉B的时候已经有点晚了，捡起G写的时候脑子也不清楚，dp漏了一种情况（最后过了我也感觉我的dp好像复杂了），这场还有个问题是我没有看过K的题意
Sakuya:赛后补K计时花了20分钟，zzy他们队10分钟，Grammy7分钟，手速还是不够，写代码有点畏手畏脚的。另外，今天做E也出了挺大的锅，直接导致oscar的J没有出来。
== 题解 ==
A: 
B: 对每个i，考虑二分答案，那么就是看i+1~mid的凸包上的情况，凸包可以用线段树分治，二分可以在线段树上二分掉一个log，最终复杂度nlog^2
C: 枚举到根号，判n=1
D: dfs，竟然不需要高精度
E: 中间状态必然单峰，维护一边的状态，转移与lowbit有关
F: 数位dp
G: 回文自动机上dp
H: 暴力
I: 暴力
J: 相当于求权值在l~r之间的最小生成森林，枚举最小权值w后处理出最小权为w的最小生成树，对每个询问分别二分
K: 二分答案，把v值从小到大排序然后DP
L: 区间dp，最远的点一定需要选，枚举选的时间后两边独立

[/wiki/2020-team1 返回]

概述

solved: 7/12 dirt: 65%

rank: 48

流水账

总结

Grammy: 我好像还是在梦游，本来感觉这场大部分题都是我很会的题，但是还是打的稀烂，B出了个假做法，发现假之后就在几个假做法直接反复横跳，丢掉B的时候已经有点晚了，捡起G写的时候脑子也不清楚，dp漏了一种情况（最后过了我也感觉我的dp好像复杂了），这场还有个问题是我没有看过K的题意

Sakuya:赛后补K计时花了20分钟，zzy他们队10分钟，Grammy7分钟，手速还是不够，写代码有点畏手畏脚的。另外，今天做E也出了挺大的锅，直接导致oscar的J没有出来。

题解

A:

B: 对每个i，考虑二分答案，那么就是看i+1~mid的凸包上的情况，凸包可以用线段树分治，二分可以在线段树上二分掉一个log，最终复杂度nlog^2

C: 枚举到根号，判n=1

D: dfs，竟然不需要高精度

E: 中间状态必然单峰，维护一边的状态，转移与lowbit有关

F: 数位dp

G: 回文自动机上dp

H: 暴力

I: 暴力

J: 相当于求权值在l~r之间的最小生成森林，枚举最小权值w后处理出最小权为w的最小生成树，对每个询问分别二分

K: 二分答案，把v值从小到大排序然后DP

L: 区间dp，最远的点一定需要选，枚举选的时间后两边独立

附加文件