DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

工作的达达斯

返回题目

题解

排序与链 将每个模块的候选设计按性能非递减排序,记排序后的性能和消耗量为 bi,j,ci,jb_{i,j},c_{i,j}bi,j​,ci,j​。排序时必须将性能和消耗量成对移动。

di,k=bi,k+1−bi,k≥0(1≤k<Ai).d_{i,k}=b_{i,k+1}-b_{i,k}\geq 0\qquad(1\leq k<A_i).di,k​=bi,k+1​−bi,k​

为模块 iii 建立 Ai−1A_i-1Ai​−1 个顶点 vi,1,…,vi,Ai−1v_{i,1},\ldots,v_{i,A_i-1}v,并令 、。顶点 在源点一侧表示选择的设计编号大于 。对每个 ,加入容量为无穷大的反向边 。有限割中源点侧的顶点必定构成前缀,因此恰好割断一条正向链边。 时也可用一条 的边表示。

乘积的分解 对于一座矿山,按输入顺序将两个模块记为 u,vu,vu,v,选定的性能记为 Bu,BvB_u,B_vBu​,Bv​。

−BuBv=−bv,1Bu−bu,AuBv+bu,Aubv,1+(bu,Au−Bu)(Bv−bv,1).-B_uB_v=-b_{v,1}B_u-b_{u,A_u}B_v+b_{u,A_u}b_{v,1}+(b_{u,A_u}-B_u)(B_v-b_{v,1}).−Bu​B

最后一项等于 ∑k,ldu,kdv,l[vu,k∈T][vv,l∈S]\sum_{k,l}d_{u,k}d_{v,l}[v_{u,k}\in T][v_{v,l}\in S]∑k,l​du,k​d。对所有 、,加入从 到 、容量为 的边。增量为 时可以省略对应边。使用相同模块对的矿山仍须逐一处理。

一元代价与答案恢复

αi=∑k:Uk=ibVk,1+∑k:Vk=ibUk,AUk,qi(j)=ci,j−αibi,j.\alpha_i=\sum_{k:U_k=i}b_{V_k,1}+\sum_{k:V_k=i}b_{U_k,A_{U_k}},\qquad q_i(j)=c_{i,j}-\alpha_i b_{i,j}.αi​= K=1+max⁡(0,max⁡i,j(−qi(j))).K=1+\max\left(0,\max_{i,j}(-q_i(j))\right).K=1+max(0,i,jmax​(−q

对每个 1≤j≤Ai1\leq j\leq A_i1≤j≤Ai​,将正向边 vi,j−1→vi,jv_{i,j-1}\to v_{i,j}vi 的容量设为 ,该值为正。设计选择与有限割一一对应。割容量等于净收益的相反数加上 ,因此求最小割即可。

answer=MK−mincut⁡−∑k=1NbUk,AUkbVk,1.\text{answer}=MK-\operatorname{mincut}-\sum_{k=1}^{N}b_{U_k,A_{U_k}}b_{V_k,1}.answer=MK−mincut−k=1∑

数值范围与复杂度 答案在 −49 998-49\,998−49998 到 999 999 998999\,999\,998999999998 之间。满足 αi≤106\alpha_i\leq10^6αi​≤10、、、。一座矿山的惩罚边容量总和为 。所有有限容量之和小于 ,因此可用 表示无穷大。所有运算均可使用有符号 位整数。

顶点数 V≤452V\leq452V≤452,加入的边数 E≤82 000E\leq82\,000E≤82000,残量反向边另行存储。Dinic 算法的一般时间复杂度为 O(V2E)O(V^2E)O(V2E),空间复杂度为 。

子任务 子任务 1 枚举所有设计组合,时间复杂度为 O((N+M)∏iAi)O((N+M)\prod_i A_i)O((N+M)∏i​Ai​),最多有 10610^6 种组合。子任务 2 中每个模块至多只有一个二元选择,可用每个模块至多一个顶点的最小割解决。子任务 3 使用完整的链。另一份正确程序使用 的阈值展开,以交叉验证两种构造。

Solution written by GPT6

≥
0(1≤
k<
Ai​).
i,1
​
,
…
,
vi,Ai​−1​
vi,0=Sv_{i,0}=Svi,0​=S
vi,Ai=Tv_{i,A_i}=Tvi,Ai​​=T
vi,kv_{i,k}vi,k​
kkk
1≤k≤Ai1\leq k\leq A_i1≤k≤Ai​
vi,k→vi,k−1v_{i,k}\to v_{i,k-1}vi,k​→vi,k−1​
Ai=1A_i=1Ai​=1
S→TS\to TS→T
v
​
=
−bv,1​Bu​−
bu,Au​​Bv​+
bu,Au​​bv,1​+
(bu,Au​​−
Bu​)(Bv​−
bv,1​).
v,l​
[
vu,k​
∈
T][vv,l​∈
S]
1≤k<Au1\leq k<A_u1≤k<Au​
1≤l<Av1\leq l<A_v1≤l<Av​
vv,lv_{v,l}vv,l​
vu,kv_{u,k}vu,k​
du,kdv,ld_{u,k}d_{v,l}du,k​dv,l​
000
k:Uk​=i∑​
bVk​,1​
+
k:Vk​=i∑​bUk​,AUk​​​,qi​(j)=
ci,j​−
αi​bi,j​.
i​
(
j
))
)
.
,
j
−
1
​
→
vi,j​
K+qi(j)K+q_i(j)K+qi​(j)
MK−∑kbUk,AUkbVk,1MK-\sum_k b_{U_k,A_{U_k}}b_{V_k,1}MK−∑k​bUk​,AUk​​​bVk​,1​
N
​
bUk​,AUk​​​
bVk​,1​
.
6
1−109≤qi(j)≤10001-10^9\leq q_i(j)\leq10001−109≤qi​(j)≤1000
K≤109K\leq10^9K≤109
MK≤5⋅1010MK\leq5\cdot10^{10}MK≤5⋅1010
(bu,Au−bu,1)(bv,Av−bv,1)≤9992(b_{u,A_u}-b_{u,1})(b_{v,A_v}-b_{v,1})\leq999^2(bu,Au​​−bu,1​)(bv,Av​​−bv,1​)≤9992
5.01⋅10115.01\cdot10^{11}5.01⋅1011
101510^{15}1015
646464
O(V+E)O(V+E)
O(V+E)
106
−wxy=wx(1−y)−wx-wxy=wx(1-y)-wx−wxy=wx(1−y)−wx