搜狗2019秋招研究员试卷部分编程题合集（第二场）

定义如下图所示的比赛地图：
 
S表示比赛起点，E表示比赛终点。实线表示陆路，虚线表示水路。兔子只能走陆路，乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟足够聪明，问谁先到达终点。
输入描述： 第1行输入v1，v2。v1是兔子的速度，v2是乌龟的速度（水路、陆路速度相同）。第2行输入n,m，点的编号是1~n,然后是m行，其中1是起点，n是终点（路径本身不限定方向）。下面m行4个数 a, b, d, c，表示a和b之间有一条边，且其长度为d，类型是c（0表示陆路，1表示水路）。最后一行是end，表示输入结束。输入保证1和n之间至少有一条路径联通。(1&ltn<=10000, 0&ltm<=1000000)。输入样例： 10 5 3 3 1 2 30 0 2 3 20 0 1 3 20 1 end 输出描述： 输出-1,0,1中的一个数。-1表示乌龟获胜，1表示兔子获胜，0表示同时到达终点。输出样例 -1

一群探险家被困古巴比伦迷宫 ，经过努力，探险家破译出了密码。原来通关需要先打开前方的M个机关的任意一个或多个为打开状态，然后关闭所有机关才能安全通过。探险家还发现了一种带有凸起的圆盘，圆盘可以用来同时反转若干个机关的状态（打开状态反转为关闭状态，关闭状态反转为打开状态，这若干个机关必须同时反转）。为了速记，探险家们用十六进制数字表示一个圆盘。如圆盘能同时控制第3、4、5个开关，圆盘就记为1C（11100）。每次操作一个圆盘，比特位为1的位置的机关同时被反转；而且每个圆盘使用一次后就会碎掉。目前探险家收集到了N个圆盘，问现在探险家可以顺利走出迷宫么？

若探险家手里有0、1、2、3、5五个圆盘，M=7，由于存在1 xor 2 xor 3 = 0， 因此结果是yes；
若探险家手里有0、1、2、2、5五个圆盘，M=7，由于存在2 xor 2 = 0， 因此结果是yes；
若探险家手里有0、1、3、5、9五个圆盘，M=7，由于不存组合使得 xor = 0， 因此结果是no。

输入描述： 包含多组数据，第一行是数据组数。

每组数据中首行为M N，M为机关个数，M <= 360(大部分情况下小于40)，N为圆盘个数,
N<=50000；其余为N行圆盘的16进制ID，可以保证每行输入小于2^M输入样例： 2 2 3 0 2 2 5 2 4 1C 输出描述： 每组一行输出，满足条件输出yes，反之输出no输出样例 yes no