2022中兴捧月 限时编程 第一场 24点游戏

吐槽

读完题眼前一亮，这不就是24点游戏嘛，小时候和我弟玩过。吐槽一下中兴这个网页编辑器怎么就没法输出看结果呢？我人麻了，编辑器只能给我反馈一个“未通过”，我想输出一下中间结果看一下也不行！？看了半个多小时才发现除法可能会除以0（某两个相等的数相减，然后作为被除数这种情况）。。。。 还是太菜了，除以0都能写得出来。。。

题意

给定4个数，是否能用算术运算（±*/和括号）得到24？

分析

首先想到的是搜索，前半个小时一直在尝试深度优先搜索去尝试所有情况，但是代码越写越臭，直奔上百行去了，而且也A不掉。然后就仔细想了想以前玩24点游戏，我是怎么快速判断当前4张牌能够凑出24的？应该是先试探2张牌能凑出什么，然后往多了考虑3张牌、4张牌能凑出什么。

于是得出了最终的解决方案，有点动态规划的思想：

定义一个二维数组 m a r k [ i ] [ j ] mark[i][j] mark[i][j]表示 i i i这个状态能否凑出 j j j这个数字。由于数组很大，不妨把第二维换成 m a p map map，反正只是用来标记。其中 i i i是二进制位压缩的牌集合，例如 i = ( 10 ) 10 = ( 1010 ) 2 i=(10)_{10}=(1010)_2 i=(10)10​=(1010)2​表示取第1和第3张牌。然后就是1张牌、2张牌、3张牌、4张牌依次考虑能凑出来多少。

例如考虑3张牌能凑出来啥的时候，一定是由2张牌和1张牌计算而来的，而4张牌可能是3+1张牌或2+2张牌。

代码

#include 
using namespace std;

unordered_map<int, bool> mark[16];

void merge(int status1, int status2){
    int status = (status1 | status2);
    for (auto &x : mark[status1]){
        for (auto &y : mark[status2]){
            mark[status][x.first + y.first] = true;
            mark[status][abs(x.first - y.first)] = true;
            mark[status][x.first * y.first] = true;
            if (y.first > 0 && x.first % y.first == 0)
                mark[status][x.first / y.first] = true;
            if (x.first > 0 && y.first % x.first == 0)
                mark[status][y.first / x.first] = true;
        }
    }
}

bool damage(vector<int> &power){
    for (int i = 0; i < 16; i++)
        mark[i].clear();
    // 1 nums
    for (int i = 0; i < 4; i++)
        mark[1 << i][power[i]] = true;
    // 2 nums
    for (int i = 0; i < 4; i++)
        for (int j = i + 1; j < 4; j++)
            merge(1 << i, 1 << j);
    // 3 nums
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++)
                if (i != j && j != k && k != i)
                    merge((1 << i) | (1 << j), 1 << k);
    // 4 nums
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++)
                for (int t = 0; t < 4; t++)
                    if (i != j && i != k && i != t && j != k && j != t && k != t)
                    {
                        merge((1 << i) | (1 << j), (1 << k) | (1 << t));
                        merge((1 << i) | (1 << j) | (1 << k), 1 << t);
                    }
    return mark[15].count(24) > 0;
}

// 本地测试：
int main()
{
    vector<int> power({1, 1, 2, 7});
    cout << damage(power) << endl;
}