首页 > ACM题库 > HDU-杭电 > Hdu 1909 ‘JBC’-复杂模拟[解题报告] C++
2013
12-23

Hdu 1909 ‘JBC’-复杂模拟[解题报告] C++

‘JBC’

问题描述 :

Life can be taught, but sometimes simple problems are just very well hidden among difficult ones. Once identifying those simple problems you are almost on a half way of solving them as well as making one big step towards winning the contest. Just be careful, this is NOT the simplest problem!Are you ready for that challenge?

Your task is to write a program that transforms numbers from various numeric systems to decade one (base=10).

输入:

Input file consists from multiple data sets separated by one or more empty lines.First line of each set contains definition of digit ordering for some hypothetical numerical system. All ASCII printable characters (codes greater than 0×20 (space)) are allowed to appear as digits, and they are sorted according to increased decimal value (starting from zero).

Each line of the input data set (starting from second one) is one number coded with previously defined digits. Such numbers can have multiple decade interpretations (taking different base for hypothetical system) and your task is to find sum of all possible interpretations.

Explanation: If we define digit ordering as “0123456789” possible bases are 2..10 but number “6201” can be decoded only in systems with base 7..10.

Input lines can contain white space characters on both ends which should be ignored.

输出:

You are required to output one decimal number per each number from input data sets. That number represents sum of decimal representations for all valid numeric system bases.Output data sets should be separated by one blank line.

样例输入:

0123456789
 90763
1

.1>C
CC.
>.1
1....

样例输出:

90763
9

60
52
353


这是一道比较复杂的模拟题,注意:

1、要用大数来做

2、去除串的前导和后导空格

3、要求的串中可能存在原来的串没有的符号,这些符号要省略

4、貌似最后一个case没有换行,若果用fgets(),可能会出错,但用gets()和getline()没有问题

程序代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <limits>
#include <algorithm>
using namespace std;
const int maxn = 20000;
struct bign{
    int len, s[maxn];
    bign(){memset(s, 0, sizeof(s)); len = 1;}
    bign(int num){*this = num;}
    bign(char *num){*this = num;}
    bign operator = (const char* num){
        len = strlen(num);
        for(int i = 0; i < len; i++)
            s[i] = num[len - i - 1] - '0';//反转
        return *this;
    }
    bign operator = (const int num){
        char s[maxn];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    string str() const {
        string res = "";
        for(int i = 0; i < len; i++)
            res = (char)(s[i] + '0') + res;
        if(res == "")
            res = "0";
        return res;
    }
    bign operator + (const bign & b) const {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++){// g 只判断最后是否进位
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    bign operator += (const bign & b) {
        *this = *this + b;
        return *this;
    }
    void clean(){
        while(len > 1 && !s[len - 1])   len--;
    }
    bign operator - (const bign & b){
        bign c; c.len = 0;
        for(int i = 0, g = 0; i < len; i++){
            int x = s[i] - g;
            if(i < b.len)   x -= b.s[i];
            if(x >= 0)  g = 0;
            else {g = 1; x += 10;}
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    bign operator -= (const bign & b){
        *this = *this - b;
        return *this;
    }
    bign operator * (const bign &b){
        bign c;
        c.len = len + b.len;
        for(int i = 0; i < len; i++)
            for(int j = 0; j < b.len; j++)
                c.s[i + j] += s[i] * b.s[j];
        for(int i = 0; i < c.len - 1; i++){
            c.s[i + 1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    void digit_shift(bign & n, int d) {
        int i;
        if(n == 0)
            return;
        for(i = n.len - 1; i >= 0; i--)
            n.s[i + d] = n.s[i];
        for(i = 0; i < d; i++)
            n.s[i] = 0;
        n.len = n.len + d;
    }
    bign operator / (const bign& b){
        bign row;
        bign c;
        c.len = len;
        int i, j;
        for(i = len - 1; i >= 0; i--){
            digit_shift(row, 1);
            row += s[i];
            c.s[i] = 0;
            while(row >= b){
                c.s[i]++;
                row -= b;
            }
        }
        c.clean();
        return c;
    }
    bool operator < (const bign & b) const{
        if(len != b.len)    return len < b.len;
        for(int i = len - 1;i >= 0; i--)
            if(s[i] != b.s[i])  return s[i] < b.s[i];
        return false;
    }
    bool operator > (const bign & b) const { return b < *this;}
    bool operator <= (const bign & b) const {return !(b < *this);}
    bool operator >= (const bign & b) const {return !(*this < b);}
    bool operator != (const bign & b) const {return b < *this || *this < b;}
    bool operator == (const bign & b) const {return !(b < *this) && !(*this < b);}
};
istream & operator >> (istream & in, bign & x){
    string s;
    in>>s;
    x = s.c_str();
    return in;
}
ostream & operator << (ostream & out, const bign & x){
    out<<x.str();
    return out;
}
map<char, int> mp;
string input;
int main()
{
    bool flag = false;
    int k = 0, len, begin;
    bign num, sum, mod;
    //freopen("input.txt", "r", stdin);
    while(true){
        flag = false;
        while(getline(cin, input)){
            if(input.size() == 0 && flag) break;
            else if(input.size() == 0 && !flag) continue;
            else {
                while(input[0] == ' ') input.erase(input.begin());
                while(input[input.size() - 1] == ' ') input.erase(input.size() - 1, 1);
                if(!flag){
                    if(k) cout<<endl;
                    mp.clear();
                    k = 1;
                    flag = true;
                    len = input.size();
                    for(int i = 0; i < len; i++)
                        mp[input[i]] = i;
                }else {
                    begin = 2;
                    for(int i = 0; i < input.size(); i++)
                        if(mp.count(input[i]) && begin < mp[input[i]] + 1)
                            begin = mp[input[i]] + 1;
                    sum = 0;
                    for(; begin <= len; begin++){
                        mod = 1; num = 0;
                        for(int j = input.size() - 1; j >= 0; j--){
                            if(mp.count(input[j])){
                                num = num + mod * mp[input[j]];
                                mod =  mod * begin;
                            }
                        }
                        sum = sum + num;
                    }
                    cout << sum << endl;
                }
            }
        }
        if(!flag) break;
    }
    return 0;
}