长春网站建设方案咨询,邢台业之峰装饰公司怎么样,专业APP客户端做网站,宁波做网站哪里专业之前自己仿照紫书上写了高精度库#xff0c;完善了乘法、减法#xff0c;并且通过了和C高精度库GMP的对拍测试#xff0c;并在一些OJ上过了一些高精度的模板题#xff0c;代码仓库地址#xff1a;https://github.com/Edward-Elric233/BigInt
求解思路
题目的意思是求前1…之前自己仿照紫书上写了高精度库完善了乘法、减法并且通过了和C高精度库GMP的对拍测试并在一些OJ上过了一些高精度的模板题代码仓库地址https://github.com/Edward-Elric233/BigInt
求解思路
题目的意思是求前100000斐波那契数列中某个前缀不超过40个字符第一次出现的位置。刚开始我的想法很简单先求出这十万个斐波那契数列的前缀然后每次读入的时候查找一遍就可以了结果超时了。每次查找的复杂度是O(1e5∗40)O(1e5 * 40)O(1e5∗40)有5e4个样例这样10s也会超时。
但是我发现这个数据结构只有查找操作因此使用unordered_map再合适不过了。我将所有前缀保存在这个unordered_map中每次查找近似都是O(1)O(1)O(1)的因此肯定不会超时。
需要注意的是这里将前缀保存的时候需要将每个数字的所有前缀都保存例如对于123就要保存前缀112123。
AC代码
// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2021/8/8
// Description:#include string
#include vector
#include iostream
#include sstream
#include algorithm
#include iomanip
#include map
#include unordered_mapclass BigInt {
public:using ll long long;static constexpr int BASE 1e8; //基数是1e8即满1e8才进一位static constexpr int WIDTH 8; //每一位的十进制长度是8位主要用于字符串和转换std::vectorint bit; //保存BigInt的每一位小端模式低位低字节高位高字节bool negative; //记录数字是否是负数static void trim(std::string s); //trim函数删除头部和尾部的空格static void num2big(std::vectorint bit, ll num); //实际处理函数将正数num放入bit数组中static void str2big(std::vectorint bit, std::string s); //实际处理函数将正数字符串放入bit数组中static bool less(const BigInt lhs, const BigInt rhs); //比较两个数字的绝对值的大小BigInt(ll num 0);BigInt(std::string s); BigInt operator (ll num); //必须返回BigInt与内置类型一致BigInt operator (std::string s);BigInt operator -() const;friend std::ostream operator (std::ostream os, const BigInt bigInt);friend std::istream operator (std::istream is, BigInt bigInt);friend BigInt operator (const BigInt lhs, const BigInt rhs);friend BigInt operator - (const BigInt lhs, const BigInt rhs);friend BigInt operator * (const BigInt lhs, const BigInt rhs);friend BigInt operator / (const BigInt lhs, const BigInt rhs);friend bool operator (const BigInt lhs, const BigInt rhs);friend bool operator (const BigInt lhs, const BigInt rhs);friend bool operator (const BigInt lhs, const BigInt rhs);friend bool operator ! (const BigInt lhs, const BigInt rhs);friend bool operator (const BigInt lhs, const BigInt rhs);friend bool operator (const BigInt lhs, const BigInt rhs);BigInt operator (const BigInt rhs);BigInt operator - (const BigInt rhs);BigInt operator * (const BigInt rhs);BigInt operator / (const BigInt rhs);std::string toString() const;BigInt setOppo(); //取相反数bool isNegative() const; //判断是否是一个负数
};std::ostream operator (std::ostream os, const BigInt bigInt);
std::istream operator (std::istream is, BigInt bigInt);
BigInt operator (const BigInt lhs, const BigInt rhs);
BigInt operator - (const BigInt lhs, const BigInt rhs);
BigInt operator * (const BigInt lhs, const BigInt rhs);
BigInt operator / (const BigInt lhs, const BigInt rhs);
bool operator (const BigInt lhs, const BigInt rhs);
bool operator (const BigInt lhs, const BigInt rhs);
bool operator (const BigInt lhs, const BigInt rhs);
bool operator ! (const BigInt lhs, const BigInt rhs);
bool operator (const BigInt lhs, const BigInt rhs);
bool operator (const BigInt lhs, const BigInt rhs);BigInt BigInt::operator-() const {BigInt ret *this;ret.negative !ret.negative;return ret;
}BigInt BigInt::setOppo() {negative !negative;return *this;
}bool BigInt::isNegative() const {return negative;
}void BigInt::num2big(std::vectorint bit, ll num) {ll x;//必须使用do while循环至少应该执行一遍处理num是0的情况do {x num % BASE;bit.push_back(static_castint(x));num / BASE;} while (num);
}BigInt::BigInt(ll num):negative(false) {if (num 0) {num -num;negative true;}num2big(this-bit, num);
}void BigInt::str2big(std::vectorint bit, std::string s) {int len (s.size() - 1) / WIDTH 1; //ceil得到lenint start, end;for (int i 0; i len; i) {end s.size() - i * WIDTH;start std::max(0, end - WIDTH);bit.push_back(std::stoi(s.substr(start, end - start)));}
}BigInt::BigInt(std::string s):negative(false) {trim(s);if (s[0] -) {negative true;s.erase(s.begin());}str2big(this-bit, s);
}void BigInt::trim(std::string s) {auto ltrim [](std::string s) {s.erase(s.begin(), std::find_if(s.begin(), s.end(), [](unsigned char c) - bool {//找到第一个非空字符return !std::isspace(c);}));};auto rtrim [](std::string s) {s.erase(std::find_if(s.rbegin(), s.rend(), [](unsigned char c) - bool {//找到最后一个非空字符return !std::isspace(c);}).base(), s.end());};ltrim(s);rtrim(s);
}BigInt BigInt::operator(ll num) {bit.clear();negative false;if (num 0) {num -num;negative true;}num2big(this-bit, num);return *this;
}BigInt BigInt::operator(std::string s) {bit.clear();negative false;trim(s);if (s[0] -) {negative true;s.erase(s.begin());}str2big(this-bit, s);return *this;
}std::ostream operator (std::ostream os, const BigInt bigInt) {if (bigInt.negative) {//输出负号os -;}auto bit bigInt.bit;//以大端字节序输出os bit.back();//除了最后一位其他的如果有前导0不能忽略os std::setfill(0);for (int i bit.size() - 2; i 0; --i) {os std::setw(BigInt::WIDTH) bit[i];}os std::setfill( );return os;
}std::istream operator (std::istream is, BigInt bigInt) {std::string s;if (is s) {//必须判断是否读入成功bigInt s;}return is;
}BigInt BigInt::operator(const BigInt rhs) {if (!negative rhs.negative) {BigInt tmp rhs;return *this (tmp - this-setOppo());} else if (negative !rhs.negative) {return *this - -rhs;}auto rbit rhs.bit;int max_len std::max(bit.size(), rbit.size());int min_len std::min(bit.size(), rbit.size());int g 0; //进位for (int i 0; i min_len; i) {bit[i] rbit[i] g;g bit[i] / BASE;bit[i] % BASE;}if (bit.size() rbit.size()) {for (int i min_len; i max_len; i) {bit.push_back(g rbit[i]);g bit.back() / BASE;bit.back() % BASE;}} else {for (int i min_len; i max_len; i) {bit[i] g;g bit[i] / BASE;bit[i] % BASE;if (!g) break;}}if (g) {//加法的进位最多为1bit.push_back(g);}return *this;
}BigInt operator (const BigInt lhs, const BigInt rhs) {BigInt ret lhs;ret rhs;return std::move(ret);
}BigInt BigInt::operator-(const BigInt rhs) {if (!negative !rhs.negative) {if (*this rhs) {} else {BigInt tmp rhs;tmp - *this;return *this tmp.setOppo();}} else if (!negative rhs.negative) {this-setOppo();*this rhs;this-setOppo();return *this;} else if (negative !rhs.negative) {return *this -rhs;} else {BigInt tmp -rhs;this-setOppo();return *this (tmp - *this);}auto rbit rhs.bit;for (int i 0; i rbit.size(); i) {if (bit[i] rbit[i]) {bit[i] BASE;bit[i 1] - 1;}bit[i] - rbit[i];}for (int i rbit.size(); i bit.size(); i) {if (bit[i] 0) {break;}bit[i] BASE;bit[i 1] - 1;}//删除前导0for (int i bit.size() - 1; i 0; --i) {if (!bit[i]) bit.pop_back();}return *this;
}BigInt operator - (const BigInt lhs, const BigInt rhs) {BigInt res lhs;res - rhs;return std::move(res);
}BigInt BigInt::operator*(const BigInt rhs) {//负负得正if (negative rhs.negative || !negative !rhs.negative) {negative false;} else {negative true;}auto rbit rhs.bit;constexpr ll LBASE BASE;std::vectorll c(bit.size() rbit.size(), 0);for (int i 0; i bit.size(); i) {for (int j 0; j rbit.size(); j) {c[i j] static_castll(bit[i]) * static_castll(rbit[j]);//在这里处理进位防止溢出if (c[i j] LBASE) {//有必要再进行除法毕竟除法比较慢c[i j 1] c[i j] / LBASE;c[i j] % LBASE;}}}//处理进位for (int i 0; i c.size(); i) {if (c[i] LBASE) {//有必要再进行除法毕竟除法比较慢c[i 1] c[i] / LBASE;c[i] % LBASE;}}//删除前导0for (int i c.size() - 1; i 0; --i) { //至少留一位if (!c[i]) c.pop_back();else break;}bit.resize(c.size());for (int i 0; i c.size(); i) {bit[i] static_castint(c[i]);}return *this;
}BigInt operator * (const BigInt lhs, const BigInt rhs) {BigInt res lhs;res * rhs;return std::move(res);
}std::string BigInt::toString() const {std::ostringstream os;os *this;return os.str();
}bool BigInt::less(const BigInt lhs, const BigInt rhs) {if (lhs.bit.size() ! rhs.bit.size()) return lhs.bit.size() rhs.bit.size();for (int i lhs.bit.size() - 1; i 0; --i) {if (lhs.bit[i] ! rhs.bit[i]) return lhs.bit[i] rhs.bit[i];}//相等return false;
}bool operator (const BigInt lhs, const BigInt rhs) {if (!lhs.negative !rhs.negative) {return BigInt::less(lhs, rhs);} else if (lhs.negative !rhs.negative) {return true;} else if (!lhs.negative rhs.negative) {return false;} else if (lhs.negative rhs.negative) {//都是负数if (BigInt::less(lhs, rhs)) {return false;} else if (BigInt::less(rhs, lhs)) {return true;} else {return false;}}
}bool operator (const BigInt lhs, const BigInt rhs) {return rhs lhs;
}bool operator (const BigInt lhs, const BigInt rhs) {return !(lhs rhs) !(rhs lhs);
}
bool operator ! (const BigInt lhs, const BigInt rhs) {return (lhs rhs) || (rhs lhs);
}bool operator (const BigInt lhs, const BigInt rhs) {return !(rhs lhs);
}bool operator (const BigInt lhs, const BigInt rhs) {return !(lhs rhs);
}using namespace std;constexpr int MAXN 1e5;
vectorBigInt fib;
unordered_mapstring, int str_hash;int main() {ios::sync_with_stdio(false);fib.push_back(1);fib.push_back(1);for (int i 2; i MAXN; i) {fib.push_back(fib[i - 1] fib[i - 2]);}for (int i 0; i MAXN; i) {string line;auto bit fib[i].bit;line.append(to_string(bit.back()));for (int i bit.size() - 2, j std::max(0, int(bit.size()) - 6); i j; --i) {const string number to_string(bit[i]);for (int i 0, j 8 - number.size(); i j; i) line.append(0);line.append(number);}
// cout line endl;for (int ii 1, jj std::min(int(line.size()), 40); ii jj; ii) {const string w line.substr(0, ii);
// cout w endl;if (str_hash.count(w)) {if (i str_hash[w]) {str_hash[w] i;}} else {str_hash[w] i;}}}
// for (int i 0; i 10; i) cout fibHead[i] ;
// cout \n;int T;cin T;string line;for (int caseI 1; caseI T; caseI) {cin line;cout Case # caseI : ;if (str_hash.count(line)) {cout str_hash[line] \n;} else {cout -1\n;}}
}
