ACW4314.三元组

题目

原题链接

思路

• 整体思路：暴力搜索 + 哈希表优化
• 暴力遍历，遇到已经访问过的位置就提前剪枝，提高速度。
• 哈希表使用技巧vis[a << 20 | b << 10 | c]可以将三元组和访问状态进行一一映射。避免了使用更繁琐的数据结构。
• 树如下图所示

注意访问次序

代码

#include <iostream>
#include <unordered_map>

using namespace std;

void dfs(int a, int b, int c, int n, unordered_map<int, int>& vis, int& ans) {
    if (a > n || b > n || c > n) {
        return;
    }

    if (vis[a << 20| b << 10| c] == 1) {
        return;
    }

    if (!(1 <= a && a <= b && b <= c && c <= n)){
        return;
    }

    vis[a << 20| b << 10| c] = 1;

    if (((a ^ b ^ c) == 0) && (a + b > c)) {
        ans += 1;
    }

    dfs(a + 1, b, c, n, vis, ans);
    dfs(a, b + 1, c, n ,vis, ans);
    dfs(a, b, c + 1, n, vis, ans);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    unordered_map<int, int> vis;

    int ans = 0;
    dfs(1, 1, 1, n, vis, ans);
    printf("%d", ans);
    return 0;
}