2021-team02-008

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team02 返回]

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

= 流水账 =

题目比较简单，依次签了A，G，K，D，F，B，L，J。

pb和cy检查E的题面，救了没过的E。

cxt上机写I。cy会了C，和pb确认C的做法。

最后一个小时，cxt和cy交替上机分别写I和C。

C最后20分钟过了，I赛后枚举题意也很快过了。

= 总结 =

=== pb： ===
又读错题了，噶

=== Creatix： ===
I 题目没说清楚，不太行，不然我觉得稳过。

前面有道签到题太慢了。其实可以早一点下来依靠一下万能的 B 队长。

=== Eden_CY： ===

数组开小爆了一发

给队友少报了题目条件

其他没什么问题


= 题解 =

 * A：简单dp

 * B：答案与放的顺序无关，从左到右dp，f[i]表示左端点到当前点0的个数为i的方案数，只有在i位置只有f[i-a[i]]要转移。

 * C：倒着加入链，并查集加启发式合并维护剩下的链的连通情况。

 * D：将值为1的两个位置连边，有环则线性相关，维护连通性并加边。

 * E：

 * F：

 * G：

 * H：（我并不确定现在的做法是对的。现在的做法基本已经和wxh的代码一致了。我觉得wxh的代码里有至少两个我觉得不合理的地方，不过确实这两个地方加起来就通过了我想的hack数据。）
 首先dp出当前猫和老鼠相邻的时候，还需要多少步才能把老鼠逼死（或者说不是dp，而是最短路）。有两种转移，一是老鼠走一步，猫跟上去；一是老鼠走一步，猫不动，老鼠回来，猫走过去和老鼠重合，老鼠再走过去，猫也走过去，老鼠走回来，猫不动，即花四步交换猫和老鼠的位置，前提是老鼠在猫不动的情况下要愿意走回来。
 然后枚举老鼠在自由的情况下走了几步，看猫能否堵住老鼠的下一条边。注意这里猫是可以跨过老鼠的。

 * I：直接状压 dp，记下当前每个格子是否有方块，状态数为 6^7。

 * J：

 * K：按最长上升子序列长度从小到大，从左到右，递减地放数。

 * L：

[/wiki/2021-team02 返回]

流水账

题目比较简单，依次签了A，G，K，D，F，B，L，J。

pb和cy检查E的题面，救了没过的E。

cxt上机写I。cy会了C，和pb确认C的做法。

最后一个小时，cxt和cy交替上机分别写I和C。

C最后20分钟过了，I赛后枚举题意也很快过了。

总结

pb：

又读错题了，噶

Creatix：

I 题目没说清楚，不太行，不然我觉得稳过。

前面有道签到题太慢了。其实可以早一点下来依靠一下万能的 B 队长。

Eden_CY：

数组开小爆了一发

给队友少报了题目条件

其他没什么问题

题解

  • A：简单dp
  • B：答案与放的顺序无关，从左到右dp，f[i]表示左端点到当前点0的个数为i的方案数，只有在i位置只有f[i-a[i]]要转移。
  • C：倒着加入链，并查集加启发式合并维护剩下的链的连通情况。
  • D：将值为1的两个位置连边，有环则线性相关，维护连通性并加边。
  • E：
  • F：
  • G：
  • H：（我并不确定现在的做法是对的。现在的做法基本已经和wxh的代码一致了。我觉得wxh的代码里有至少两个我觉得不合理的地方，不过确实这两个地方加起来就通过了我想的hack数据。）

首先dp出当前猫和老鼠相邻的时候，还需要多少步才能把老鼠逼死（或者说不是dp，而是最短路）。有两种转移，一是老鼠走一步，猫跟上去；一是老鼠走一步，猫不动，老鼠回来，猫走过去和老鼠重合，老鼠再走过去，猫也走过去，老鼠走回来，猫不动，即花四步交换猫和老鼠的位置，前提是老鼠在猫不动的情况下要愿意走回来。

然后枚举老鼠在自由的情况下走了几步，看猫能否堵住老鼠的下一条边。注意这里猫是可以跨过老鼠的。

  • I：直接状压 dp，记下当前每个格子是否有方块，状态数为 6^7。
  • J：
  • K：按最长上升子序列长度从小到大，从左到右，递减地放数。
  • L：
附加文件