2020-team2-050

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 概述 =

 solved: ??/??

 rank: ??

= 流水账 =

咕

= 总结 =

=== pb： ===
~~这里是总结~~

=== Creatix： ===
~~这里是总结~~

=== yyc： ===
~~这里是总结~~

= 题解 =

 * A：

 * B：

 * C：

 * D：题意：二维平面上有一些加油站，每个加油站有一个油价，油箱有容量，两点距离为曼哈顿距离，问从1走到n，加油不超过t（<=10）次的最小花费。

 考虑对于任意一个最终路径上的点i，若 C[i] >= C[i+1]，则在 i+1 位置油箱会空。

 若 C[i] < C[i + 1]，则i即使加满油也必不能到i+2（否则会跳过i+1)。故在i处油箱会满。

 即，任选路径上两个点，必有一个处于油箱满或油箱空的状态。记f[i][0/1]表示在i，油箱空或满，每次转移1步或两步即可。

 * E：

 * F：

 * G：

 * H：

 * I：

 * J：

 * K：这儿有两位神仙：

 首先证明可以拆分成若干个整块连着一个出头，队伍里3人没人想写拆分，然后想一个更概括性的奇奇怪怪的DFS填充 —— oscar

 只要看到条件说每个点度不小于2，就可以随便填填就填满了 —— CJB

 呜呜呜，学不来

 这里有一个赛场上骗队友去写拆分的人想了一晚上想出来的证明：

 要证明满足条件则一定有解，不妨证明一个更强的结论：若一个连通块除了一个长为1*n(n>=2)的部分外所有点的度数都不小于2，则该连通块有解。

 归纳证明：每次把那个特殊的1*n的段向两边扩展成极长的1*m(m>=n)的段，把1*m的部分用1*2或1*3的基础图形填充，之后发现原图形被分割成了若干个独立的部分，每个部分只有和1*m相邻的部分可能出现度为1，归纳可得该子问题优解。

 * L：

 * M：

[/wiki/2020-team2 返回]

概述

solved: ??/??

rank: ??

流水账

咕

总结

pb：

这里是总结

Creatix：

这里是总结

yyc：

这里是总结

题解

• A：
• B：
• C：
• D：题意：二维平面上有一些加油站，每个加油站有一个油价，油箱有容量，两点距离为曼哈顿距离，问从1走到n，加油不超过t（<=10）次的最小花费。

考虑对于任意一个最终路径上的点i，若 C[i] >= C[i+1]，则在 i+1 位置油箱会空。

若 C[i] < C[i + 1]，则i即使加满油也必不能到i+2（否则会跳过i+1)。故在i处油箱会满。

即，任选路径上两个点，必有一个处于油箱满或油箱空的状态。记f[i][0/1]表示在i，油箱空或满，每次转移1步或两步即可。

• E：
• F：
• G：
• H：
• I：
• J：
• K：这儿有两位神仙：

首先证明可以拆分成若干个整块连着一个出头，队伍里3人没人想写拆分，然后想一个更概括性的奇奇怪怪的DFS填充 —— oscar

只要看到条件说每个点度不小于2，就可以随便填填就填满了 —— CJB

呜呜呜，学不来

这里有一个赛场上骗队友去写拆分的人想了一晚上想出来的证明：

要证明满足条件则一定有解，不妨证明一个更强的结论：若一个连通块除了一个长为1*n(n>=2)的部分外所有点的度数都不小于2，则该连通块有解。

归纳证明：每次把那个特殊的1*n的段向两边扩展成极长的1*m(m>=n)的段，把1*m的部分用1*2或1*3的基础图形填充，之后发现原图形被分割成了若干个独立的部分，每个部分只有和1*m相邻的部分可能出现度为1，归纳可得该子问题优解。

• L：
• M：