ui网站建设站评价,电脑系统网站建设,北京网站排名seo,网站建设网点【NOIP提高组】虫食算 C语言C #x1f490;The Begin#x1f490;点点关注#xff0c;收藏不迷路#x1f490; 所谓虫食算#xff0c;就是原先的算式中有一部分被虫子啃掉了#xff0c;需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子#xff1a;
43#98… 【NOIP提高组】虫食算 C语言C The Begin点点关注收藏不迷路
所谓虫食算就是原先的算式中有一部分被虫子啃掉了需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子
43#9865#045 8468#6633 44445506678 其中#号代表被虫子啃掉的数字。根据算式我们很容易判断第一行的两个数字分别是5和3第二行的数字是5。 现在我们对问题做两个限制
首先我们只考虑加法的虫食算。这里的加法是N进制加法算式中三个数都有N位允许有前导的0。 其次虫子把所有的数都啃光了我们只知道哪些数字是相同的我们将相同的数字用相同的字母表示不同的数字用不同的字母表示。如果这个算式是N进制的我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。 BADC CRDA DCCC
上面的算式是一个4进制的算式。很显然我们只要让ABCD分别代表0123便可以让这个式子成立了。你的任务是对于给定的N进制加法算式求出N个不同的字母分别代表的数字使得该加法算式成立输入数据保证有且仅有一组解。
输入 输入包含4行。第一行有一个正整数N(N26)后面的3行每行有一个由大写字母组成的字符串分别代表两个加数以及和。这3个字符串左右两端都没有空格从高位到低位并且恰好有N位。
输出
输出包含一行。在这一行中应当包含唯一的那组解。解是这样表示的输出N个数字分别表示ABC……所代表的数字相邻的两个数字用一个空格隔开不能有多余的空格。
样例输入
5
ABCED
BDACE
EBBAA样例输出
1 0 3 4 2提示
【数据规模】 对于30的数据保证有N10 对于50的数据保证有N15 对于全部的数据保证有N26。
C语言
#include stdio.h
#include string.h// 最大可能的字符数可根据实际情况调整
#define MAX_CHARS 30 int numDigits; // 存储进制数N简称numDigits
char addends[4][MAX_CHARS]; // 存储算式的三个数两个加数与和简称addends数组
int usedDigits[MAX_CHARS]; // 标记数字是否已被使用简称usedDigits数组
int digitMapping[MAX_CHARS]; // 存储字母到数字的映射简称digitMapping数组
int solutionFound; // 标记是否已找到解简称solutionFound// 将字符转换为对应的索引A对应0B对应1以此类推
int charToIndex(char c) {return c - A;
}// 递归搜索可能的字母到数字的映射以找到满足算式的解
void searchMapping(int row, int col, int carry) {int i;// 如果已经找到解直接返回if (solutionFound 1) {return;}// 如果已经处理完所有列从高位到低位if (col -1) {// 如果进位为0说明找到了满足算式的解if (carry 0) {for (i 0; i numDigits; i) {printf(%d , digitMapping[i]);}solutionFound 1;}return;}// 检查当前列的各位数字是否满足加法规则考虑进位for (i col; i 0; i--) {int digit1 digitMapping[charToIndex(addends[1][i])];int digit2 digitMapping[charToIndex(addends[2][i])];int digit3 digitMapping[charToIndex(addends[3][i])];if (digit1 -1 || digit2 -1 || digit3 -1) {continue;}if ((digit1 digit2) % numDigits! digit3 (digit1 digit2 1) % numDigits! digit3) {return;}}// 如果当前位置的字母还没有映射到数字if (digitMapping[charToIndex(addends[row][col])] -1) {for (i numDigits - 1; i 0; i--) {if (!usedDigits[i]) {// 如果不是处理和的那一行if (row! 3) {digitMapping[charToIndex(addends[row][col])] i;usedDigits[i] 1;searchMapping(row 1, col, carry);digitMapping[charToIndex(addends[row][col])] -1;usedDigits[i] 0;} else {int sum digitMapping[charToIndex(addends[1][col])] digitMapping[charToIndex(addends[2][col])] carry;if (sum % numDigits! i) {continue;}usedDigits[i] 1;digitMapping[charToIndex(addends[row][col])] i;searchMapping(1, col - 1, sum / numDigits);usedDigits[i] 0;digitMapping[charToIndex(addends[row][col])] -1;}}}} else {// 如果当前位置的字母已经有映射if (row! 3) {searchMapping(row 1, col, carry);} else {int sum digitMapping[charToIndex(addends[1][col])] digitMapping[charToIndex(addends[2][col])] carry;if (sum % numDigits! digitMapping[charToIndex(addends[3][col])]) {return;}searchMapping(1, col - 1, sum / numDigits);}}
}int main() {// 读取进制数Nscanf(%d, numDigits);// 读取算式的三个数scanf(%s%s%s, addends[1], addends[2], addends[3]);// 初始化数字映射数组为 -1表示未映射memset(digitMapping, -1, sizeof(int) * numDigits);// 初始化是否找到解的标记为0solutionFound 0;// 开始搜索满足算式的字母到数字的映射searchMapping(1, numDigits - 1, 0);return 0;
}C
#include iostream
#include string
#include cstring// 最大可能的字符数可根据实际情况调整
const int MAX_CHARS 30; int numDigits; // 存储进制数N简称numDigits
std::string addends[4]; // 存储算式的三个数两个加数与和简称addends数组
int usedDigits[MAX_CHARS]; // 标记数字是否已被使用简称usedDigits数组
int digitMapping[MAX_CHARS]; // 存储字母到数字的映射简称digitMapping数组
bool solutionFound; // 标记是否已找到解简称solutionFound// 将字符转换为对应的索引A对应0B对应1以此类推
int charToIndex(char c) {return c - A;
}// 递归搜索可能的字母到数字的映射以找到满足算式的解
void searchMapping(int row, int col, int carry) {int i;// 如果已经找到解直接返回if (solutionFound) {return;}// 如果已经处理完所有列从高位到低位if (col -1) {// 如果进位为0说明找到了满足算式的解if (carry 0) {for (i 0; i numDigits; i) {std::cout digitMapping[i] ;}solutionFound true;}return;}// 检查当前列的各位数字是否满足加法规则考虑进位for (i col; i 0; i--) {int digit1 digitMapping[charToIndex(addends[1][i])];int digit2 digitMapping[charToIndex(addends[2][i])];int digit3 digitMapping[charToIndex(addends[3][i])];if (digit1 -1 || digit2 -1 || digit3 -1) {continue;}if ((digit1 digit2) % numDigits! digit3 (digit1 digit2 1) % numDigits! digit3) {return;}}// 如果当前位置的字母还没有映射到数字if (digitMapping[charToIndex(addends[row][col])] -1) {for (i numDigits - 1; i 0; i--) {if (!usedDigits[i]) {// 如果不是处理和的那一行if (row! 3) {digitMapping[charToIndex(addends[row][col])] i;usedDigits[i] 1;searchMapping(row 1, col, carry);digitMapping[charToIndex(addends[row][col])] -1;usedDigits[i] 0;} else {int sum digitMapping[charToIndex(addends[1][col])] digitMapping[charToIndex(addends[2][col])] carry;if (sum % numDigits! i) {continue;}usedDigits[i] 1;digitMapping[charToIndex(addends[row][col])] i;searchMapping(1, col - 1, sum / numDigits);usedDigits[i] 0;digitMapping[charToIndex(addends[row][col])] -1;}}}} else {// 如果当前位置的字母已经有映射if (row! 3) {searchMapping(row 1, col, carry);} else {int sum digitMapping[charToIndex(addends[1][col])] digitMapping[charToIndex(addends[2][col])] carry;if (sum % numDigits! digitMapping[charToIndex(addends[3][col])]) {return;}searchMapping(1, col - 1, sum / numDigits);}}
}int main() {// 读取进制数Nstd::cin numDigits;// 读取算式的三个数for (int i 1; i 3; i) {std::cin addends[i];}// 初始化数字映射数组为 -1表示未映射std::memset(digitMapping, -1, sizeof(int) * numDigits);// 初始化是否找到解的标记为falsesolutionFound false;// 开始搜索满足算式的字母到数字的映射searchMapping(1, numDigits - 1, 0);return 0;
}The End点点关注收藏不迷路
