HDU 3925 Substring 【大数相减】

题目意思是，给你提供两个数字 a 和 b

a 可以不断的往上加，直到b 为其子串

问的是 a 最小加几？

显而易见，a 的数据范围给了10 ^100非常大，直接模拟肯定不行

那么就用 b 减去 a 来找，也算是一种模拟的方法

举个例子, a = 1299, b = 33

<1>33　　　　 330　　3300　　33000

(12)99　　　(1)299　　1299　　 1299

------　　　--------　-------- -------

34　　　　　 31　　2001　　　32001

如果当前 b 比a的部分小，在前面添1

每次比较完在b后面添0

取所有比较结果中最小的数字作为答案

当然，如果a <= b 是可以直接得到答案的 ans = b - a

但是这题用G++提交不知道为什么会WA

C++就能过

Source code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

#include <stack>

#include <string>

#include <map>

#include <queue>

#include <vector>

#include <algorithm>

#define LL long long

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

using namespace std;

string Plus(string s1,string s2)
{
if(s1.length()<s2.length())
{
string temp=s1;
s1=s2;
s2=temp;
}
int i,j;
for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
{
s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0)); //注意细节
if(s1[i]-'0'>=10)
{
s1[i]=char((s1[i]-'0')%10+'0');
if(i) s1[i-1]++;
else s1='1'+s1;
}
}
return s1;
}

string Minus(string a,string b){

    string c="",ans="",t;

    int flag = , k = ;

    bool flag2 = false;

    if(a.length() < b.length() || (a.length() == b.length()&& a.compare(b) < )){

        t = a;

        a = b;

        b = t;

        flag2 = true;

    }

    int i = a.length() - , j = b.length() - ;

    while(i >=  && j >= ){

        if(a[i] + flag > b[j]){

          c += a[i] + flag - b[j] + '';

          flag = ;

        }

        else if(a[i] + flag == b[j]){

          c += '';

          flag = ;

        }

        else{

          c += (a[i] - '') + flag +  - (b[j] - '') + '';

          flag = -;

        }

        --i;

        --j;

        ++k;

    }

    while(i >= ){

        if(a[i] + flag < ''){

            c += a[i] + flag +  + '';

            flag = -;

        }

        else{

            c += a[i] + flag;

            flag = ;

        }

        --i;

        ++k;

    }

    int len = k - ;

    while(c[len] == '' && len > ) --len;

    for(j = ; j <= len; ++j)

      ans += c[j];

    if(flag2){

        ans += '-';

    }

    char tt;

    for(i = , j = ans.length()-; i < j; ++i, --j){

        tt = ans[i];

        ans[i] = ans[j];

        ans[j] = tt;

    }

    return ans;

}

bool judge(string a, string b){

    if(a.size() < b.size()) return false;

    else if(a.size() > b.size())    return true;

    else{

        for(int i = ; i < a.size(); ++i){

            if(a[i] > b[i]) return true;

            else if(a[i] < b[i]) return false;

        }

    }

}

int main(){

    int i, j, t, n, m, numCase = ;

    string s1,s2, hh;

    string cnt, ans;

    bool flag1;

    scanf("%d",&t);

    while(t--){

        cin >> s1 >> s2;

        flag1 = false;

        int len1 = s1.size();

        int len2 = s2.size();

        if(judge(s2, s1)){

            cout << "Case #" << ++numCase << ": " << Minus(s2, s1) << endl;

            continue;

        }

        for(i = ; i < len1 - len2; ++i){

            string ww = s1.substr(i, len2);

            if(ww.compare(s2) == ){

                flag1 = true;

                break;

            }

        }

        if(flag1){

            cout << "Case #" << ++numCase << ": " << '' << endl;

            continue;

        }

        for(i = ; i < len1 - len2 + ; ++i){

            if(i == len1 - len2 + ){

                hh = s1.substr(len1 - len2 - i + , i + len2 - );

            } else{

                hh = s1.substr(len1 - len2 - i, i + len2);

            }

            if(judge(hh, s2)){

                string gg = "";

                gg += s2;

                ans = Minus(gg ,hh);

            }

            else{

                ans = Minus(s2 ,hh);

            }

            s2 += "";

            if(i == ){

                cnt = ans;

            } else{

                if(judge(cnt, ans)){

                    cnt = ans;

                }

            }

        }

        cout << "Case #" << ++numCase << ": " << cnt << endl;

    }

    return ;

}

巴特西

HDU 3925 Substring 【大数相减】

最新文章

热门文章