问题:
我们得到了一系列二进制字符串。这个系列的第一项是0。因此,T1="0"。为了在任何给定的Ti处找到字符串,我们查看Ti-1,并将所有出现的"0"替换为"01",将"1"替换为"10"。给定两个整数N和X,您的工作是找到TN并返回其第X个索引。注:Ti为1-索引。
输入格式:
输入的第一行包含一个整数T,表示测试用例。接下来的T行包含两个空格分隔的整数,N和X.
输出格式:
打印第N行中的第X个索引
样本输入:
1
4 5
样本输出:
1
说明:
T1: '0'
T2: '01'
T3: '0110'
T4: '01101001'
T4中的第5个元素是"1"。
我尝试了下面的解决方案,但n值大于25时超过了时间限制。如何处理大型测试用例?
from sys import stdin , setrecursionlimit
setrecursionlimit(10**8)
t = int(input())
def temp(s,n):
if n==0:
return s
ans = ''
d = {
'0':'01',
'1':'10'
}
for ele in s:
ans+=d[ele]
return temp(ans,n-1)
while t:
n,x = [int(x) for x in stdin.readline().strip().split()]
s = '0'
res = temp(s,n)
print(res[x-1])
t-=1
试试这个。您可以使用迭代(for
循环(而不是递归:
# Iterative function to get T(i)
def T(i): # Define function
l = '0' # Variable that holds the last value in the sequence
for _ in range(i-1): # Iterate i-1 times
d = {'0': '01', '1': '10'} # Just like in your code
l = ''.join(map(d.get, l)) # Equivalent to ''.join(d[c] for c in l)
return l # Return the last value
r = int(input()) # Number of test cases
while r: # Just like in your code
n, x = map(int, input().split()) # Get n and x as input, and convert to integer
print(T(n)[x-1]) # Get T(n) and get the xth index
r -= 1 # Decrement r by 1
输入:
1
4 5
输出:
1
生成的元素有一个模式。
0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
那个模式是nextElement
就是previousElement + flipallbits(previousElement)
。并尝试形成一个递归关系来查找特定索引中的位。
假设一个索引是4,那么它就是索引0的翻转运算。
假设一个索引为5,则为索引1的翻转操作。哪个插管是索引0的翻转操作。
因此,您必须从索引中移除2的最高幂,然后翻转位,如果索引为0,则返回0。
x = 3
def findElement(x):
if(x == 0):
return False
power = 1
while (power*2) <= x:
power *= 2
return not findElement(x - power)
print(int(findElement(x)))
在这个实现中不需要n。另一个选项是计数,即索引x的二进制表示中的1的数量,并检查是否为偶数。如果其偶数返回0,则返回1。
你只需要看到模式,其中奇数到偶数的转换是前一个字符串+它的反向,而偶数到奇数的转换是上一个字符串+值的补码
这是代码
def function(n, x):
tmp = ['0']
if n==0:
if x>len(tmp)-1:
return -1
elif x<=len(tmp)-1:
return tmp[x]
for i in range(1, n):
if not i%2:
tmp = tmp + tmp[::-1]
else:
tmp = tmp + ['0' if i=='1' else '1' for i in tmp]
if x<=len(tmp)-1:
return tmp[x]
return -1
如果索引超出范围,则为-1
。
def find_character(N, X):
if N == 1:
return "0" if X == 1 else "1"
mid = 2**(N-1)
if X <= mid:
return find_character(N-1, X)
else:
return "1" if find_character(N-1, X-mid) == "0" else "0"
# Taking input
T = int(input())
for _ in range(T):
N, X = map(int, input().split())
# Calling the function
result = find_character(N, X)
print(result)
def find_character(N,X(:如果N==1:返回";0";如果X==1;1〃;
mid = 2**(N-1)
if X <= mid:
return find_character(N-1, X)
else:
return "1" if find_character(N-1, X-mid) == "0" else "0"
T=int(input(((
对于范围(T(内的_:N、 X=映射(int,input((.split(((结果=find_character(N,X(打印(结果(