2020-team1-047

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==

== 总结 ==
Grammy: 开场冲了G，拿下巨大优势，然后尝试在A,E,F中开出一道题，但好像都失败了，于是后面就在摸鱼了啊？
Sakuya:韩国场太毒瘤哩，根本开不动后面的题目。这次D我们队卡了那么久是真的离谱，不过最后那个错误还是挺难发觉的。希望以后不要读错题目。
== 题解 ==
A: 推性质可得合法的充要条件是 sigma i=1 to k ai <= sigma i=1 to k cnti,  cnt[i]是>=i的b的数量，用线段树维护这个合法性
B:
C:
D:从大往小加边，每次连两个集合时两个集合各自任意挑一个点都要连一条目前权值的边。注意同权值的边要一起判-1之后再一起加入。
E:
F: 
G: dp套dp，预处理一些东西优化复杂度
H:二分答案x，把x以后的都变成0（或者1），然后一直把数往小下放，如果已有数大于需求数则把多余的变成0或1，否则把未满足的下放。
I:
J: 撞墙相当于再添加一个反向指令，预处理一个ans[i]表示从（0，0）出发执行后缀s[i...n]但是s[i]取原本反方向的最终结果，那么如果从i出发到一个pos使得重新回到（0，0），则ans[i]=ans[pos]。在暴力的基础上用set优化即可。
K: 对点按坐标字典序排序，然后正着走一遍反着走一遍，同一面上显然不会交叉。
L:

[/wiki/2020-team1 返回]

概述

solved: 5/12 dirt: 55%

rank: 60

流水账

总结

Grammy: 开场冲了G，拿下巨大优势，然后尝试在A,E,F中开出一道题，但好像都失败了，于是后面就在摸鱼了啊？

Sakuya:韩国场太毒瘤哩，根本开不动后面的题目。这次D我们队卡了那么久是真的离谱，不过最后那个错误还是挺难发觉的。希望以后不要读错题目。

题解

A: 推性质可得合法的充要条件是 sigma i=1 to k ai <= sigma i=1 to k cnti, cnt[i]是>=i的b的数量，用线段树维护这个合法性

B:

C:

D:从大往小加边，每次连两个集合时两个集合各自任意挑一个点都要连一条目前权值的边。注意同权值的边要一起判-1之后再一起加入。

E:

F:

G: dp套dp，预处理一些东西优化复杂度

H:二分答案x，把x以后的都变成0（或者1），然后一直把数往小下放，如果已有数大于需求数则把多余的变成0或1，否则把未满足的下放。

I:

J: 撞墙相当于再添加一个反向指令，预处理一个ans[i]表示从（0，0）出发执行后缀s[i...n]但是s[i]取原本反方向的最终结果，那么如果从i出发到一个pos使得重新回到（0，0），则ans[i]=ans[pos]。在暴力的基础上用set优化即可。

K: 对点按坐标字典序排序，然后正着走一遍反着走一遍，同一面上显然不会交叉。

L:

附加文件