首页 > 其他分享 >Codeforces Round 967 (Div. 2) C题 类分治解法

Codeforces Round 967 (Div. 2) C题 类分治解法

时间:2024-08-21 10:53:12浏览次数:13  
标签:pre 967 Codeforces 相邻 input hc Div now 解法

废话不多说, 先上代码

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

相关文章

  • Codeforces Round 967 (Div. 2)
    A.MakeAllEqual题意:给定n个数每次可以选2个相邻的数,并且前面的数不能比后面的数大,并且删除其中的一个。这个数组是循环数组,最后一个数是第一个数的前一个数。问最少操作多少次,可以让剩下的数全都相等。思路:红黑树+一次遍历,记录出现次数最多的数,剩下的数全部删掉即可。总结:看......
  • CodeForces 360D Levko and Sets
    洛谷传送门CF传送门求出\(p\)的原根\(g\),对每个\(a_i\)求出一个\(x_i\)表示\(g^{x_i}\equiva_i\pmod{p}\)(这部分可以BSGS)。之后的表述中\(a_i\)指\(x_i\)。那么集合生成方式相当于初始\(c=0\),每次让\(c\gets(c+a_ib_j)\bmod(p-1)\)。根据裴蜀定......
  • 【LGR-196-Div.4】洛谷入门赛 #26 题A - H 详细题解--优化思路简洁代码(C++,Python语
    前言:    觉得这个比赛很有意思的,都是暴力题,涉及一些细节,难度比较适合刚学编程语言的,可以很好的锻炼基础还有手速,最后两题也是比较有意思,之后也准备更新atc的比赛题解和洛谷的一些高质量比赛题解(算法网瘾就是想参加各种比赛)   如果觉得有帮助,或者觉得我写的好,......
  • Educational Codeforces Round 168 (Rated for Div. 2) D题
    文章目录题目来源题意思路code题目来源D.MaximizetheRoot题意给定一棵n个点的数,根节点为1,每个点都有权值aia_i......
  • Codeforces Round 966 (Div. 3) (A~F)
    文章目录写在前面A-PrimaryTask思路codeB.SeatinginaBus思路codeC-NumericStringTemplate思路codeD-RightLeftWrong思路codeE-PhotoshootforGorillas思路codeF-ColorRowsandColumns思路codeCodeforcesRound966(Div.3)写在前面赛时写的......
  • CF Round 966 Div3
    A给定一个字符串,判断是不是大于等于10210^2102的形式,例如......
  • Codeforces 169 Div2
    AClosestPoint由题意可得三个及以上的点无法插入新的点,只有两个点时可以插入但当两个点间隔为1时同样无法插入先判断,后输出就行#include<bits/stdc++.h>usingnamespacestd;constintN=50;intt,n;inta[N];intmain(){ cin>>t; while(t--){ cin>>n; for(i......
  • 自创CodeForcesHelperv1.0,解决CF太卡和跳题问题,代码持续更新!
    文章目录前言一、方法二、源代码三、使用方法四、效果展示总结前言对于OIers来说,Codeforces是一个很好的外国OJ。洛谷上确实收录了大部分CF的题,但是最近由于Codeforces的cloudflare加强了,所以洛谷的爬虫已经无法正确爬取提交记录的数据了,详见link。我......
  • [AGC064C] Erase and Divide Game
    link感觉题解说的都很不清晰,这里只谈个人理解。考虑操作的本质是什么,两人从低到高确定二进制下的每一位填的数,并且场上只保留对应后缀的数字,当场上没有数字时当前操作者输。设\(f[i,S]\)表示确定了前\(i\)位,填的数为\(S\),接下来先手是否能赢,那么有\(f[i,S]=\neg(f[i......
  • Codeforces Round 894 (Div. 3) D
    题目:E.KolyaandMovieTheatre题目链接:https://codeforces.com/contest/1862/problem/E思路:主要用优先队列存放大于0的元素,然后除了第一个数据后的每m个数据就可以存放到记录数组里面,最后遍历找价值最大的点击查看代码#include<bits/stdc++.h>#defineintlonglongusing......