闲人の题解 P1834

violet

文章标签

首页

归档

标签

关于

友人帐

载入天数...

载入时分秒...

总访问量: | 访问人数:

2021-11-20

6 min read

题解

闲人の题解 P1834

题目描述

1 ~ 9 的数用四则运算凑成 24。
满足答案字典序最小。
题目保证有解。

题目传送门

讲解

Round1

此题关键在于字典序。先让我们来想一想，什么情况下字典序.可以尽可能小？ $(((3 * 5)+2)+7)$ 这是样例给出的答案。
观察一下，为什么他要把三个括号放在前面？显然，因为“()”的 ASCII 码是运算符里（仅限于本题）最小的。所以如果我们可以把式子写成 $(((A\operatorname{opr} B)\operatorname{opr} C)\operatorname{opr} D)$ （注：opr 指运算符）的形式就不需要额外考虑怎么加括号的事了！

Round2

分析一下刚刚我们处理字典序的方法，不难发现其中的 BUG！如果遇上了 $ 5 5 5 5 $ 的情况显然用刚才的表达式是无法求出解的，而只能换成 $((5* 5)-(5/5))$ 的形式。所以当我们遇到这样的情况，先看一下第一种情况行不行的通，行不通再用第二种方法。

Round3

我们如何来比对那个式子的字典序最小呢？我们可以用一个 cmp 数组初始为“zzzzzzzzzzzzz”然后每搜到一个答案就把它替换掉。

Round4

深搜的思路也比较简单，先枚举四张牌，在枚举运算符，然后把得到的数值递归到下一层，最后判断是否等于 24 即可。

Round5

其他的细节会在代码注释里出现，这样方便同学们理解。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int src[5]; //面值
char opr[4] = {'+', '-', '*', '/'};
char out[15] = {'(', '(', '(', '\0', '\0', '\0', ')', '\0', '\0', ')', '\0', '\0', ')'};
//数字在（从“0”开始数）第3，5，8，11的位置 
//可以推出公式：除第1个数字在位置3外，第n个数字在3 * n - 1
//运算符同理：第n个运算符在3 * n - 2(符号只有三个)
char cmp[15] = "zzzzzzzzzzzzz";  
bool u[5];
int calc(int a, int b, int cal)
{
    switch (cal)
    {
    case (0):
        return a + b;
    case (1):
        return a - b;
    case (2):
        return a * b;
    case (3):
        return a / b;
    default:
        return -1;
    }
}

void search_second(int d)		//第二种情况 
{
    int A, B;
    int sum;
    for (int a1 = 1; a1 <= 4; a1++)
    {
        for (int a2 = 1; a2 <= 4; a2++)
        {
            if (a2 == a1)
                continue;
            for (int a3 = 1; a3 <= 4; a3++)
            {
                if (a3 == a1 || a3 == a2)
                    continue;
                for (int a4 = 1; a4 <= 4; a4++) //24
                {
                    if (a4 == a1 || a4 == a2 || a4 == a3)
                        continue;
                    for (int i = 0; i < 4; i++)
                    {
                        if (i == 3 && src[a1] % src[a2] != 0)
                        {
                            continue;
                        }
                        for (int j = 0; j < 4; j++)
                        {
                            if (j == 3 && src[a3] % src[a4] != 0)
                            {
                                continue;
                            }
                            A = calc(src[a1], src[a2], i);
                            B = calc(src[a3], src[a4], j);

                            for (int q = 0; q < 4; q++)
                            {
                                if (q == 3)
                                {
                                    if (A != 0 && B != 0)
                                    {
                                        if (A % B != 0)
                                            continue;
                                    }
                                    else
                                        continue;
                                }

                                sum = calc(A, B, q);
                                if (sum == 24)
                                {
                                    int x1 = src[a1], x2 = src[a2], x3 = src[a3], x4 = src[a4];
                                    out[0] = '(';
                                    out[1] = '(';
                                    out[2] = x1 + '0';
                                    out[3] = opr[i];
                                    out[4] = x2 + '0';
                                    out[5] = ')';
                                    out[6] = opr[q];
                                    out[7] = '(';
                                    out[8] = x3 + '0';
                                    out[9] = opr[j];
                                    out[10] = x4 + '0';
                                    out[11] = ')';
                                    out[12] = ')';

                                    if (strcmp(out, cmp) < 0)
                                    {
                                        strcpy(cmp, out);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return;
}

void search(int d, int sum)
{
    if (d > 4)
    {
        if (sum == 24 && strcmp(out, cmp) < 0)
        {
            strcpy(cmp, out);
        }
        return;
    }
    for (int i = 1; i <= 4; i++)
    {
        if (!u[i])
        {
            u[i] = 1;
            if (d == 1)
            {
                out[3] = char(src[i] + '0');
            }
            else
            {
                out[3 * d - 1] = char(src[i] + '0'); //放数字
            }
            for (int j = 0; j < 4; j++)
            {
                int tmps = sum;
                if (j == 3 && tmps % src[i] != 0)
                {
                    continue;
                }
                if (d == 1)
                {
                    search(d + 1, src[i]);
                    break;
                }
                tmps = calc(tmps, src[i], j); //计算当前能算出的数值
                out[3 * d - 2] = opr[j];      //放符号
                search(d + 1, tmps);          //下一个数
                out[3 * d - 2] = '\0';
            }
            if (d == 1)
            {
                out[3] = '\0';
            }
            else
            {
                out[3 * d - 1] = '\0';
            }
            u[i] = 0;
        }
    }
    return;
}
int main()
{
    for (int i = 1; i <= 4; i++)
    {
        cin >> src[i];
    }
    search(1, 0);
    if (cmp[1] == 'z')						//如果第一种情况找不出就换第二种 
    {
        search_second(1);
    }
    puts(cmp);
    return 0;
}