Google Code Jam 2016 Round 1B B

题意：给出两个数字位数相同，分别中间有若干位不知道，用问号表示。现在要求补全这两个数字，使得差值的绝对值最小，多解则取第一个数字的值最小的，再多解就取第二个数字最小的。

分析：

类似数位dp，但是很多状态可以直接得出最终解，个别状态需要状态转移。

我们从高位到低位依次确定两个数的每个位是几。一旦确定了两个数的一个位不一样，则可以立即将小的一方的后续问号全部写9，大的一方后续问号全部写0。这样才能让差值最小。

那我们观察每个位的时候要如何确定其值呢？分如下几种情况。

1.两个数的该位都是问号，那么分三种情况：

　　1.1 都标为0，看下一个位。

　　1.2&1.3 将一位标为1，另一个位标为0，并更新答案，终结状态。（这表示我们主动在高位制造了一个差值以便后面取得整体差值最小。例如：？0？，？9？，答案是100,099）

2.两个数的该位都不是问号，若相等，继续看下一位。若不等，则标出后面问号，更新答案，终结状态。

3.两个数的该位有一个是问号，那么这个这与第一种情况类似，分三种情况处理。

　　3.1 标为与该位相等，看下一个位。

　　3.2 标为该位减1，赋值后续问号，更新答案，终结状态。

　　3.3 标为该位加1，赋值后续问号，更新答案，终结状态。

就这么多情况。值得注意的是，虽然有些时候进行了状态转移（看下一个位）。但是并不需要搜索和回溯。因为每个状态的多个分支中，只有一个是状态转移，其他的都是最终态。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

using namespace std;

#define d(x) 

const int MAX_LEN = ;

char st[][MAX_LEN];

char ans[][MAX_LEN];

char temp[][MAX_LEN];

long long diff;

int n;

void input()

{

    scanf("%s", st[]);

    scanf("%s", st[]);

    n = strlen(st[]);

}

long long get_value(char st[])

{

    long long ten = ;

    long long ret = ;

    for (int i = n - ; i >= ; i--)

    {

        ret += (st[i] - '') * ten;

        ten *= ;

    }

    return ret;

}

bool ok(long long temp_diff)

{

    if (temp_diff > diff)

        return false;

    if (temp_diff < diff)

        return true;

    if (strcmp(ans[], temp[]) > )

        return true;

    if (strcmp(ans[], temp[]) < )

        return false;

    return strcmp(ans[], temp[]) > ;

}

void update()

{

    long long a = get_value(temp[]);

    long long b = get_value(temp[]);

    long long temp_diff = abs(a - b);

    if (ok(temp_diff))

    {

        diff = temp_diff;

        strcpy(ans[], temp[]);

        strcpy(ans[], temp[]);

    }

}

void make(int index, int a, int b)

{

    if (a <  || b <  || a >  || b > )

        return;

    strcpy(temp[], st[]);

    strcpy(temp[], st[]); 

    temp[][index] = a + '';

    temp[][index] = b + '';

    int ch_a = '';

    int ch_b = '';

    if (a > b)

        swap(ch_a, ch_b);

    for (int i = index + ; i < n; i++)

    {

        if (temp[][i] == '?')

            temp[][i] = ch_a;

        if (temp[][i] == '?')

            temp[][i] = ch_b;

    }

    d(printf("a=%d\n", a));

    d(printf("b=%d\n", b));

    d(puts(temp[]));

    d(puts(temp[]));

    update();

}

void work()

{

    diff = 1LL << ;

    for (int i = ; st[][i]; i++)

    {

        if (st[][i] == st[][i] && st[][i] != '?')

        {

            continue;

        }

        if (st[][i] == st[][i] && st[][i] == '?')

        {

            make(i, , );

            make(i, , );

            st[][i] = st[][i] = '';

            continue;

        }

        //reach here means st[0][i] != st[1][i]

        if (st[][i] != '?' && st[][i] != '?')

        {

            make(i, st[][i] - '', st[][i] - '');

            return;

        }

        //reach here means only one of them is ?.

        if (st[][i] == '?')

        {

            make(i, st[][i] - '' + , st[][i] - '');

            make(i, st[][i] - '' - , st[][i] - '');

            st[][i] = st[][i];

        }

        if (st[][i] == '?')

        {

            make(i, st[][i] - '', st[][i] - '' + );

            make(i, st[][i] - '', st[][i] - '' - );

            st[][i] = st[][i];

        }

    }

    make(n - , st[][n - ] - '', st[][n - ] - '');

}

int main()

{

    int t;

    scanf("%d", &t);

    int case_num = ;

    while (t--)

    {

        case_num++;

        printf("Case #%d: ", case_num);

        input();

        work();

        printf("%s %s\n", ans[], ans[]);

    }

    return ;

}

巴特西

Google Code Jam 2016 Round 1B B

最新文章

热门文章