2021-team1-C05

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team1 返回]
== 概述 ==
solved: 4/14  dirt: 64%
rank: 9
[[Image(2021-C05.png,700px)]]
== 流水账 ==
本场题非常的阴间，因为都要加文件。
Qza 开场发现 F 非常水，很快就签了。Xqj 发现 J 是个签到，Qza 得到题意后便开始尝试用 map 做字符串匹配。然而 WA 了，两人都不知道发生了什么，遂开始目瞪口呆地肉眼调试。而 Csr 说她会 B 了，便上去签 B，签完后见 Qza 和 Xqj 依然没找到错误，便重构了一份 J。写到一半发现个细节，便询问 Xqj 和 Qza，Xqj 听到这个问题后才发现题少读了一句话，遂知道哪里写挂了，改掉便过了这题。然后全队又开始卡题，Xqj 卡 H，Csr 卡 K，Qza 无所事事地开其他题并在纸上写 A 的搜索框架。很久以后，Xqj 和 Csr 分别过掉了 H 和 K。Qza 把题意告知 Xqj 和 Csr 后便自己去肝 A 了。但是很遗憾忘记加两个 flag 导致没有在最后 10min 绝杀。
== 总结 ==
Qza：J 的读题出了很大问题，导致卡题时间过久；I 题没有从最终解的总数量方向考虑，导致思路出现偏差；A 题写挂了一发，加上时间不够，导致没调出来。总体来说做题状态较差。但在本次比赛中，所有题都被开过，不存在因为没读题而导致错失一道简单题的情况。
Csr：
Xqj：
== 题解 ==
A: 爆搜。复杂一点的搜索方式是转着圈搜索，因为边界的拼图一定是有一条边平整的，所以状态比较少，搜起来快。简单点的写法就是将每个拼图的左上角视为这个拼图的代表点，然后将其他位置到左上角的dx和dy计算出来，方便搜索时修改当前局面；搜索时找出当前地图最左边的、没有被填过的点，选一块没用过的拼图拼上去即可。
B: 
C：
D：最小树形图。考虑把任务目标抽象为将所有字符连接到一起，则需要建立虚拟根。虚拟根向每个字符串的第一个字符连又向边，长度为 1；字符串内部每个字符向后一个字符连有向边，长度为 1。然后枚举两个字符串（包括自己和自己），如果两个字符串满足一个的前缀是另一个的子串，则这个子串内的字符向前缀里的字符一一连别，长度为 0。然后跑最小树形图。或者：将每个字符串抽象为点，虚拟根向每个字符串连边，长度为字符串长度；若某个串的子串是另一个串的前缀，则这个串向那个前缀的串连边，长度为那个串的长度减去前缀的长度。然后跑最小树形图。
E：三分。对于 x 方向，凸包内能容下的最长的线段长度是单峰的（y 方向也是），而对于一个确定的 x 长度，取到的最大面积（也就是最大的 y）也是单峰的，所以可以在凸包上三分套三分来求。
F：字符串长度都是 9，所以暴力匹配即可。
G：首先，选出最靠后的那个山头，把最高的塔建上去，则这个塔是能够达到的最高的位置。其他塔可以贪心地建，选取最靠前的没有被阴影挡住的点随便建一座塔。因为上限已经确定了，如果其他的塔可以填满下限到上限的所有长度，则答案就是上限；如果不能，则所有塔一定都被尽可能用到了，所以这样放依然能保证最优。
H：
I：
J：简单的模拟+dp。注意handle前面的@之前一定有空格，注意handle可以结束于末尾。
K：

[/wiki/2021-team1 返回]

概述

solved: 4/14 dirt: 64%

rank: 9

流水账

本场题非常的阴间，因为都要加文件。

Qza 开场发现 F 非常水，很快就签了。Xqj 发现 J 是个签到，Qza 得到题意后便开始尝试用 map 做字符串匹配。然而 WA 了，两人都不知道发生了什么，遂开始目瞪口呆地肉眼调试。而 Csr 说她会 B 了，便上去签 B，签完后见 Qza 和 Xqj 依然没找到错误，便重构了一份 J。写到一半发现个细节，便询问 Xqj 和 Qza，Xqj 听到这个问题后才发现题少读了一句话，遂知道哪里写挂了，改掉便过了这题。然后全队又开始卡题，Xqj 卡 H，Csr 卡 K，Qza 无所事事地开其他题并在纸上写 A 的搜索框架。很久以后，Xqj 和 Csr 分别过掉了 H 和 K。Qza 把题意告知 Xqj 和 Csr 后便自己去肝 A 了。但是很遗憾忘记加两个 flag 导致没有在最后 10min 绝杀。

总结

Qza：J 的读题出了很大问题，导致卡题时间过久；I 题没有从最终解的总数量方向考虑，导致思路出现偏差；A 题写挂了一发，加上时间不够，导致没调出来。总体来说做题状态较差。但在本次比赛中，所有题都被开过，不存在因为没读题而导致错失一道简单题的情况。

Csr：

Xqj：

题解

A: 爆搜。复杂一点的搜索方式是转着圈搜索，因为边界的拼图一定是有一条边平整的，所以状态比较少，搜起来快。简单点的写法就是将每个拼图的左上角视为这个拼图的代表点，然后将其他位置到左上角的dx和dy计算出来，方便搜索时修改当前局面；搜索时找出当前地图最左边的、没有被填过的点，选一块没用过的拼图拼上去即可。

B:

C：

D：最小树形图。考虑把任务目标抽象为将所有字符连接到一起，则需要建立虚拟根。虚拟根向每个字符串的第一个字符连又向边，长度为 1；字符串内部每个字符向后一个字符连有向边，长度为 1。然后枚举两个字符串（包括自己和自己），如果两个字符串满足一个的前缀是另一个的子串，则这个子串内的字符向前缀里的字符一一连别，长度为 0。然后跑最小树形图。或者：将每个字符串抽象为点，虚拟根向每个字符串连边，长度为字符串长度；若某个串的子串是另一个串的前缀，则这个串向那个前缀的串连边，长度为那个串的长度减去前缀的长度。然后跑最小树形图。

E：三分。对于 x 方向，凸包内能容下的最长的线段长度是单峰的（y 方向也是），而对于一个确定的 x 长度，取到的最大面积（也就是最大的 y）也是单峰的，所以可以在凸包上三分套三分来求。

F：字符串长度都是 9，所以暴力匹配即可。

G：首先，选出最靠后的那个山头，把最高的塔建上去，则这个塔是能够达到的最高的位置。其他塔可以贪心地建，选取最靠前的没有被阴影挡住的点随便建一座塔。因为上限已经确定了，如果其他的塔可以填满下限到上限的所有长度，则答案就是上限；如果不能，则所有塔一定都被尽可能用到了，所以这样放依然能保证最优。

H：

I：

J：简单的模拟+dp。注意handle前面的@之前一定有空格，注意handle可以结束于末尾。

K：