HBC237536[SCOI2010]游戏,图论,图匹配,数据结构,并查集,搜索Swapping Game题解 （ffhasnmathitnndogsnumbered）

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

FF has nmathit nn dogs numbered 1,2,3,...,n1,n1,2,3,...,n-1,n1,2,3,...,n1,n. At the beginning, the dogs are arranged by their number in ascending order. They are playing a swapping game, the rules of game are as follows: 1. The dogs will swap in every second. 2. If the current number of seconds is odd, then swap the dog which index is 2i12*i-12i1 and 2i2*i2i. For example, if n=5mathit n=5n=5, the sequence of dogs is 1,2,3,4,51,2,3,4,51,2,3,4,5 and the current time at the beginning, then the dogs will be 2,1,4,3,52,1,4,3,52,1,4,3,5 after 1-st second. 3. If the current number of seconds is even, then swap the dog which index is 2i2*i2i and 2i+12*i+12i+1. For example, if n=5mathit n=5n=5, the sequence of dogs is 2,1,4,3,52,1,4,3,52,1,4,3,5 and the current time is 2, then the dogs will be 2,4,1,5,32,4,1,5,32,4,1,5,3 after 2-nd seconds. FF wants to know, what is the index of the dog numbered qmathit qq after kkk seconds.

FF has nmathit nn dogs numbered 1,2,3,...,n−1,n1,2,3,...,n-1,n1,2,3,...,n−1,n. At the beginning, the dogs are arranged by their number in ascending order. They are playing a swapping game, the rules of game are as follows: 1. The dogs will swap in every second. 2. If the current number of seconds is odd, then swap the dog which index is 2∗i−12*i-12∗i−1 and 2∗i(1≤i≤⌊n2⌋)2*i(1 leq i leq lfloor frac{n}{2} rfloor)2∗i(1≤i≤⌊2n​⌋). For example, if n=5mathit n=5n=5, the sequence of dogs is 1,2,3,4,51,2,3,4,51,2,3,4,5 and the current time at the beginning(current time is 1), then the dogs will be 2,1,4,3,52,1,4,3,52,1,4,3,5 after 1-st second. 3. If the current number of seconds is even, then swap the dog which index is 2∗i2*i2∗i and 2∗i+1(1≤i≤⌊n−12⌋)2*i+1(1 leq i leq lfloor frac{n-1}{2} rfloor)2∗i+1(1≤i≤⌊2n−1​⌋). For example, if n=5mathit n=5n=5, the sequence of dogs is 2,1,4,3,52,1,4,3,52,1,4,3,5 and the current time is 2, then the dogs will be 2,4,1,5,32,4,1,5,32,4,1,5,3 after 2-nd seconds. FF wants to know, what is the index of the dog numbered qmathit qq after kkk seconds.

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC237536[SCOI2010]游戏 图论 图匹配 数据结构 并查集 搜索Swapping Game题解