2020-team0x06-011

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team0x06 返回]

[[Image(Standing.PNG, 1000px)]]

== 概述 ==

Summer 2020 - Training 8

== 流水账 ==

开场看见K题签到，'''K1Y9''',然后fx胡出了H题二分答案，然后czyh对答案大小预期错误wa了一发，'''H2Y62'''。czyh开始胡J，fx发现听不懂czyh在胡言乱语什么，开始“你等一下”“你确定是这样？”“你为什么这么写？”,czyh思维混乱难以回答但由于没有人抢机子就在机上面向样例编程，然后突然过样例了,交了就过了'''J1Y157'''。fx溜了，全队陷入僵局。

lmh开场做L，做了1.5h觉得不可做就丢了，然后挂机半场，最后开了D，但因为没考虑周全没写出来。

== 总结 ==

=== ntwbvdbl_oe ===

 * 我是菜鸡

=== Orange_User ===

=== functionendless ===


== 题解 ==

A: 最大流模型明显，经过不明推导后有结论{{{\forall 1 \le k \le n, \sum_{i=1}^k a_i \le \sum_{j=1}^m min(b_j, k}}}}时可行，设c_k为>=k的b_i的数量，则{{{\sum_{j=1}^m min(b_j, k} = \sum_{j=1}^k c_j}}}，线段树维护

B:

C:

D: 在降序边集上合并连通块，每次将相同权值的边同时加入，并要保证每条边两端属于不同连通块，否则不合法

E:

F: 容易转化为费用流模型，发现只用做两次最短路。SPFA会T，可第一次在DAG上DP跑出dis数组，之后对于边(u,v)，w+=dis[u]-dis[v]后跑dij即可（如果还T就试试random_shuffle边集

G:

H: 二分答案，贪心验证。

I:

J: fx：我知道你在写什么，但我不知道为什么这能过 czyh：我不知道我在写什么，但它就是过了。

K：签到

L:

[/wiki/2020-team0x06 返回]

概述

Summer 2020 - Training 8

流水账

开场看见K题签到，K1Y9,然后fx胡出了H题二分答案，然后czyh对答案大小预期错误wa了一发，H2Y62。czyh开始胡J，fx发现听不懂czyh在胡言乱语什么，开始“你等一下”“你确定是这样？”“你为什么这么写？”,czyh思维混乱难以回答但由于没有人抢机子就在机上面向样例编程，然后突然过样例了,交了就过了J1Y157。fx溜了，全队陷入僵局。

lmh开场做L，做了1.5h觉得不可做就丢了，然后挂机半场，最后开了D，但因为没考虑周全没写出来。

总结

ntwbvdbl_oe

  • 我是菜鸡

Orange_User

functionendless

题解

A: 最大流模型明显，经过不明推导后有结论{{{\forall 1 \le k \le n, \sum_{i=1}k a_i \le \sum_{j=1}m min(b_j, k}}}}时可行，设c_k为>=k的b_i的数量，则{{{\sum_{j=1}m min(b_j, k} = \sum_{j=1}k c_j}}}，线段树维护

B:

C:

D: 在降序边集上合并连通块，每次将相同权值的边同时加入，并要保证每条边两端属于不同连通块，否则不合法

E:

F: 容易转化为费用流模型，发现只用做两次最短路。SPFA会T，可第一次在DAG上DP跑出dis数组，之后对于边(u,v)，w+=dis[u]-dis[v]后跑dij即可（如果还T就试试random_shuffle边集

G:

H: 二分答案，贪心验证。

I:

J: fx：我知道你在写什么，但我不知道为什么这能过 czyh：我不知道我在写什么，但它就是过了。

K：签到

L:

附加文件