【NOIP提高组】虫食算

【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(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。

输出

输出包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

样例输入

5
ABCED
BDACE
EBBAA

样例输出

1 0 3 4 2

提示

【数据规模】
对于30％的数据，保证有N<＝10；
对于50％的数据，保证有N<＝15；
对于全部的数据，保证有N<＝26。

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对应0，B对应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对应0，B对应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💐点点关注，收藏不迷路💐

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/2042.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

练习LabVIEW第三十题

练习LabVIEW第三十题

学习目标&#xff1a; 刚学了LabVIEW&#xff0c;在网上找了些题&#xff0c;练习一下LabVIEW&#xff0c;有不对不好不足的地方欢迎指正&#xff01; 第三十题&#xff1a; 用labview写一个获取当前系统时间的程序 开始编写&#xff1a; 前面板添加一个字符串显示控件&am…
阅读更多...
书生大模型实战营 L0 入门岛

书生大模型实战营 L0 入门岛

书生大模型训练营入门岛任务——训练营链接 1. Linux前置知识 任务&#xff1a;端口转发 当使用vscode远程连接服务器时&#xff0c;在服务器运行的任务&#xff0c;vscode会自动帮忙进行端口映射&#xff0c;方便本地进行访问。 2. Python前置知识 任务1&#xff1a;Leec…
阅读更多...
【本科毕业设计】基于单片机的智能家居防火防盗报警系统

【本科毕业设计】基于单片机的智能家居防火防盗报警系统

基于单片机的智能家居防火防盗报警系统 源码下载摘要Abstract第1章 绪论1.1课题的背景1.2 研究的目的和意义 第2章 系统总体方案设计2.1 设计要求2.2 方案选择和论证2.2.1 单片机的选择2.2.2 显示方案的选择 第3章 系统硬件设计3.1 整体方案设计3.1.1 系统概述3.1.2 系统框图 3…
阅读更多...
＜项目代码＞YOLOv8 猫狗识别＜目标检测＞

＜项目代码＞YOLOv8 猫狗识别＜目标检测＞

YOLOv8是一种单阶段&#xff08;one-stage&#xff09;检测算法&#xff0c;它将目标检测问题转化为一个回归问题&#xff0c;能够在一次前向传播过程中同时完成目标的分类和定位任务。相较于两阶段检测算法&#xff08;如Faster R-CNN&#xff09;&#xff0c;YOLOv8具有更高的…
阅读更多...
前端项目使用高德地图插件

前端项目使用高德地图插件

高德开放平台 | 高德地图API 1、注册成为开发者 登录 高德开放平台控制台&#xff0c;如果没有开发者账号&#xff0c;请 注册开发者。 2. 创建key&#xff0c;项目里面要用 进入应用管理&#xff0c;创建新应用&#xff0c;新应用中添加 key&#xff0c;服务平台选择 Web端…
阅读更多...
统信UOS开发环境支持php

统信UOS开发环境支持php

UOS对PHP开发环境提供了灵活的选择，在这里开发者可以轻松搭建开发环境，是开发者最理想的选择。 文章目录 一、环境部署php开发环境安装二、代码示例PHP开发案例三、常见问题1. 权限问题2. PHP-FPM服务未正确启动或配置错误一、环境部署 php开发环境安装 php为服务器开发语言…
阅读更多...
word转ppt软件哪个好？这些工具你值得拥有

word转ppt软件哪个好？这些工具你值得拥有

在日常工作和学习中&#xff0c;我们经常需要将word文档转换为ppt幻灯片&#xff0c;以便于展示和汇报。 为了提高效率&#xff0c;市场上涌现了许多word转ppt工具&#xff0c;它们能够自动排版&#xff0c;帮助我们快速完成转换工作。 一、迅捷PPT &#x1f525;优势——多样…
阅读更多...
idm扩展自动更新，导致不能正常使用处理方法

idm扩展自动更新，导致不能正常使用处理方法

idm扩展自动更新&#xff0c;导致不能正常使用处理方法 针对于edge和chrome浏览器的设置 处理思路&#xff0c;设置权限&#xff0c;让浏览器的没有权限修改扩展的文件&#xff0c;从而关闭自动更新 具体做法 1找到idm安装路径&#xff0c;里面有IDMGCE.crx的文件就是扩展文…
阅读更多...
Spring框架的声明式事务

Spring框架的声明式事务

目录 一.配置文件的方式 1.配置文件 2.业务层 3.持久层 4.测试类 5.运行 6.查看数据库 7.出现异常运行 二.半注解的方式 1.配置文件 2.db.properties 3.持久层 4.业务层 5.测试类 6.运行 7.查看数据库 8.加上异常 三.纯注解的方式 1.持久层 2.业务层 3.配置…
阅读更多...
弹性布局flex-direction

弹性布局flex-direction

通常来讲&#xff0c;要布局一个底部按钮固定&#xff0c;中间内容可以滑动&#xff0c;都会用中间内容padding-bottom固定内容的高度来使内容可以滑动到看见全部。 如果在固定的内容里&#xff0c;有一个数据为动态&#xff0c;并且可以很多&#xff0c;会导致固定的内容高度不…
阅读更多...
spring ai 入门 之 结构化输出 - 把大模型llm返回的内容转换成java bean

spring ai 入门 之 结构化输出 - 把大模型llm返回的内容转换成java bean

目录 ​编辑 将AI非结构化文本转换为特定格式数据的应用场景说明 Spring AI 介绍 &#xff1a;为Java开发者打造的AI应用开发框架 Qwen 介绍 &#xff1a; 一个国内领先的开源大模型 Spring AI Alibaba框架介绍 &#xff1a; 一个国内最好的spring ai实现 使用spring ai …
阅读更多...
深入解析：物联网技术及其应用

深入解析：物联网技术及其应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 深入解析&#xff1a;物联网技术及其应用 深入解析&#xff1a;物联网技术及其应用 深入解析&#xff1a;物联网技术及其应用 物…
阅读更多...
.net core 接口,动态接收各类型请求的参数

.net core 接口,动态接收各类型请求的参数

[HttpPost] public async Task<IActionResult> testpost([FromForm] object info) { //Postman工具测试结果&#xff1a; //FromBody,Postman的body只有rawjson时才进的来 //参数为空时&#xff0c;Body(form-data、x-www-form-urlencoded)解析到的数据也有所…
阅读更多...
Python装饰器执行的顺序你知道吗

Python装饰器执行的顺序你知道吗

1. 引言 前面的文章中&#xff0c;讲到了 Python 装饰器的基础使用方式&#xff0c;在实际使用中&#xff0c;可能会遇到一个函数使用多个装饰器的情况&#xff0c;这个时候装饰器的顺序同样至关重要。本文将讨论装饰器的顺序如何影响函数的行为&#xff0c;并通过几个例子来说…
阅读更多...
嵌入式操作系统FreeRTOS文件详解

嵌入式操作系统FreeRTOS文件详解

系列文章目录 嵌入式操作系统FreeRTOS文件详解 嵌入式操作系统FreeRTOS文件详解 系列文章目录FreeRTOS下载 FreeRTOS下载 官网下载解压后得到的文件&#xff0c;如下图所示&#xff1a; 打开图 1.3.1.2 中的 FreeRTOS 子文件夹&#xff0c;就能够看到 FreeRTOS 内核的文件&…
阅读更多...
使用Jupyter Notebook进行数据科学项目

使用Jupyter Notebook进行数据科学项目

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用Jupyter Notebook进行数据科学项目 Jupyter Notebook 简介 安装 Jupyter Notebook 创建和管理 Notebook 编写和运行代码 示例…
阅读更多...
火山引擎VeDI数据服务平台：在电商场景中，如何解决API编排问题？

火山引擎VeDI数据服务平台：在电商场景中，如何解决API编排问题？

01 平台介绍 数据服务平台可以在保证服务高可靠性和高安全性的同时&#xff0c;为各业务线搭建数据服务统一出口&#xff0c;促进数据共享&#xff0c;为数据和应用之间建立了一座“沟通桥梁”。 同时&#xff0c;解决数据理解困难、异构、重复建设、审计运维困难等问题&#x…
阅读更多...
C#进阶1

C#进阶1

C#进阶1 本文章主要介绍C#的进阶知识&#xff0c;如反射&#xff0c;特性.... 参考视频链接 原码 文章目录 C#进阶1反射步骤泛型反射调用方法 获取属性 特性特性的定义步骤扩展枚举练习 反射 在 C# 中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&a…
阅读更多...
【深度学习】合合信息：生成式AI时代的内容安全与系统构建

【深度学习】合合信息：生成式AI时代的内容安全与系统构建

生成式AI时代的内容安全与系统构建 一、生成式 AI 的发展现状二、图像内容安全问题2.1、举几个伪造数字内容的例子2.1.1、谣言检测2.1.2、欺诈图像识别2.1.3、伪造信息 2.2、伪造文档/证照检测应用场景2.2.1、目前图像篡改主要涉及以下几个场景 2.3、合合信息伪造文档/证照检测…
阅读更多...
软件系统安全保证措施，质量保证措施方案（Word原件套用）

软件系统安全保证措施，质量保证措施方案（Word原件套用）

系统安全保证措施是构建稳固防御体系的核心&#xff0c;旨在全方位保障信息系统的安全性。以下是对这七项措施的简要概述&#xff1a; 一、身份鉴别&#xff1a;采用多种认证方式&#xff0c;如密码、生物识别等&#xff0c;确保用户身份的准确无误&#xff0c;防止非法入侵。 …
阅读更多...
最新文章

Copyright @ 2022~2023