q=(5√+1)2，在黄金系统下面a0a1...an等于 ∑ni=0ai∗qn−i ，其中 ai 是0或者1。
现在给出两个黄金系统下面的数字，请比较他们的大小。
Input
单组测试数据。
第一行有一个字符串A。
第二行有一个字符串B。
按照a0到an的顺序输入。
他们都是非空串，可能有前导0，并且只有0和1组成，长度不超过100000。
Output
如果A>B，输出>；
如果A=B，输出=；
如果A<B，输出<；
Input示例
00100
11
Output示例
=
思路：打个表 可以发现 qi 是一个类斐波那契数列
因为字符串长度 最大到100000 所以 肯定会爆 long long
既然是类斐波那契数列
我们就有 qn == qn-1 *qn-2
证明：q2=(√5+1)2/4=(5+1+2√5)/4=(3+√5)/2=1+(1+√5)/2=1+q
所以n>=2时有qn=qn−2∗q2=qn−2(q+1)=qn−1+qn−2
我们可以用 f[i] 表示 qi 的系数
我们可以用 1 表示 字符串a的第 i 位 存在 一个1
-1 表示 字符串的b第 i 位 存在一个 1
当字符串a的第 i 位上存在 1 的时候 ++f[n-i]
字符串b的第 i 位上存在 1 的时候 --f[n-i]
再用来模拟从高位到低位进位 即 f[i]=f[i+1]+f[i+2];
题目中的说法是 ∑ni=0(ai∗qn−i) 我程序中 f[i] = s[i] - '0' ;相当于把字符串倒叙映射
因此 从高到低位 是 从 max( Len1, Len2)--> i==3
全部转移到 f[1] 和 f[0] 上 再来判断大小
这样就可以过了么 too young !! 会爆long long 的！！
事实上 我们从高位向低位转移的的时候 当某一位上的绝对值大于 2 的时候 就已经比较出大小了
所以要在转移过程中判断大小
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #define max(a,b) a<b?b:a 5 6 const int MAXN=100010; 7 8 int Len1,Len2; 9 10 char s[MAXN],v[MAXN]; 11 12 int f[MAXN]; 13 14 int hh() { 15 scanf("%s%s",s+1,v+1); 16 17 double q=(sqrt(5)+1)/2; 18 Len1=strlen(s+1);Len2=strlen(v+1); 19 for(int i=1; i<=Len1; ++i) f[Len1-i]=s[i]-'0'; 20 for(int i=1; i<=Len2; ++i) f[Len2-i]+='0'-v[i]; 21 22 for(int i=max(Len1,Len2); i>=3; --i) { 23 if(f[i]<-1) {printf("< "); return 0;} 24 if(f[i]>1) {printf("> "); return 0;} 25 f[i-1]+=f[i]; 26 f[i-2]+=f[i]; 27 } 28 f[1]+=f[2];f[0]+=f[2]; 29 if(f[1]==0 && f[0]==0) printf("= "); 30 else { 31 double Ans=f[1]*1.0*q+f[0]; 32 if(Ans>0) printf(">"); 33 else printf("< "); 34 } 35 36 return 0; 37 } 38 39 int sb=hh(); 40 int main(int argc,char**argv) {;}