【Nowcoder 上海五校赛】1 + 2 = 3?
题目描述
小Y在研究数字的时候,发现了一个神奇的等式方程,他屈指算了一下有很多正整数x满足这个等式,比如1和2,现在问题来了,他想知道从小到大第N个满足这个等式的正整数,请你用程序帮他计算一下。
(表示按位异或运算)
输入描述:
第一行是一个正整数,表示查询次数。
接着有T行,每行有一个正整数,表示小Y的查询。
输出描述:
对于每一个查询N,输出第N个满足题中等式的正整数,并换行。
输入
4 1 2 3 10
输出
1 2 4 18
题解
首先我们可以打表,在数据小的情况下找规律:
在1~100之间找出满足规律的数,并转成二进制
--------------------------------
第1个数 1 1 // 二进制1位的个数为1
第2个数 2 10 // 二进制2位的个数为1
第3个数 4 100 // 二进制3位的个数为2
第4个数 5 101
第5个数 8 1000 // 二进制4位的个数为3
第6个数 9 1001
第7个数 10 1010
第8个数 16 10000 // 二进制5位的个数为5
第9个数 17 10001
第10个数 18 10010
第11个数 20 10100
第12个数 21 10101
第13个数 32 100000 // 二进制6位的个数为8
第14个数 33 100001
第15个数 34 100010
第16个数 36 100100
第17个数 37 100101
第18个数 40 101000
第19个数 41 101001
第20个数 42 101010
第21个数 64 1000000 // 二进制7位的个数为13
第22个数 65 1000001
第23个数 66 1000010
第24个数 68 1000100
第25个数 69 1000101
第26个数 72 1001000
第27个数 73 1001001
第28个数 74 1001010
第29个数 80 1010000
第30个数 81 1010001
第31个数 82 1010010
第32个数 84 1010100
第33个数 85 1010101
--------------------------------
结果我们发现答案在二进制下其位数是满足斐波那契规律的
例:当N等于70时,答案的二进制为:100100010
① 70-1-1-1-2-3-5-8-13-21=15
可知1+1+1+2+3+5+8+13+21=55,即9位二进制(第55个数对应100000000)
② 15-1-1-1-2-3-8=0
可知1+1+1+2+3+5+8=15,即6位二进制(第15个数对应100010)
③ 相加可得100100010,转换为十进制即为290
所以得把给定的n拆成几个斐波那契数的和,并标记一下每次用到第几个斐波那契数,每次num加上1<<(pos-1)即可。
得好好学学左移运算符啦!!!!
#include<bits/stdc++.h> using namespace std; int main() { long long a[65],num,n,d; int t,i; a[0]=a[1]=a[2]=1; for (i=3;i<60;i++) a[i]=a[i-1]+a[i-2]; cin>>t; while(t--) { cin>>n; num=0; while(n) { i=0; while(n>=a[i]) { n-=a[i]; i++; } d=1; num+=(d<<(i-1)); } cout<<num<<endl; } return 0; }
上一篇: 撞五花肉了,尴尬不
下一篇: HTML 练习js代码位置在head标签