Menu
Article ACM

HDU 4405 Aeroplane chess

NodeKey

NodeKey

• 2 min read

昨天周赛的水搜索 然而………………

因为昨晚基地灯坏了，只能跟寝室里的煞笔一起打（当然他比我强，他10分钟A了 我越写越急

最后写了两个小时………………

不想多说什么了 先贴上源代码 再分析优化

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
char str[20];
int flag[20];
int len, ans;

bool judge()
{
    int mid;
    for (mid = 0; mid < len; mid++)
        if (flag[mid] == 2)
            break;
    if (mid == len)
        return false;
    long long lans = str[0] - '0', rans = str[mid] - '0', i;
    for (i = 1; i < mid; i++)
        if (flag[i])
            break;
        else
            lans = lans * 10 + str[i] - '0';
    while (i < mid) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        lans += tmp;
    }
    for (i = mid + 1; i < len; i++)
        if (flag[i])
            break;
        else
            rans = rans * 10 + str[i] - '0';
    while (i < len) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        rans += tmp;
    }
    return lans == rans;
}

void dfs(int pos, bool has_equal)
{
    if (pos == len) {
        if (has_equal && judge())
            ans++;
        return;
    }
    if (has_equal) {
        flag[pos] = 1;
        dfs(pos + 1, true);
        flag[pos] = 0;
        dfs(pos + 1, true);
    } else {
        flag[pos] = 0;
        dfs(pos + 1, false);
        flag[pos] = 1;
        dfs(pos + 1, false);
        // if(pos==len-1) return;
        flag[pos] = 2;
        dfs(pos + 1, true);
    }
}

int main()
{
    while (scanf("%s", str) != EOF) {
        if (strcmp(str, "END") == 0)
            break;
        len = strlen(str), ans = 0;
        memset(flag, 0, sizeof flag);
        flag[len] = 1000;
        dfs(1, false);
        printf("%d\n", ans);
    }
    return 0;
}

我当时的思路很明显了 先用DFS放置所有 + = 的位置 到最后判断一些能不能使等式成立

因为前面想的少，搞得后面的bug处理特别多

尤其是判断那里

对于优化建议

1.完全可以预处理一下 比如定义一个二维数组 num[27][27] 用num[x][y]表示 x-y 的数字 然后只要判断加号位置就好了

2.另外的话可以以一个循环判断=的位置 再对左右按序DFS 即可

好吧 我已经理论优化了

最后想说的是 打ACM 心态很重要 心态爆炸了 这场基本也是完了

Share