2016中国大学生程序设计竞赛（长春） Ugly Problem 模拟+大数减法

时间：2023-03-10 01:37:39
2016中国大学生程序设计竞赛（长春） Ugly Problem 模拟+大数减法

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5920

2016中国大学生程序设计竞赛（长春） Ugly Problem 模拟+大数减法

我们的思路是：

  1. 对于一个串s，先根据s串前一半复制到后一半构成一个回文串，
  2. 如果这个回文串比s小，则做减法并递归；
  3. 如果相等直接结束；
  4. 如果大，那么找前一半离中心最近的一个非零数减1，并把这位之后到中心的数全都变为9，例如11000->11011，大了，所以变成10901；

ps：因为大数相减要传指针参数，调了蛮久，发现指针的乱指了，所以开了一个二维数组，每一次算出的原串和回文串都用新的指针，也就是s[tot],ss[tot],temp[tot];

/**************************************************************

    Problem:

    User: youmi

    Language: C++

    Result: Accepted

    Time:

    Memory:

****************************************************************/

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#include <cmath>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#define zeros(a) memset(a,0,sizeof(a))

#define ones(a) memset(a,-1,sizeof(a))

#define sc(a) scanf("%d",&a)

#define sc2(a,b) scanf("%d%d",&a,&b)

#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define scs(a) scanf("%s",a)

#define sclld(a) scanf("%I64d",&a)

#define pt(a) printf("%d\n",a)

#define ptlld(a) printf("%I64d\n",a)

#define rep(i,from,to) for(int i=from;i<=to;i++)

#define irep(i,to,from) for(int i=to;i>=from;i--)

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

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

#define lson (step<<1)

#define rson (lson+1)

#define eps 1e-6

#define oo 0x3fffffff

#define TEST cout<<"*************************"<<endl

const double pi=*atan(1.0);

using namespace std;

typedef long long ll;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

ll Pow(ll base, ll n, ll mo)

{

    ll res=;

    while(n)

    {

        if(n&)

            res=res*base%mo;

        n>>=;

        base=base*base%mo;

    }

    return res;

}

//***************************

int n;

const int maxn=+;

const ll mod=;

char ans[][maxn];

int tot=;

int Minus(char *source1, char *source2, char *result)//返回:1（s1>s2）,-1(s1<s2),0(s1=s2)

{

    int length1 = strlen(source1); // 被减数的长度

    int length2 = strlen(source2); // 减数的长度

    int i, j, k = ;

    int temp; // 临时存放位相减的结果

    int bit = ; // 借位，1表示需要借位，0表示不需要借位

    char ch; // 用于交换

    for (i = length1 - , j = length2 - ; i >=  && j >= ; --i, --j)

    {

        // 计算两个位之间的差值，同时要考虑借位

        temp = (source1[i] - '') - (source2[j] - '') - bit;

        if (temp < ) // 需要借位

        {

            bit = ;

            result[k++] = temp +  + '';

        }

        else// 不需要借位

        {

            bit = ;

            result[k++] = temp + '';

        }

    }

    while (i >= ) // length1 > length2的情况，结果为正数，将剩余数据赋值给计算结果数组

    {

        temp = source1[i--] - '' - bit;

        if (temp < ) // 需要借位

        {

            bit = ;

            result[k++] = temp +  + '';

        }

        else

        {

            bit = ;

            result[k++] = temp + '';

        }

    }

    while (j >= )// length1 < length2的情况，结果为负数，将剩余数据赋值给计算结果数组

    {

        temp =  - bit - (source2[j--] - '');

        result[k++] = temp + '';

    }

    // 对仍有进位的情况考虑，主要分两种：一种是strlen(p1)<strlen(p2),另一种是p1-p2<0，这两种情况bit为1

    if (bit == )

    {

        // 最低位肯定不会被借位，所以不需要减去借位

        // 只会向高位借位

        result[] =  - (result[] - '') + '';

        for (i = ; i < k; i++)

        {

            result[i] =  - (result[i] - '') - bit + '';

        }

    }

    for (i = k - , j = ; i >= j; --i, ++j)

    {

        ch = result[i];

        result[i] = result[j];

        result[j] = ch;

    }

    result[k] = '\0';

    while(result[]==''&&strlen(result)>)//去掉前导零

        strcpy(result,result+);

    if(length1<length2)

        return -;

    else if(length1>length2)

        return ;

    else

    {

        for(int i=;i<length1;i++)

        {

            if(source1[i]>source2[i])

                return ;

            else if (source1[i]<source2[i])

                return -;

        }

    }

    return ;

}

char ss[][maxn],temp[][maxn];

char s[][maxn];

void dfs()

{

    int len=strlen(s[tot]);

    if(len==)

    {

        strcpy(ans[tot],s[tot]);

        tot++;

        return;

    }

    int half=len/;

    int pre=-;

    int num=-len%;

    if(len%==)

    {

        for(int i=;i<half;i++)

        {

            if(s[tot][i]!='')

                pre=max(pre,i);

            ss[tot][i]=s[tot][i];

        }

        for(int i=half;i<len;i++)

            ss[tot][i]=ss[tot][*half-i-];

    }

    else

    {

        for(int i=;i<=half;i++)

        {

            if(s[tot][i]!='')

                pre=max(pre,i);

            ss[tot][i]=s[tot][i];

        }

        for(int i=half+;i<len;i++)

            ss[tot][i]=ss[tot][*half-i];

    }

    ss[tot][len]='\0';

    s[tot][len]='\0';

    int flag=Minus(s[tot],ss[tot],temp[tot]);

    if(flag==-)

    {

        if(s[tot][pre]==''&&pre==)

        {

            for(int i=;i<len-;i++)

                ss[tot][i]='';

            ss[tot][len-]='\0';

        }

        else

        {

            ss[tot][pre]=s[tot][pre]-;

            ss[tot][*half-pre-num]=s[tot][pre]-;

            for(int i=pre+;i<*half-pre-num;i++)

                ss[tot][i]='';

        }

        Minus(s[tot],ss[tot],temp[tot]);

        strcpy(ans[tot],ss[tot]);

        strcpy(s[tot+],temp[tot]);

        tot++;

        dfs();

    }

    else if(flag==)

    {

        strcpy(ans[tot],ss[tot]);

        tot++;

        return;

    }

    else

    {

        strcpy(ans[tot],ss[tot]);

        strcpy(s[tot+],temp[tot]);

        tot++;

        dfs();

    }

}

int main()

{

    int kase=;

    sc(n);

    while(n--)

    {

        printf("Case #%d:\n",++kase);

        tot=;

        scs(s[tot]);

        while(s[tot][]==''&&strlen(s[tot])>)//去掉前导零

            strcpy(s[tot],s[tot]+);

        dfs();

        pt(tot);

        rep(i,,tot-)

        puts(ans[i]);

    }

    return ;

}

相关文章