简单解题思路

问题描述

给定两个数字 n 和 m，模拟一个猜数字游戏的过程：

• 数字对 (j, k)（1 ≤ j < k ≤ n）是隐藏的，玩家需要通过 m 轮提示猜出这对数字。
• 每轮提示要么给出两数之和 s = j + k，要么给出两数之积 p = j * k。
• 目标是统计所有满足条件的数字对 (j, k)，使得玩家恰好在 m 轮提示后才能确定这对数字。

核心思路

1. 预处理所有可能的数字对：

   • 预计算所有 (j, k) 的和与积，并存储每个积对应的所有因数对 fac[p]。

2. 动态规划搜索：

   • 使用 f[j][k] 表示猜出 (j, k) 所需的最少轮数。
   • 通过 search(j, k, dep) 函数模拟猜数字的过程：
     • 如果当前轮数 dep 是偶数，检查是否可以通过和 s = j + k 排除其他可能的 (i, s-i)。
     • 如果当前轮数 dep 是奇数，检查是否可以通过积 p = j * k 排除其他可能的因数对 fac[p]。
   • 如果当前轮数可以确定 (j, k)，则更新 f[j][k] = dep。

3. 统计结果：

   • 遍历所有 (j, k)，统计 f[j][k] == m 的数字对，输出它们的数量和具体值。

关键步骤

1. 预处理：

   • 计算所有 (j, k) 的积 p = j * k，并存储每个 p 的所有因数对 fac[p]。

2. 搜索与更新：

   • 对于每对 (j, k)，模拟 m 轮提示，检查是否能在 m 轮内确定该数字对。
   • 更新 f[j][k] 为最小的满足条件的轮数。

3. 输出结果：

   • 统计所有 f[j][k] == m 的数字对，输出它们的数量和具体值。

总结

• 核心算法：动态规划 + 模拟猜数字过程。
• 适用场景：逻辑推理游戏、交互式问题求解。
• 优化点：预处理因式分解结果，避免重复计算。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 205;
int n, f[N][N], tot[N * N];
pair<int, int> fac[N * N][15]; // 15 试出来的，否则 MLE

int search(int a, int b, int dep) {
    // 搜索 j，k 是否要 i 次才能猜出来
    int s = a + b, p = a * b, i, flag = 1;
    if (dep % 2 == 0) {
        for (i = 1; i + i < s; i++) {
            if (i != a && s - i <= n && f[i][s - i] >= dep) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            f[a][b] = dep;
        }
    } else {
        for (i = 1; i <= tot[p]; i++) {
            if (fac[p][i].first != a && f[fac[p][i].first][fac[p][i].second] >= dep) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            f[a][b] = dep;
        }
    }
    return f[a][b] == dep;
}

void preset() {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            tot[i * j]++;
            fac[i * j][tot[i * j]] = make_pair(i, j);
        }
    }
}

int main() {
    int i, j, k, m, ans = 0;
    cin >> n >> m;
    memset(f, 0x3f, sizeof(f));
    preset();
    for (i = 0; i <= m; i++) {
        int flag = 0;
        for (j = 1; j <= n; j++) {
            for (k = j + 1; k <= n; k++) {
                if (f[j][k] > m) {
                    flag |= search(j, k, i);
                }
            }
        }
        if (!flag) {
            break;
        }
    }
    for (i = 1; i <= n; i++) {
        for (j = i + 1; j <= n; j++) {
            if (f[i][j] == m) {
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    for (i = 1; i <= n; i++) {
        for (j = i + 1; j <= n; j++) {
            if (f[i][j] == m) {
                printf("%d %d\n", i, j);
            }
        }
    }
    return 0;
}