2019-team11/HW8

从 Trac 迁移的文章

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

原文章内容如下：

=== 2019.05.11 2018-2019 CTU Open Contest 总结 By 1em0n Team ===

=== Part 1 流水账 ===

=== Part 2 队员总结 ===

=== 孔畅 ===

=== 夏天鑫 ===

=== 黄彦玮 ===

早上真的不适合训练……以后训练前一天晚上还是要早点睡orz

签到题只有A一个，还因为不知道筛子的形状WA了1发

J题数据范围其实有提示，按位dfs其实不难想……但当时我咬定是个点治就没写，比较可惜

B题真不难，就是个多源bfs，大概是因为我没见过这样的题吧……

I题是好题，但好像没什么人做，而且三个人居然一致认为不好写（虽然确实不好写，调了1h+），其实真说不定能写出来

比较有趣的是我们队两个博弈居然都做出来了……（历史总是惊人的相似）真·博弈队

这次4题其实挺不应该的，虽说状态不佳是主要原因（早上真的困orz），不过有些题没去认真想就扔了也挺不该的

开题节奏慢依然是问题，以后注意。



=== 补题 ===
|| Contest Name                                                                                            || A || B || C || D || E || F || G || H || I || J || K || L || M ||
|| 2018-2019 CTU Open Contest                  || O || Ø || O || . || Ø || O || O || O || Ø || Ø || X || X || X ||
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的

题解：

A：（暴力）给定一个筛子图案，判断点数。————模拟

B：（Bfs）5000*5000平面上n个点，所有小方格的对角线都有边，询问q次，给定一个点，问到最近点的距离。———多源bfs，最初所有点入队即可。

C：（大模拟）根据题意模拟即可。

E：（后缀数组+二分）给定一个字符串，用若干个长为n的串覆盖原串（可重叠），求这n个串字典序最大的那一个最小是多少。————先把原串复制一份（环），二分答案（即串的排名），转化成判断是否存在一个长度小于等于n的串都由rank小于mid的串覆盖。每次判断扫一遍，排名大于它的直接跳过，其它的每一次记录连续的起点和终点，如果有一个连续区间长度大于等于n说明可行。

F：（DP）待补

G：（博弈/搜索）8*8棋盘上有黑白两个马，给定启示位置，轮流走求谁能赢（或平局）。————直接从两个位置模拟轮流走，扩展所有可以走到的位置，谁先吃了对方谁就赢。

H：（博弈）待补

I：（贪心+模拟）平面上有若干个点，问可不可以把这些点连成若干个不重叠的正方形。————从左下角开始贪心连正方形，每次选最小的，连完后删点。

J：（图论/思维）某些楼层间有电梯，每层楼有一个权，每到某一层楼B玩家手中的钱X变为X-X XOR t(B)+t(B)，求游戏结束最多有多少钱。————按位处理（细节不太记得了）

2019.05.11 2018-2019 CTU Open Contest 总结 By 1em0n Team

Part 1 流水账

Part 2 队员总结

孔畅

夏天鑫

黄彦玮

早上真的不适合训练……以后训练前一天晚上还是要早点睡orz

签到题只有A一个，还因为不知道筛子的形状WA了1发

J题数据范围其实有提示，按位dfs其实不难想……但当时我咬定是个点治就没写，比较可惜

B题真不难，就是个多源bfs，大概是因为我没见过这样的题吧……

I题是好题，但好像没什么人做，而且三个人居然一致认为不好写（虽然确实不好写，调了1h+），其实真说不定能写出来

比较有趣的是我们队两个博弈居然都做出来了……（历史总是惊人的相似）真·博弈队

这次4题其实挺不应该的，虽说状态不佳是主要原因（早上真的困orz），不过有些题没去认真想就扔了也挺不该的

开题节奏慢依然是问题，以后注意。

补题

Contest Name A B C D E F G H I J K L M
2018-2019 CTU Open Contest O Ø O . Ø O O O Ø Ø X X X

O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的

题解：

A：（暴力）给定一个筛子图案，判断点数。————模拟

B：（Bfs）5000*5000平面上n个点，所有小方格的对角线都有边，询问q次，给定一个点，问到最近点的距离。———多源bfs，最初所有点入队即可。

C：（大模拟）根据题意模拟即可。

E：（后缀数组+二分）给定一个字符串，用若干个长为n的串覆盖原串（可重叠），求这n个串字典序最大的那一个最小是多少。————先把原串复制一份（环），二分答案（即串的排名），转化成判断是否存在一个长度小于等于n的串都由rank小于mid的串覆盖。每次判断扫一遍，排名大于它的直接跳过，其它的每一次记录连续的起点和终点，如果有一个连续区间长度大于等于n说明可行。

F：（DP）待补

G：（博弈/搜索）8*8棋盘上有黑白两个马，给定启示位置，轮流走求谁能赢（或平局）。————直接从两个位置模拟轮流走，扩展所有可以走到的位置，谁先吃了对方谁就赢。

H：（博弈）待补

I：（贪心+模拟）平面上有若干个点，问可不可以把这些点连成若干个不重叠的正方形。————从左下角开始贪心连正方形，每次选最小的，连完后删点。

J：（图论/思维）某些楼层间有电梯，每层楼有一个权，每到某一层楼B玩家手中的钱X变为X-X XOR t(B)+t(B)，求游戏结束最多有多少钱。————按位处理（细节不太记得了）