UVa-12333：Revenge of Fibonacci 高精度

之前自己仿照紫書上寫了高精度庫，完善了乘法、減法，并且通過了和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，就要保存前綴1，12，123。

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_map>class BigInt {
public:using ll = long long;static constexpr int BASE = 1e8;    //基數是1e8，即滿1e8才進一位static constexpr int WIDTH = 8;     //每一位的十進制長度是8位，主要用于字符串和轉換std::vector<int> bit;               //保存BigInt的每一位，小端模式：低位低字節，高位高字節bool negative;                      //記錄數字是否是負數static void trim(std::string &s);                           //trim函數：刪除頭部和尾部的空格static void num2big(std::vector<int> &bit, ll num);         //實際處理函數：將正數num放入bit數組中static void str2big(std::vector<int> &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::vector<int> &bit, ll num) {ll x;//必須使用do while，循環至少應該執行一遍，處理num是0的情況do {x = num % BASE;bit.push_back(static_cast<int>(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::vector<int> &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::vector<ll> 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_cast<ll>(bit[i]) * static_cast<ll>(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_cast<int>(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;
vector<BigInt> fib;
unordered_map<string, 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";}}
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383528.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383528.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383528.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

vim命令筆記

vim命令筆記

vim折疊函數&#xff1a;https://www.cnblogs.com/zlcxbb/p/6442092.html Vim錄制宏及使用&#xff1a;https://www.jianshu.com/p/9d999c72a9f3 將vim與系統剪貼板的交互使用&#xff1a;https://zhuanlan.zhihu.com/p/73984381
閱讀更多...
Educational Codeforces Round 114總結

Educational Codeforces Round 114總結

緒論 https://codeforces.com/contest/1574/ 以前想要打CF&#xff0c;總是覺得沒有時間&#xff0c;要做這個&#xff0c;要做那個&#xff0c;現在時間充裕了一些&#xff0c;想要多打一些CF&#xff0c;但是光打比賽不總結是沒有什么幫助的&#xff0c;這是我從以前的ACM訓…
閱讀更多...
UVA - 210：Concurrency Simulator

UVA - 210：Concurrency Simulator

題目鏈接&#xff1a;https://vjudge.net/problem/UVA-210 題目分析 就是一道模擬題&#xff0c;但是細節有點多。 寫代碼兩個小時&#xff0c;調試代碼用了兩天。。。很長時間不刷題了&#xff0c;這道雖然算法簡單但是細節滿滿的題目對我來說是一個很好的熱身。 盡量不要去…
閱讀更多...
UVA - 514：Rails

UVA - 514：Rails

題目鏈接&#xff1a;https://vjudge.net/problem/UVA-514 題目分析 題目的意思是給一個棧輸入一系列數據&#xff0c;在這個過程中可以出棧&#xff0c;看能否達到某個結果。 剛開始我覺得這個情況好多&#xff0c;因此不是用模擬&#xff0c;而應該觀察結果本身。對于結果中…
閱讀更多...
UVA - 442：Matrix Chain Multiplication

UVA - 442：Matrix Chain Multiplication

題目鏈接&#xff1a;https://vjudge.net/problem/UVA-442 題目分析 題目的意思非常簡單&#xff0c;就是給定一個矩陣乘法的表達式然后計算就可以了。隨便寫寫 AC代碼 #include <iostream> #include <deque> #include <vector> #include <string>…
閱讀更多...
leetcode869. 重新排序得到 2 的冪

leetcode869. 重新排序得到 2 的冪

題目連接&#xff1a;https://leetcode-cn.com/problems/reordered-power-of-2/ 題目分析 如果直接順著題目的思路&#xff0c;得到數字n的全排列&#xff0c;然后再去判斷其是不是2的冪是比較復雜的。 我們應該注意到&#xff0c;因為數字是可以隨意排列的&#xff0c;因此所…
閱讀更多...
使用wireshark+ssh+tcpdump遠程抓包

使用wireshark+ssh+tcpdump遠程抓包

因為需要抓取遠程服務器上的數據包&#xff0c;又不想使用tcpdump這種命令行工具進行&#xff08;用了wireshark后誰還愿意去看密密麻麻的命令行呢&#xff09;&#xff0c;所以在網上查找了一下使用wireshark遠程抓包的方法&#xff0c;在這里記錄一下。 原生支持 wireshark…
閱讀更多...
C++ Variadic Templates（可變參數模板）

C++ Variadic Templates（可變參數模板）

本文參考侯捷老師的視頻&#xff1a;https://www.youtube.com/watch?vTJIb9TGfDIw&listPL-X74YXt4LVYo_bk-jHMV5T3LHRYRbZoH 以及C primer第五版 相關內容。 可變參數模板函數 //遞歸的終止條件 void print() {} //Variadic Templates //一般用于遞歸處理 template <…
閱讀更多...
Ubuntu修復Fix Busybox Initramfs錯誤

Ubuntu修復Fix Busybox Initramfs錯誤

今天早上我打開電腦&#xff0c;進入Ubuntu系統&#xff0c;結果黑屏了&#xff0c;屏幕顯示&#xff1a; BusyBox v1.30.1 (Ubuntu 1:1.30.1-4ubuntu6.1) built-in shell (ash) Enter help for a list of built-in commands.(initramfs)然而我并不知道這個是什么意思&#x…
閱讀更多...
Leetcode第284場周賽

Leetcode第284場周賽

緒論 最近發現Leetcode每周的周賽難度挺適合我的&#xff0c;而且時間也比較友好&#xff08;不像Codeforces每次都是半夜&#xff09;。所以連續參加了三周的周賽。這次才想起來應該記錄一下自己的參賽歷程。一方面是總結經驗&#xff0c;另一方面有了記錄就更有動力去提升&a…
閱讀更多...
Leetcode第286場周賽

Leetcode第286場周賽

緒論 上周因為有事沒有參加周賽&#xff0c;這周沒有錯過。這次周賽拿到了人生第一個AK&#xff0c;參加大大小小的比賽這么多次&#xff0c;從來沒有AK過&#xff0c;淚目了。 感覺這次比賽的思維難度對我來講稍高一些&#xff0c;前三道題就花了一個小時&#xff0c;而以往…
閱讀更多...
第287場周賽

第287場周賽

緒論 雖然是上周日參加的比賽&#xff0c;但是這周沒有怎么學習&#xff0c;每天就是玩耍。也導致對周賽的總結遲遲沒有進行。想著再拖下去下次周賽都要開始了&#xff0c;在這里補一下。 這場比賽總體比上場簡單一些&#xff0c;但是最后一道題因為忘記初始化類內變量導致調試…
閱讀更多...
第288場周賽

第288場周賽

緒論 雖然沒有AK&#xff0c;但是不知道為什么排名比以前AK了都靠前。可能是因為最后一道題有些難度&#xff0c;縮小了我和大佬之間的差距。最后一個小時寫最后一道題&#xff0c;累死累活想了一個貪心遍歷的算法&#xff0c;當時是一直RE&#xff0c;后來下來調了調又WA了。 …
閱讀更多...
Clion遠程部署和運行

Clion遠程部署和運行

緒論 作為Clion的忠實粉絲&#xff0c;現在的我的幾乎所有的coding都是通過Clion完成。因為需要在服務器上進行開發&#xff0c;又離不開Clion&#xff0c;就了解了如何通過Clion遠程部署和開發。 主要是借鑒了博客&#xff1a;使用Clion優雅的完全遠程自動同步和遠程調試c。如…
閱讀更多...
C++ 單例模式 call_once : terminate called after throwing an instance of ‘std::system_error‘

C++ 單例模式 call_once : terminate called after throwing an instance of ‘std::system_error‘

在學習了C中可以使用call_once進行初始化資源后&#xff0c;我就想著寫一個單例模板供以后使用。 template<typename T> class SingleTon {using Ptr std::shared_ptr<T>;static Ptr p;static std::once_flag flag;template<typename ...Args>static void …
閱讀更多...
C++讀寫鎖造成死鎖

C++讀寫鎖造成死鎖

C14支持std::shared_timed_mutex C17支持std::shared_mutex 前者相比后者支持的操作更多&#xff0c;但是后者相對性能更好。 使用std::lock_guard<std::shared_mutex>和std::unique_lock<std::shared_mutex>互斥訪問使用std::shared_lock<std::shared_mutex…
閱讀更多...
每日一題：449. 序列化和反序列化二叉搜索樹

每日一題：449. 序列化和反序列化二叉搜索樹

題目分析 題目鏈接&#xff1a;449. 序列化和反序列化二叉搜索樹 覺得序列化很簡單&#xff0c;前序遍歷、后序遍歷、中序遍歷、層序遍歷等等。其中得到前序遍歷和后序遍歷是可以通過遞歸解法反序列化的&#xff0c;覺得這樣子做有點復雜。就想著可不可以一次遍歷。一次遍歷的…
閱讀更多...
C++高效集合數據結構設計

C++高效集合數據結構設計

緒論 在復雜算法實現過程中我們經常會需要一個高效的集合數據結構&#xff0c;支持常數級別的增、刪、查&#xff0c;以及隨機返回、遍歷&#xff0c;最好還能夠支持交集、并集、子集操作 哈希集合實現 大家可能很快想到unordered_set&#xff0c;unordered_set由于底層是哈…
閱讀更多...
C++ 工具函數庫

C++ 工具函數庫

在寫一些大型項目的過程中經常需要一些工具函數&#xff0c;例如獲取隨機數、計時器、打印函數、重要常量&#xff08;如最大值&#xff09;、信號與槽等&#xff0c;由于每一個工程都自己手動實現一個實在是太傻&#xff0c;我將其總結放入一個文件中。 utils.h // Copyright…
閱讀更多...
muduo網絡庫使用入門

muduo網絡庫使用入門

muduo網絡庫介紹 muduo網絡庫是陳碩大神開發的基于主從Reactor模式的&#xff0c;事件驅動的高性能網絡庫。 網絡編程中有很多是事務性的工作&#xff0c;使用muduo網絡庫&#xff0c;用戶只需要填上關鍵的業務邏輯代碼&#xff0c;并將回調注冊到框架中&#xff0c;就可以實…
閱讀更多...
最新文章

Copyright @ 2022~2023