首页 > 代码库 > HDU 4814 Golden Radio Base 模拟
HDU 4814 Golden Radio Base 模拟
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4814
题目大意:
把一个正整数表示为φ进制, φ = (1+√5)/2 。
且已知:
1. φ + 1 = φ 2 ,所以有11(φ) = 100(φ),且要求11要转变为100
2. 2 *φ 2 = φ3 + 1 。
解题思路:
观察发现,2 = 10.01。所以对于一个数N,能够从N/2 推导得到,是一个模拟的过程。我比赛的时候居然用了高速幂。。。
代码:
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<deque> #include<list> #include<set> #include<map> #include<stack> #include<queue> #include<numeric> #include<iomanip> #include<bitset> #include<sstream> #include<fstream> #define debug puts("-----") #define pi (acos(-1.0)) #define eps (1e-8) #define inf (1<<30) #define LL long long using namespace std; int str[400]; int tmp[400]; int n; void out() { int st, ed; for (int i = 0; i < 400; i++) if (str[i]) { st = i; break; } for (int i = 399; i >= 0; i--) if (str[i]) { ed = i; break; } for (int i = st; i <= 200; i++) printf("%d", str[i]); if (ed > 200) { printf("."); for (int i = 201; i <= ed; i++) printf("%d", str[i]); } puts(""); } void gao(int str[], int tmp[]) { for (int i = 0; i < 400; i++) str[i] += tmp[i]; int k = 0; while(k < 400) { if (str[k] >= 2) { str[k - 1] += 1; str[k] -= 2; str[k + 2] += 1; k--; } else if (k > 0 && str[k] == 1 && str[k - 1] == 1) { str[k] = 0; str[k - 1] = 0; str[k - 2] += 1; k -= 2; } else k++; } } void fi_pow(int k) { memset(tmp, 0, sizeof(tmp)); memset(str, 0, sizeof(str)); tmp[200] = 1; while(k) { if (k & 1) { gao(str, tmp); //out(); } k >>= 1; gao(tmp, tmp); } } int main () { while(~scanf("%d", &n)) { if (n == 1) { puts("1"); continue; } fi_pow(n); out(); } return 0; }
HDU 4814 Golden Radio Base 模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。