2020-team1-046

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 8/11  dirt: 53%
rank: 24
[[Image(Rank.png,800px)]]

== 流水账 ==
感觉这场是构造场啊（？）
开场的一系列提交全是先1发wa再1发A，很神秘
== 总结 ==
Sakuya: 最后放弃C题给oscar写K是挺正确的选择，次日在gay统课上写了两个小时，我吐了。
srand(time(NULL))过不了srand(19260817)居然过了，真神奇。
Grammy今天做了很多构造题，构造完就在跟着榜开了一些贪心和dp，最后救了一下A题，一共写了五题，感觉很爽
== 题解 ==
A: 从小到大考虑答案，根据当前枚举的x，将序列分成很多段，每段内相当于有1,-1，讨论后可以对这个东西的差分数组 （维护每段1的数量+1/2） 的和，用线段树搞
B: dp,f[i][j][k]表示前i个数，第一轮和为j，第二轮和为k的最小代价，要注意两个细节： 要按照第一轮的耗时从小到大对物品排序；转移的时候只有当j<第一轮上限的时候才能对j加。
C: 先二分出最小的pos使得[1,pos]区间包含最小值或最大值，然后用两次操作得出a[pos]以及它是最小值还是最大值。最后二进制分组，每次带上a[pos]和不带上a[pos]得出该集合所有元素。
D: 所有种类出现次数<=n直接排序输出，有一个>n时其余只有一种且<=2无解,>2 aaaabaaabb，两种以上aaaabaaaac、aaaaaaabaaaqwqwq即可
E: 直接枚举车车的数量然后大力贪心
F: 一对点，若一个点是另一个点的祖先就可以匹配，先手必败当前仅当树存在完备匹配
证明：后手策略为选完备匹配中的另一个点。
先手策略为找一个极大匹配，选一个未匹配点，然后每次选匹配中的另一个点。这样操作下去后手一定选不到未匹配点，因为否则就找出了一条增广路，与极大匹配矛盾。
G: 最多直接能选就选，最少倒着贪心匹配一下
H:
I: 找一个i使得离他最近的j离他的距离，是所有i里面最大的。
J: 每个点排序后贪心匹配，这样一定形成若干个环，也就是答案。
K: 机器人只能待在每个方向的表面上，一共6n^2^种状态，转移是一坨屎，写了30+24种转移，每种要更新6个值（

[/wiki/2020-team1 返回]

概述

solved: 8/11 dirt: 53%

rank: 24

流水账

感觉这场是构造场啊（？）

开场的一系列提交全是先1发wa再1发A，很神秘

总结

Sakuya: 最后放弃C题给oscar写K是挺正确的选择，次日在gay统课上写了两个小时，我吐了。

srand(time(NULL))过不了srand(19260817)居然过了，真神奇。

Grammy今天做了很多构造题，构造完就在跟着榜开了一些贪心和dp，最后救了一下A题，一共写了五题，感觉很爽

题解

A: 从小到大考虑答案，根据当前枚举的x，将序列分成很多段，每段内相当于有1,-1，讨论后可以对这个东西的差分数组 （维护每段1的数量+1/2） 的和，用线段树搞

B: dp,f[i][j][k]表示前i个数，第一轮和为j，第二轮和为k的最小代价，要注意两个细节： 要按照第一轮的耗时从小到大对物品排序；转移的时候只有当j<第一轮上限的时候才能对j加。

C: 先二分出最小的pos使得[1,pos]区间包含最小值或最大值，然后用两次操作得出a[pos]以及它是最小值还是最大值。最后二进制分组，每次带上a[pos]和不带上a[pos]得出该集合所有元素。

D: 所有种类出现次数<=n直接排序输出，有一个>n时其余只有一种且<=2无解,>2 aaaabaaabb，两种以上aaaabaaaac、aaaaaaabaaaqwqwq即可

E: 直接枚举车车的数量然后大力贪心

F: 一对点，若一个点是另一个点的祖先就可以匹配，先手必败当前仅当树存在完备匹配

证明：后手策略为选完备匹配中的另一个点。

先手策略为找一个极大匹配，选一个未匹配点，然后每次选匹配中的另一个点。这样操作下去后手一定选不到未匹配点，因为否则就找出了一条增广路，与极大匹配矛盾。

G: 最多直接能选就选，最少倒着贪心匹配一下

H:

I: 找一个i使得离他最近的j离他的距离，是所有i里面最大的。

J: 每个点排序后贪心匹配，这样一定形成若干个环，也就是答案。

K: 机器人只能待在每个方向的表面上，一共6n2种状态，转移是一坨屎，写了30+24种转移，每种要更新6个值（

附加文件