【UVA-1588】Kickdown【紫书】

【UVA-1588】Kickdown【紫书】

问题链接:https://vjudge.net/problem/UVA-1588

udebug链接:https://www.udebug.com/UVa/1588

Solution:

思路是:首先将两个字符串读进来,然后将ascii字符转化为数字,接着枚举拼接方案(因为字符串长度最大是100,暴力枚举预估不会超时),遇到拼接失败(相同两个位置上相加大于3)直接放弃当前拼接方案,开始枚举下一个方案。

本题有两个坑:1)图片和样例具有诱导性,两个字符串不一定是第一个比第二个长。【我们可以判断一下,如过第一个比第二个短就交换一下】2)短的那个可以拼在左边,不一定是右边,下面三种拼接方案都是可以的。

 

 

#include <iostream>
#include <cstring>
// #define DBG

using namespace std;

const int OFFSET = 100;
const int LIM = OFFSET * 3;
char top[LIM], bottom[LIM], buff[LIM];

inline int maxi(int a, int b) { return a > b ? a : b; }
inline int mini(int a, int b) { return a < b ? a : b; }

inline void swap(int &bottomlen, int &toplen) {
    if (toplen > bottomlen) {
        int tmp = bottomlen;
        bottomlen = toplen;
        toplen = tmp;
        strcpy(buff, top + OFFSET);
        strcpy(top + OFFSET, bottom + OFFSET);
        strcpy(bottom + OFFSET, buff);
    }
}

int main(void) {
    while (~scanf("%s%s", bottom + OFFSET, top + OFFSET)) {
        int i, j, k, ans, toplen = strlen(top + OFFSET), bottomlen = strlen(bottom + OFFSET);
        swap(bottomlen, toplen);
        for (i = OFFSET; top[i]; i++) top[i] -= '0';
        for (j = OFFSET; bottom[j]; j++) bottom[j] -= '0';
        for (i = OFFSET, j = OFFSET, k = 0; k <= bottomlen; i = j = OFFSET, k++) {
#ifdef DBG
            cout << "Try: " << k << endl;
#endif
            for (; top[i] && top[i] + bottom[j + k] <= 3; i++, j++);
            if (!top[i]) break;
        }
        ans = maxi(k + toplen, bottomlen);
        for (i = OFFSET, j = OFFSET, k = -1; k <= toplen; i = j = OFFSET, k--) {
#ifdef DBG
            cout << "Try: " << k << endl;
#endif
            for (; top[i] && top[i] + bottom[j + k] <= 3; i++, j++);
            if (!top[i]) break;
        }
        ans = mini(ans, bottomlen - k);
        printf("%d\n", ans);
        memset(top, 0, sizeof top);
        memset(bottom, 0, sizeof bottom);
    }
    return 0;
}