废话不多说, 先上代码
t = int(input()) while t > 0: n = int(input()) pre_d = {1: [i for i in range(2, n + 1)]} pair_l = [] while len(pre_d) != 0: item = pre_d.items() now_d = {} for k, v in item: for i in v: print('?', k, i) hc = int(input()) if hc == k or hc == i: pair_l.append((k, i)) elif now_d.get(hc) is None: now_d[hc] = [i] else: now_d[hc].append(i) pre_d = now_d print('!',end=' ') for a,b in pair_l: print(a, b,end=' ') t -= 1
此解法思路类似于分治, 我也不知道为什么是对的, 但是过了
大致思路
假设 1 是树的根节点, 我们依次询问 1 和 [2,n] 得到返回的值, 这个值如果等于 1, 就说明 1 和 该数字相邻, 把这个关系保存起来(当我们找到所有的相邻关系时, 直接输出就可以了)
然后我们再依次以返回结果为非 1 的数字作为父节点, 询问上次询问中非 1 的那个数字
思路以此类推
好吧, 我感觉我也讲不太清楚, 那还是直接上图吧
假设我们有这样一个无向树
解法大概是下面这种思路, 从上到下, 从左到右尝试就行
所以最后的结果是:
! 1 3 1 4 4 2 4 6 3 5 5 7
即所有的相邻关系(每队相邻关系的先后无所谓)
如果还没看懂, 请去研究我的代码, 我昨天和我室友讲这个做法, 他也没太理解
ps. 其实对于每次询问, 如果结果是两个询问数中的一个, 就说明两数相邻. 我的这种解法其实就是基于分治思想, 最大化利用每次的返回的结果进行二分查找
标签:pre,967,Codeforces,相邻,input,hc,Div,now,解法 From: https://blog.csdn.net/fruian/article/details/141383373