2021-team06-C210921

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(210921-standing.png,800px)]]

== submission ==

[[Image(210921-submission1.png,800px)]]
[[Image(210921-submission2.png,800px)]]


== 概述 ==

solved: 11/13  dirt: 26.67%

rank: 7



==  ==

== 总结 ==

whn:
整体状态不错，前期签到过程非常顺利，前八个签到题都没有罚时。直到F因为板子来源出错。
F题的dinic和C题的两圆求交点的已有板子都不全，需要及时收录；在学习时不能指望当时学会了就不管了。
后半程机时这次有些空的多，底力提升后面对剩下CG之类的局面，G还是要冲的。


== 题解 ==

A: 签到，枚举一个数看另一个数是否在6以内即可。

B: yja

C: 大致思路是分类讨论，先后处理1根，2根，3根绳子绷紧时的情况。
只有一根绳子和两根绳子绷紧时是平面几何问题；三根绳子则需要考虑三角形三个顶点作半径为绳长的球可得到的交点。这一问题的基本思路是，先求出两个球交出来的平面，第三个球也要对平面作交，然后转换成两圆求交点问题。y

D：策略显然是能赢则赢，否则能平则平，直接贪心即可。

E：yja

F：费用流，对每条边新建点，超级源到边点(1容量，0费用），边点到两个顶点(1,0)，所有顶点到超级汇有(a[u],0)和(∞,1)两条边，跑费用流即可。

G：题目总共有三个要求：段数、最小和与最大字典序。问题分为两部分：求解每段和的最小值和最大化字典序。

每段和的最小值部分：二分每段允许的最大sum,则如果能设法dp出最大、最小段数，那么k只要夹在中间就会合法，r=mid;否则l=mid.
dp过程需要先离散化每个sum(a[i])的后缀（由于树状数组下标不好设置成0所以是后缀）s[i]，然后维护一个pair树状数组记录sum>=某个离散值所能得到的最大&最小段数.从s[n]到s[1]枚举后缀，每次查询lower_bound(s[i]-w)的最小和最大段数，然后+1更新f[i]和树状数组。最后检查f[1].fi <= k && k<= f[1].se是否成立。

*树状数组维护后缀时，modify操作要从i到0更新，query则要i到n+1。

最大化字典序部分：现在已经得到每个后缀i在答案下能分出的最大和最小段数。
考虑现在的三个要求：sum,段数和字典序。
合并处理方法：
①将每个位置的最大和最小段数处理成事件（最大段进入，最小段-1离开）离散化每个sum(a[i])和sum(a[i])-w;维护一棵线段树，以这些值作为下标，记录“sum的最大位置”；再对每个离散值开一个set维护当前能到这些离散值的有哪些位置。
②然后是处理事件：对于每个进入事件，在对应的sum位置（离散值位置）的set添加其后缀坐标；离开时间则删除之，然后无论进入和离开，都需并以处理后的set的最大值更新线段树的sum位置。
③实际问题：先处理所有涉及段数>=k的事件，然后设置一个位置指针now=1，再处理段数k-1到0的事件（从某个k位置转移到k-1位置，意为在这两个位置划分出一段，并且新的后缀由于能划分出k-1段，最终将保证有一种合法方案）
在每个后面时间点，处理完事件之后，查询线段树(sum[now]-w)到maxsum的最大值（即最靠后的位置）cur，更新之，记录答案（cur-now)，然后再将后缀now+1到cur从线段树移除避免重复转移。处理完所有事件之后算法结束。


H：模拟，“日语很难”。

I：二分答案后得到我们有多少个1，2，3，接下来就是贪心处理打怪。考虑如果只有1，2的情况必定是每个怪先尽可能用2打到剩<2血或用完2，然后用1收工；但在有3的情况下可能会导致模3余1的数与卡2冲突浪费1伤害，在浪费过多时会误判打怪结果，重点在于解决这个。采用如下方式预处理3：先把所有血量大于等于3且为奇数的怪打一下3，然后将两张三组合为6按照上面的规则打一遍，再按照上面的思路按3，2，1顺序贪心即可。只需考虑这样做，必定会尽可能无浪费的用完3，且通过保证剩下血量都是偶数避免2的浪费，便可知正确性。

J: 模拟，不过细节有些多，待lxy补充

K: 签到，按照1,k+1,...,2,k+2,...这样构造即可。

L: 跑100次bfs即可，每次将所有新available的火锅店加入初始队列，就可以一遍bfs解决所有点到任意新火锅店的最短距离了。

M: 可以到机场的人的速度必然是最大的若干个；因此把速度从大到小排序，维护一个指针，每次延误时推进指针即可。

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 11/13 dirt: 26.67%

rank: 7

总结

whn:

整体状态不错，前期签到过程非常顺利，前八个签到题都没有罚时。直到F因为板子来源出错。

F题的dinic和C题的两圆求交点的已有板子都不全，需要及时收录；在学习时不能指望当时学会了就不管了。

后半程机时这次有些空的多，底力提升后面对剩下CG之类的局面，G还是要冲的。

题解

A: 签到，枚举一个数看另一个数是否在6以内即可。

B: yja

C: 大致思路是分类讨论，先后处理1根，2根，3根绳子绷紧时的情况。

只有一根绳子和两根绳子绷紧时是平面几何问题；三根绳子则需要考虑三角形三个顶点作半径为绳长的球可得到的交点。这一问题的基本思路是，先求出两个球交出来的平面，第三个球也要对平面作交，然后转换成两圆求交点问题。y

D：策略显然是能赢则赢，否则能平则平，直接贪心即可。

E：yja

F：费用流，对每条边新建点，超级源到边点(1容量，0费用），边点到两个顶点(1,0)，所有顶点到超级汇有(a[u],0)和(∞,1)两条边，跑费用流即可。

G：题目总共有三个要求：段数、最小和与最大字典序。问题分为两部分：求解每段和的最小值和最大化字典序。

每段和的最小值部分：二分每段允许的最大sum,则如果能设法dp出最大、最小段数，那么k只要夹在中间就会合法，r=mid;否则l=mid.

dp过程需要先离散化每个sum(a[i])的后缀（由于树状数组下标不好设置成0所以是后缀）s[i]，然后维护一个pair树状数组记录sum>=某个离散值所能得到的最大&最小段数.从s[n]到s[1]枚举后缀，每次查询lower_bound(s[i]-w)的最小和最大段数，然后+1更新f[i]和树状数组。最后检查f[1].fi <= k && k<= f[1].se是否成立。

*树状数组维护后缀时，modify操作要从i到0更新，query则要i到n+1。

最大化字典序部分：现在已经得到每个后缀i在答案下能分出的最大和最小段数。

考虑现在的三个要求：sum,段数和字典序。

合并处理方法：

①将每个位置的最大和最小段数处理成事件（最大段进入，最小段-1离开）离散化每个sum(a[i])和sum(a[i])-w;维护一棵线段树，以这些值作为下标，记录“sum的最大位置”；再对每个离散值开一个set维护当前能到这些离散值的有哪些位置。

②然后是处理事件：对于每个进入事件，在对应的sum位置（离散值位置）的set添加其后缀坐标；离开时间则删除之，然后无论进入和离开，都需并以处理后的set的最大值更新线段树的sum位置。

③实际问题：先处理所有涉及段数>=k的事件，然后设置一个位置指针now=1，再处理段数k-1到0的事件（从某个k位置转移到k-1位置，意为在这两个位置划分出一段，并且新的后缀由于能划分出k-1段，最终将保证有一种合法方案）

在每个后面时间点，处理完事件之后，查询线段树(sum[now]-w)到maxsum的最大值（即最靠后的位置）cur，更新之，记录答案（cur-now)，然后再将后缀now+1到cur从线段树移除避免重复转移。处理完所有事件之后算法结束。

H：模拟，“日语很难”。

I：二分答案后得到我们有多少个1，2，3，接下来就是贪心处理打怪。考虑如果只有1，2的情况必定是每个怪先尽可能用2打到剩<2血或用完2，然后用1收工；但在有3的情况下可能会导致模3余1的数与卡2冲突浪费1伤害，在浪费过多时会误判打怪结果，重点在于解决这个。采用如下方式预处理3：先把所有血量大于等于3且为奇数的怪打一下3，然后将两张三组合为6按照上面的规则打一遍，再按照上面的思路按3，2，1顺序贪心即可。只需考虑这样做，必定会尽可能无浪费的用完3，且通过保证剩下血量都是偶数避免2的浪费，便可知正确性。

J: 模拟，不过细节有些多，待lxy补充

K: 签到，按照1,k+1,...,2,k+2,...这样构造即可。

L: 跑100次bfs即可，每次将所有新available的火锅店加入初始队列，就可以一遍bfs解决所有点到任意新火锅店的最短距离了。

M: 可以到机场的人的速度必然是最大的若干个；因此把速度从大到小排序，维护一个指针，每次延误时推进指针即可。

附加文件