题解 | #24dian#

F - 24dian

题意：
用张纸牌计算，这张纸牌所有可行的计算过程中都得包括一个小数，按字典序输出方案。

思路：
很容易推出是一定无解，至少可以通过排列好计算顺序，使得小数不存在。其余情况时，暴力枚举计算顺序和符号即可，枚举计算顺序时括号也就能被考虑进去了。每次从剩余集合内任意挑选两个数出来进行计算，算完再丢回去，进行下一轮计算，直到只剩下一个数为止。因为太菜写了结构体

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

typedef long long ll;
const int N = 3e4 + 7;
const int inf = 0x3f3f3f3f;
int n, m;

struct fen {
    int x, y;
    fen () {}
    fen (int x, int y) : x(x), y(y) {}
    fen operator*(const fen &a){
        int X = x * a.x, Y = y * a.y;
        int go = __gcd(X, Y);
        return fen(X / go, Y / go);
    }
    fen operator+(const fen &a){
        int X = x * a.y + a.x * y, Y = y * a.y;
        int go = __gcd(X, Y);
        return fen(X / go, Y / go);
    }
    fen operator-(const fen &a){
        int X = x * a.y - a.x * y, Y = y * a.y;
        int go = __gcd(X, Y);
        return fen(X / go, Y / go);
    }
    fen operator/(const fen &a){
        int X = x * a.y, Y = y * a.x;
        int go = __gcd(X, Y);
        return fen(X / go, Y / go);
    }
};

bool ok[2];

void dfs(vector<fen> v, int tp) {
    if (v.size() == 1) {
        if (v[0].y == 1 && v[0].x == m) ok[tp] = true;
        return;
    }
    for (int i = 0; i < v.size(); ++i) { // 选择一个i
        vector<fen> tmp;
        for (int j = 0; j < v.size(); ++j) {
            if (i != j) tmp.push_back(v[j]);
        }
        for (int j = 0; j < tmp.size(); ++j) { // 选择一个j
            vector<fen> nxt;
            for (int k = 0; k < tmp.size(); ++k) if (k != j) nxt.push_back(tmp[k]);
            fen to = v[i] + tmp[j];
            nxt.push_back(to);
            dfs(nxt, tp | (to.y != 1)); // y != 1说明除不尽，即存在小数
            nxt.pop_back();
            if (ok[0]) return;

            to = v[i] - tmp[j];
            nxt.push_back(to);
            dfs(nxt, tp | (to.y != 1));
            nxt.pop_back();
            if (ok[0]) return;

            to = v[i] * tmp[j];
            nxt.push_back(to);
            dfs(nxt, tp | (to.y != 1));
            nxt.pop_back();
            if (ok[0]) return;

            if (tmp[j].x == 0) continue;
            to = v[i] / tmp[j];
            nxt.push_back(to);
            dfs(nxt, tp | (to.y != 1));
            nxt.pop_back();
            if (ok[0]) return;
        }
    }
}

bool ans[17][17][17][17];
int num;

void run() {
    scanf("%d %d", &n, &m);
    if (m >= 13 * 13 * 13 * 13 || n <= 3) {
        puts("0");
        return;
    }

    for (int a = 1; a <= 13; ++a) {
        for (int b = a; b <= 13; ++b) {
            for (int c = b; c <= 13; ++c) {
                for (int d = c; d <= 13; ++d) {
                    vector<fen> v;
                    v.push_back(fen(a, 1));
                    v.push_back(fen(b, 1));
                    v.push_back(fen(c, 1));
                    v.push_back(fen(d, 1));
                    ok[0] = ok[1] = false;
                    dfs(v, 0);
                    if (ok[1] && !ok[0]) {
                        num++;
                        ans[a][b][c][d] = true;
                    }
                }
            }
        }
    }

    printf("%d\n", num);
    for (int a = 1; a <= 13; ++a) {
        for (int b = 1; b <= 13; ++b) {
            for (int c = 1; c <= 13; ++c) {
                for (int d = 1; d <= 13; ++d) {
                    if (ans[a][b][c][d]) {
                        printf("%d %d %d %d\n", a, b, c, d);
                    }
                }
            }
        }
    }
} 

int main() {
//    init();
    int t = 1;
//    scanf("%d", &t);
//    printf("%d\n", 13 * 13 *13 *13);
    while (t--) run();
    return 0;
}