test

原始文件为 cpp 代码，本文是转换后的 Markdown 文件。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <cstring>
#include <algorithm>

using namespace std;

class Bigint
{
    private:
        vector<int> number;
        bool positive;
        int base;
        unsigned int skip;
        static const int default_base=1000000000;

    public:
        //Constructors
        Bigint();
        Bigint(long long);
        Bigint(string);
        Bigint(const Bigint& b);

        //Adding
        Bigint operator+(Bigint const &) const;
        Bigint &operator+=(Bigint const &);
        Bigint operator+(long long const &) const;
        Bigint &operator+=(long long);

        //Subtraction
        Bigint operator-(Bigint const &) const;
        Bigint &operator-=(Bigint const &);

        //Allocation
        Bigint operator=(const long long &);
        Bigint operator=(string &);

        //Access
        int operator[](int const &);

        //Input&Output
        friend istream &operator>>(istream &, Bigint &);
        friend ostream &operator<<(ostream &, Bigint const &);

        //Helpers
        void clear();
        Bigint &abs();

        //Trivia
        int digits() const;
    private:
        int segment_length(int) const;
        Bigint pow(int const &, map<int, Bigint> &);
        int compare(Bigint const &) const; //0 a == b, -1 a < b, 1 a > b
};

Bigint abs(Bigint);
string to_string(Bigint const &);

//Constructor
Bigint::Bigint()
{
    positive = true;
    base = Bigint::default_base;
    skip = 0;
}
Bigint::Bigint(const Bigint &b)
    : number(b.number),
    positive(b.positive),
    base(b.base),
    skip(b.skip) { }
Bigint::Bigint(long long value)
{
    base = Bigint::default_base;
    skip = 0;
    if (value < 0) {
        positive = false;
        value *= -1;
    } else {
        positive = true;
    }

    while (value) {
        number.push_back((int) (value % base));
        value /= base;
    }
}

Bigint::Bigint(string stringInteger)
{
    int size = stringInteger.length();

    base = Bigint::default_base;
    skip = 0;
    positive = (stringInteger[0] != '-');

    while (true) {
        if (size <= 0) break;
        if (!positive && size <= 1) break;

        int length = 0;
        int num = 0;
        int prefix = 1;
        for (int i(size - 1); i >= 0 && i >= size - 9; --i) {
            if (stringInteger[i] < '0' || stringInteger[i] > '9') break;
            num += (stringInteger[i] - '0') * prefix;
            prefix *= 10;
            ++length;
        }
        number.push_back(num);
        size -= length;
    }
}

//Adding
Bigint Bigint::operator+(Bigint const &b) const
{
    Bigint c = *this;
    c += b;

    return c;
}

Bigint &Bigint::operator+=(Bigint const &b)
{
    if (!b.positive) {
        return *this -= b;
    }
    auto it1 = number.begin();
    auto it2 = b.number.begin();
    int sum = 0;
    while (it1 != number.end() || it2 != b.number.end()) {
        if (it1 != number.end()) {
            sum += *it1;
        } else {
            number.push_back(0);
            it1 = number.end()-1;
        }
        if (it2 != b.number.end()) {
            sum += *it2;
            ++it2;
        }
        *it1 = sum % base;
        ++it1;
        sum /= base;
    }
    if (sum) number.push_back(1);

    return *this;
}

Bigint Bigint::operator+(long long const &b) const
{
    Bigint c = *this;
    c += b;

    return c;
}

Bigint &Bigint::operator+=(long long b)
{
    vector<int>::iterator it = number.begin();
    if (skip > number.size()) {
        number.insert(number.end(), skip - number.size(), 0);
    }
    it += skip;
    bool initial_flag=true;
    while (b || initial_flag) {
        initial_flag=false;
        if (it != number.end()) {
            *it += b % base;
            b /= base;
            b += *it / base;
            *it %= base;
            ++it;
        } else {
            number.push_back(0);
            it = number.end() - 1;
        }
    }

    return *this;
}

//Subtraction
Bigint Bigint::operator-(Bigint const &b) const
{
    Bigint c = *this;
    c -= b;

    return c;
}

Bigint &Bigint::operator-=(Bigint const &b)
{
    vector<int>::iterator
        it1 = number.begin();
    vector<int>::const_iterator
        it2 = b.number.begin();
    int dif = 0;
    while (it1 != number.end() || it2 != b.number.end()) {
        if (it1 != number.end()) {
            dif += *it1;
            ++it1;
        }
        if (it2 != b.number.end()) {
            dif -= *it2;
            ++it2;
        }
        if (dif < 0) {
            *(it1 - 1) = dif + base;
            dif = -1;
        } else {
            *(it1 - 1) = dif % base;
            dif /= base;
        }
    }
    if (dif < 0) positive = false;

    if (number.size() > 1)
    {
        do
        {
            it1 = number.end() - 1;
            if (*it1 == 0) number.pop_back();
            else break;
        } while (number.size() > 1);
    }

    return *this;
}

//Allocation
Bigint Bigint::operator=(const long long &a)
{
    number.clear();
    long long t = a;
    do {
        number.push_back((int) (t % base));
        t /= base;
    } while (t != 0);

    return *this;
}

Bigint Bigint::operator=(string& stringInteger)
{
    int size = stringInteger.length();

    base = Bigint::default_base;
    skip = 0;
    positive = (stringInteger[0] != '-');

    while (true) {
        if (size <= 0) break;
        if (!positive && size <= 1) break;

        int length = 0;
        int num = 0;
        int prefix = 1;
        for (int i(size - 1); i >= 0 && i >= size - 9; --i) {
            if (stringInteger[i] < '0' || stringInteger[i] > '9') break;
            num += (stringInteger[i] - '0') * prefix;
            prefix *= 10;
            ++length;
        }
        number.push_back(num);
        size -= length;
    }
    return *this;
}

//Access
int Bigint::operator[](int const &b)
{
    return to_string(*this)[b] - '0';
}

//Trivia
int Bigint::digits() const
{
    int segments = number.size();

    if (segments == 0) return 0;

    int digits = 9 * (segments - 1);
    digits += segment_length(number.back());

    return digits;
}

//Helpers
void Bigint::clear()
{
    number.clear();
    positive = true;
    skip = 0;
}

Bigint &Bigint::abs()
{
    positive = true;

    return *this;
}

//Input&Output
ostream &operator<<(ostream &out, Bigint const &a)
{
    if (!a.number.size()) return out << 0;
    int i = a.number.size() - 1;
    for (; i>=0 && a.number[i] == 0; --i);

    if (i == -1) return out << 0;
    if (!a.positive) out << '-';

    vector<int>::const_reverse_iterator it = a.number.rbegin() + (a.number.size() - i - 1);

    out << *it++;
    for (; it != a.number.rend(); ++it) {
        for (int i(0), len = a.segment_length(*it); i < 9 - len; ++i) out << '0';
        if (*it) out << *it;
    }

    return out;
}

istream &operator>>(istream &in, Bigint &a)
{
    string str;
    in >> str;

    a = str;

    return in;
}

int Bigint::segment_length(int segment) const
{
    int length = 0;
    while (segment) {
        segment /= 10;
        ++length;
    }

    return length;
}

Bigint abs(Bigint value)
{
    return value.abs();
}

string to_string(Bigint const &value)
{
    ostringstream stream;
    stream << value;

    return stream.str();
}

struct Node
{
    Node* child[10];
    bool have_value;
    int value;

    Node() { have_value = false;  for(int i = 0; i < 10; ++i) child[i] = NULL; }
    void setvalue(int index) { value = index; have_value = true; }
};

Node* root;

const int maxn = 100005;
int tree[40][10];

void init();
void build(string str, int index);
int query(string str);

int main()
{
    // freopen("in.txt", "r", stdin);
    init();

    Bigint a = 0, b = 1;
    for(int i = 0; i < 100000; ++i)
    {
        build(to_string(b), i);
        Bigint tmp = b;
        // b = a + b;
        if(to_string(tmp).size() > 50)
        {
            b = to_string(a + b).substr(0, 50);
            a = to_string(tmp).substr(0,50);
        }else
        {
            b = to_string(a + b).substr(0, 51);
            a = tmp;
        }
    }

    int T; cin >> T;
    for(int i = 1; i <= T; ++i)
    {
        string str; cin >> str;
        printf("Case #%d: %d\n", i, query(str));
    }
}

void init()
{
    root = new Node();
}

void build(string str, int index)
{
    Node* cur_node = root;
    for(int i = 0; i < str.length(); ++i)
    {
        int num = str[i] - '0';
        if(!cur_node->child[num])
        {
            cur_node->child[num] = new Node();
            cur_node->child[num]->setvalue(index);
        }
        cur_node = cur_node->child[num];
    }
}

int query(string str)
{
    Node* cur_node = root;
    for(int i = 0; i < str.length(); ++i)
    {
        int num = str[i] - '0';
        if(!cur_node->child[num])
        {
            return -1;
        }
        cur_node = cur_node->child[num];
    }
    return cur_node->value;
}