题目描述

Phil Kropotnik 是一名游戏制作人，需要为游戏设计非传统的骰子。给定一组已经确定的骰子，要求设计最后一个骰子的面值，使得所有骰子的组合能够满足特定的总和及其出现次数。具体来说：

• 输入包含多组数据，每组数据包括：
  • 已指定的骰子数量 n 及其面值。
  • 待确定骰子的面数 r 和 m 个条件，每个条件包括一个目标总和 v_i 和对应的组合数 c_i。
• 输出满足条件的骰子面值（非降序排列），如果无解则输出 "Impossible"。
• 骰子面值为 1 到 50 的整数，且需选择字典序最小的解。

解题思路

问题分析

1. 组合数计算：对于给定的骰子组合，计算所有可能的和及其出现次数。
2. 条件满足：设计的骰子必须满足所有给定的 (v_i, c_i) 条件。
3. 搜索空间：待确定骰子的面值范围为 1 到 50，且面数为 r（4 ≤ r ≤ 6），搜索空间较大，需优化。

关键步骤

1. 预处理已知骰子的和组合：

   • 使用动态规划计算已知骰子的所有可能和及其出现次数。
   • 例如，sum_counts[s] 表示已知骰子组合得到和 s 的方式数。

2. 计算待定骰子的贡献：

   • 对于待定骰子的每个可能面值 x，计算其对每个条件 (v_i, c_i) 的贡献：
     • 需要满足 sum_counts[v_i - x] 的和等于 c_i。
   • 预处理 x_contrib[i][x] = sum_counts[v_i - x]，表示面值 x 对条件 i 的贡献。

3. 回溯搜索：

   • 按非降序生成待定骰子的面值组合（避免重复搜索）。
   • 对于部分面值组合，检查是否能满足所有条件：
     • 当前贡献 + 剩余面值的最大/最小可能贡献是否可能满足条件。
     • 剪枝：如果当前部分面值已经无法满足条件，提前终止搜索。

4. 选择最优解：

   • 优先选择字典序最小的面值组合。

优化

• 字典序生成：按非降序生成面值组合，确保第一个找到的解即为字典序最小。
• 剪枝：利用预处理的最大/最小贡献信息，提前排除不可能的分支。
• 动态规划：高效计算已知骰子的和组合。

代码实现

#include <bits/stdc++.h>
using namespace std;

struct Condition {
	int v;
	int c;
};

vector<int> parse_faces(const string& line) {
	vector<int> res;
	istringstream iss(line);
	int f;
	iss >> f;
	for (int i = 0; i < f; ++i) {
		int x;
		iss >> x;
		res.push_back(x);
	}
	return res;
}

bool read_input(int& n, vector<vector<int>>& dice, int& r, vector<Condition>& conds) {
	string line;
	if (!getline(cin, line)) return false;
	while (line.empty()) {
		if (!getline(cin, line)) return false;
	}
	istringstream iss(line);
	iss >> n;
	if (n == 0) return false;
	dice.clear();
	for (int i = 0; i < n; ++i) {
		while (getline(cin, line)) {
			if (!line.empty()) break;
		}
		vector<int> faces = parse_faces(line);
		dice.push_back(faces);
	}
	while (getline(cin, line)) {
		if (!line.empty()) break;
	}
	istringstream iss2(line);
	int m;
	iss2 >> r >> m;
	conds.resize(m);
	for (int i = 0; i < m; ++i) {
		iss2 >> conds[i].v >> conds[i].c;
	}
	return true;
}

void preprocess_sum_counts(const vector<vector<int>>& dice, unordered_map<int, int>& sum_counts) {
	sum_counts.clear();
	sum_counts[0] = 1;
	for (const auto& die : dice) {
		unordered_map<int, int> new_counts;
		for (const auto& [s, cnt] : sum_counts) {
			for (int face : die) {
				new_counts[s + face] += cnt;
			}
		}
		sum_counts.swap(new_counts);
	}
}

void preprocess_x_contrib(int m, const vector<Condition>& conds, const unordered_map<int, int>& sum_counts, vector<vector<int>>& x_contrib) {
	x_contrib.assign(m, vector<int>(51, 0));
	for (int i = 0; i < m; ++i) {
		int v_i = conds[i].v;
		for (int x = 1; x <= 50; ++x) {
			int s = v_i - x;
			if (sum_counts.count(s)) {
				x_contrib[i][x] = sum_counts.at(s);
			} else {
				x_contrib[i][x] = 0;
			}
		}
	}
}

void preprocess_max_min_contrib(int m, const vector<Condition>& conds, const vector<vector<int>>& x_contrib, vector<vector<int>>& max_contrib, vector<vector<int>>& min_contrib) {
	max_contrib.assign(m, vector<int>(51, 0));
	min_contrib.assign(m, vector<int>(51, 0));
	for (int i = 0; i < m; ++i) {
		int current_max = 0;
		for (int x = 50; x >= 1; --x) {
			current_max = max(current_max, x_contrib[i][x]);
			max_contrib[i][x] = current_max;
		}
		int current_min = INT_MAX;
		for (int x = 50; x >= 1; --x) {
			current_min = min(current_min, x_contrib[i][x]);
			min_contrib[i][x] = current_min;
		}
	}
}

void backtrack(int pos, int last_val, vector<int>& current_faces, vector<int> current_c, const vector<Condition>& conds, int r, const vector<vector<int>>& x_contrib, const vector<vector<int>>& max_contrib, const vector<vector<int>>& min_contrib, vector<int>& best) {
	if (pos == r) {
		for (int i = 0; i < conds.size(); ++i) {
			if (current_c[i] != conds[i].c) {
				return;
			}
		}
		if (best.empty() || current_faces < best) {
			best = current_faces;
		}
		return;
	}
	for (int x = last_val; x <= 50; ++x) {
		vector<int> new_c = current_c;
		for (int i = 0; i < conds.size(); ++i) {
			new_c[i] += x_contrib[i][x];
		}
		bool possible = true;
		int remaining = r - pos - 1;
		for (int i = 0; i < conds.size(); ++i) {
			int required = conds[i].c;
			int max_p = new_c[i] + max_contrib[i][x] * remaining;
			int min_p = new_c[i] + min_contrib[i][x] * remaining;
			if (max_p < required || min_p > required) {
				possible = false;
				break;
			}
		}
		if (possible) {
			current_faces.push_back(x);
			backtrack(pos + 1, x, current_faces, new_c, conds, r, x_contrib, max_contrib, min_contrib, best);
			current_faces.pop_back();
		}
	}
}

void solve() {
	int n;
	vector<vector<int>> dice;
	int r;
	vector<Condition> conds;
	while (true) {
		if (!read_input(n, dice, r, conds)) {
			break;
		}
		unordered_map<int, int> sum_counts;
		preprocess_sum_counts(dice, sum_counts);
		vector<vector<int>> x_contrib;
		preprocess_x_contrib(conds.size(), conds, sum_counts, x_contrib);
		vector<vector<int>> max_contrib, min_contrib;
		preprocess_max_min_contrib(conds.size(), conds, x_contrib, max_contrib, min_contrib);
		vector<int> best;
		vector<int> current_faces;
		vector<int> current_c(conds.size(), 0);
		backtrack(0, 1, current_faces, current_c, conds, r, x_contrib, max_contrib, min_contrib, best);
		if (best.empty()) {
			cout << "Impossible" << endl;
		} else {
			cout << "Final die face values are";
			for (int x : best) {
				cout << " " << x;
			}
			cout << endl;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

示例解释

• 样例输入 1：
  • 已知骰子：[1, 10, 15, 20]。
  • 待定骰子面数：5，条件：(2,3), (3,1), (11,3), (16,4), (26,1)。
  • 输出：1 1 1 2 6，因为这是满足所有条件的最小字典序解。
• 样例输入 2：
  • 无解，输出 "Impossible"。
• 样例输入 3：
  • 输出 3 7 9 9，满足所有条件的最小字典序解。****