2017-Onsite01-team2

从 Trac 迁移的文章

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

原文章内容如下：

[http://www.cc98.org/topic/4734313 2017 CCPC 哈尔滨赛区小结By chenjb @Legilimens]
=== chenjb ===
继续练吧，青岛fighting！
=== oipotato ===
难得来写一次总结。。今天其实前中后期都挺坎坷的，但是全程三个人其实都不是很慌，还是很稳的一道道题开出来，作为一支第一次参加比赛的队伍，这样的表现还是不错的，主要原因就是之前训的多了，遇到过各种情况，各种崩盘，所以在逆风局心态上个人认为我们三个人比之前好了太多。封榜前是第三，其实在sub上机敲C的时候有悄悄跟cjb讲过几句觉得有希望拿杯，也都觉得如果C开出来就稳了，努力想开D也因为太菜了没看出结论，直接被数据范围引诱向了一个不太对的方向。最后C没过有点遗憾，结果出来前还BB了一波复旦不会超过我们的N中情况，风随烟结束后跑进来喊的三声OK吹响了我们捧杯失败的号角。赛后cjb得知复旦10题的时候挺惊讶的，说实话很佩服他们的韧性和封榜后的过题能力，在几何题WA了15发之后还能顽强的找到错误再过两题真的是不容易，还是得学习一个。cjb觉得相比题数被碾压，可能复旦同题数反杀我们会好受一点，其实我倒觉得这样挺好，最后一小时C有点慌没调出来，前期有点不顺导致后期来不及搞C，D，K题应该早点捏小数据发现致命错误，诸如此类的理由在被题数碾压之后都没必要说出口了，的确是技不如人，是菜。虽然输的心服口服，但是我们还会回来的，菜就多练，会复仇的。Legilimens never give up
=== subconscious  ===
== 题解 ==
 * C：
 * D：emmmmm.找到距离最远的一对有人的点，答案就是dist/2向下取整...感受一下大概就是每一次最远的一对人都会往里收缩....
 * E：题目大意：N*N的网格放服务器，有些网格不能放，有些网格已经放好服务器。服务器有K种类型。给出T个group，每个group为K个网格，表示这组的K个网格放的服务器的种类必须两两不同。求对于剩余的能放服务器的格子，有多少满足限制的放置方案。[[BR]]     做法：数据范围都很小，但是爆搜还是过不了的。考虑转化成精确覆盖问题用dancing link。构造一个（N*N*K）* (N*N+T*K)的01矩阵。行用来表示某个格子的类型。列用来限制，前N*N列用于限制每个格子只有一种服务器类型，后T*K个列用于限制每个group，每种服务器都必须恰有一个。
 * G：题目大意：给出一段代码。求最少执行几遍，能使得所有statement语句都被执行。[[BR]]    做法：把一段连续的没有发生跳转的语句抽象成一个点。这样抽象出的点最多200个。把强连通分量缩在一起后，就变成求有向无环图的最小路径覆盖，floyd传递闭包后可以转化为一个二分图匹配问题。复杂度为O（N^3^），N为关键点数。
 * I：


== 补题 ==

2017 CCPC 哈尔滨赛区小结By chenjb @Legilimens

chenjb

继续练吧，青岛fighting！

oipotato

难得来写一次总结。。今天其实前中后期都挺坎坷的，但是全程三个人其实都不是很慌，还是很稳的一道道题开出来，作为一支第一次参加比赛的队伍，这样的表现还是不错的，主要原因就是之前训的多了，遇到过各种情况，各种崩盘，所以在逆风局心态上个人认为我们三个人比之前好了太多。封榜前是第三，其实在sub上机敲C的时候有悄悄跟cjb讲过几句觉得有希望拿杯，也都觉得如果C开出来就稳了，努力想开D也因为太菜了没看出结论，直接被数据范围引诱向了一个不太对的方向。最后C没过有点遗憾，结果出来前还BB了一波复旦不会超过我们的N中情况，风随烟结束后跑进来喊的三声OK吹响了我们捧杯失败的号角。赛后cjb得知复旦10题的时候挺惊讶的，说实话很佩服他们的韧性和封榜后的过题能力，在几何题WA了15发之后还能顽强的找到错误再过两题真的是不容易，还是得学习一个。cjb觉得相比题数被碾压，可能复旦同题数反杀我们会好受一点，其实我倒觉得这样挺好，最后一小时C有点慌没调出来，前期有点不顺导致后期来不及搞C，D，K题应该早点捏小数据发现致命错误，诸如此类的理由在被题数碾压之后都没必要说出口了，的确是技不如人，是菜。虽然输的心服口服，但是我们还会回来的，菜就多练，会复仇的。Legilimens never give up

subconscious

题解

• C：
• D：emmmmm.找到距离最远的一对有人的点，答案就是dist/2向下取整...感受一下大概就是每一次最远的一对人都会往里收缩....
• E：题目大意：N*N的网格放服务器，有些网格不能放，有些网格已经放好服务器。服务器有K种类型。给出T个group，每个group为K个网格，表示这组的K个网格放的服务器的种类必须两两不同。求对于剩余的能放服务器的格子，有多少满足限制的放置方案。
  做法：数据范围都很小，但是爆搜还是过不了的。考虑转化成精确覆盖问题用dancing link。构造一个（N*N*K）* (N*N+T*K)的01矩阵。行用来表示某个格子的类型。列用来限制，前N*N列用于限制每个格子只有一种服务器类型，后T*K个列用于限制每个group，每种服务器都必须恰有一个。
• G：题目大意：给出一段代码。求最少执行几遍，能使得所有statement语句都被执行。
  做法：把一段连续的没有发生跳转的语句抽象成一个点。这样抽象出的点最多200个。把强连通分量缩在一起后，就变成求有向无环图的最小路径覆盖，floyd传递闭包后可以转化为一个二分图匹配问题。复杂度为O（N³），N为关键点数。
• I：

补题