信息学集训队作业林希德0022visit

1、IOI2003国家集训队 难题讨论活动阶段IVPAGE PAGE 4访问解题报告金陵中学 林希德【题目大意】有一列客户，当客户x向顾问咨询以后，该顾问根据x的性别指示客户x + 1到顾问(male)处或(female)处。这样，新的顾问为客户x+1服务。请你找出最短的客户队列，使得不论咨询从哪个顾问开始，队伍的最后一个客户总遇到顾问。【解决情况】两种算法：1、利用无判重的BFS在0.83s内通过原始测试数据，其中时间复杂度，空间复杂度不超过60M（其中是最短客户队列的长度）。2、利用“动态规划 + 反向搜索”在0.22s内较好解决原始测试数据，复杂度无法估算；总的来说，两种算法都具备较好的实战

2、性，可惜没能将问题彻底解决。【算法梗概】算法1：是客户1可能访问的顾问集合。如果客户1为女性，那么客户2可能访问的顾问集合为；如果客户1为男性，那么客户2可能访问的顾问集合为。根据这样的规则，我们用BFS不断扩展出客户3、客户4、客户5可能访问的顾问集合，直到找到某大小为1的集合，即是问题答案。算法2：布尔函数表示是否存在分别从顾问i和顾问j出发，客户1为女性且长度为k的访问队列。定义类同。利用动态规划不断求出GF和GM的值，一旦存在整数k满足或者全部为真，立刻用反向搜索，判断是否已经找到合法队列。【讨论收获与感谢】当可行解需满足的条件十分苛刻不易求解时，转而寻找满足部分易求解条件的解也不失为

3、一种有效策略。【正文】 一、算法1算法描述：因为问题要求“咨询可以开始于任何顾问”，所以客户1可能访问的顾问集合必然是，这与访问队列的具体内容无关。如果是第k个客户可能访问的顾问集合，那么第k + 1个客户的访问集合就应该是（假设客户k是女性）或者（假设客户k是男性）。我们用一个长度为n的布尔数组保存访问集合，然后根据上述规则BFS依次扩展出客户2、客户3、客户4的访问集合。过程如下： pp1 = 1，p2 = 1，p1 = 1n；While p1 = p2 doPp2+1 = 空集，Pp2+2 = 空集；For i = 1 n do If i在集合Pp1中 ThenPp2+1 = Pp2+1

4、 + Fi；Pp2+2 = Pp2+2 + Mi； End If If | Pp2+1 | 或者 | Pp2+2 | = 1 Then 输出访问队列，退出程序； p2 = p2 + 2，p1 = p1 + 1；End while复杂度分析：因为路径不相同，所以客户可能的访问集合恰有个，因此算法1的总复杂度决定于最短访问队列的长度T，即为。本题中N = 40，时空复杂度上限高达，因此，在BFS的过程中我们无奈地选择了不判重。尽管由集合Pp1扩展到集合Pp2时，元素个数不会增加，但也不保证严格减少。所以，一旦出现循环，不判重的BFS将扩展出无限多的元素，我们只能考虑当P2大到一定程度以后即退出Wh

5、ile，输出无解。二、算法2算法描述：算法2实则是个静态规划的过程。定义布尔函数= true表示存在队列S满足：S1 = F；S的长度不超过k；分别从顾问i和顾问j出发，队列末端的顾客将遇到同一个顾问；的定义类同。易知， = 或者 或者，= 或者或者。 我们以k的增长来划分DP阶段，一旦发现k满足或者全部为真，立刻用“反向搜索”判断是否已经找到合法队列。“反向搜索”过程如下： U= (x,y)；x,yU= (x,y)；x,y1.n；Search（U,k,空串）；void Search(集合 U；整数k；字符队列str)如果k = 0 那么输出str、结束所有程序；fv = GFi,j,k（i,

6、j）属于U）均为真；mv = GMi,j,k（i,j）属于U）均为真；If fv为真 ThenV = (Fi,Fj)：(i,j)属于U；Search(V，k - 1，str + F)；End ifIf mv为真 ThenV = (Mi,Mj)：(i,j)属于U；Search(V，k - 1，str + M)；End if当然，如果某时出现=并且=，那么就停止静态递推而输出无解。算法2的主要根据就是：自认为出针对性的大数据实在不容易。 复杂度分析：空间复杂度 = DP的状态数 = 。时间复杂度 = DP的复杂度 + 反向搜索的复杂度 = + ；算法2的时间复杂度理论值较高，但实际远达不到。三、算法比较如果本题的数据规模只有20左右（事实上，官方测试数据最大为19），那么判重的BFS即算法1在理论上是时空都可以承受的NP算法。不过，从实际运行效果看，算法2比算法1要好