【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💐点点关注,收藏不迷路💐 |
相关文章:
【NOIP提高组】虫食算
【NOIP提高组】虫食算 C语言C 💐The Begin💐点点关注,收藏不迷路💐 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子: 43#98…...
软件测试面试题个人总结
前面看到了一些面试题,总感觉会用得到,但是看一遍又记不住,所以我把面试题都整合在一起,都是来自各路大佬的分享,为了方便以后自己需要的时候刷一刷,不用再到处找题,今天把自己整理的这些面试题…...
HTML 语法规范——代码注释、缩进与格式、标签与属性、字符编码等
文章目录 一、代码注释1.1 使用注释的主要目的1.2 使用建议二、标签的使用2.1 开始标签和结束标签2.2 自闭合标签2.3 标签的嵌套2.4 标签的有效性三、属性四、缩进与格式4.1 一致的缩进4.2 元素单独占用一行4.3 嵌套元素的缩进4.4 避免冗长的行五、字符编码六、小结在开发 HTML…...
【Wi-Fi】WiFi中QAM及16-QAM、64-QAM、512-QAM、1024-QAM、2048-QAM、4096-QAM整理
参考链接 什么是QAM?QAM是如何工作的? - 华为 不同阶QAM调制星座图中,符号能量的归一化计算原理 - 知乎 16 QAM modulation vs 64 QAM modulation vs 256 QAM modulation 512 QAM vs 1024 QAM vs 2048 QAM vs 4096 QAM modulation type…...
红黑树的平衡之舞:数据结构中的优雅艺术
文章目录 前言🚀一、红黑树的介绍1.1 红黑树的概念1.2 红黑树的特点1.3 红黑树的性质 🚀二、红黑树结点的定义🚀三、红黑树的框架🚀四、旋转操作🚀五、红黑树的插入操作5.1 uncle结点存在且为红5.2 uncle结点不存在或者…...
angular实现list列表和翻页效果
说明:angular实现list列表和翻页效果 上一页 当前页面 下一页 效果图: step1: E:\projectgood\ajnine\untitled4\src\app\car\car.component.css .example-form-fields {display: flex;align-items: flex-start; }mat-list-item{background: antiquew…...
闯关leetcode——3285. Find Indices of Stable Mountains
大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/find-indices-of-stable-mountains/description/ 内容 There are n mountains in a row, and each mountain has a height. You are given an integer array height where height[i] represents t…...
算法【Java】—— 动态规划之斐波那契数列模型
动态规划 动态规划的思路一共有五个步骤: 状态表示:由经验和题目要求得出,这个确实有点抽象,下面的题目会带大家慢慢感受状态标识状态转移方程初始化:避免越界访问 dp 表,所以在进行填表之前我们要预先填…...
idea连接docker并构建镜像
安装docker 安装docker idea连接docker 安装docker插件 设置docker连接 设置docker.exe 这个docker.exe是为了运行docker,可以通过安装docker desktop获取 docker desktop下载地址 右键图标找到文件位置 在同级的resource中 编写Dockerfile # 使用官方 Nginx…...
百度如何打造AI原生研发新范式?
👉点击即可下载《百度AI原生研发新范式实践》资料 2024年10月23-25日,2024 NJSD技术盛典暨第十届NJSD软件开发者大会、第八届IAS互联网架构大会在南京召开。本届大会邀请了工业界和学术界的专家,优秀的工程师和产品经理,以及其它行…...
RedisTemplate类中的常用方法粗解(简单明了,预计5分钟看完)
在阅读项目代码过程中发现引用RedisTemplate 的方法操作redis时,都会有一些特定的ops ,对此好奇就查资料的情况下有了本博客。 操作之前付一张我们项目中的用到的地方的图 另外本文中的语言用到的是Java,附上试验用到的redisTemplete依赖 <…...
鸿蒙ArkTS中的布局容器组件(Column、Row、Flex、 Stack、Grid)
在鸿蒙ArkTS中,布局容器组件有很多,常见的有: ⑴ Column:(垂直布局容器):用于将子组件垂直排列。 ⑵ Row:(水平布局容器):用于将子组件水…...
显存占用 显存测试
目录 显存测试 显存占用示例 一个模型多卡占用 显存测试 import torch# 计算张量的大小(例如:每个 float 占用 4 字节) # 40GB 40 * 1024 * 1024 * 1024 字节 # 每个 float 4 字节,因此需要的 float 数量为 (40 * 1024 * 1024…...
快速入门CSS
欢迎关注个人主页:逸狼 创造不易,可以点点赞吗 如有错误,欢迎指出~ 目录 CSS css的三种引入方式 css书写规范 选择器分类 标签选择器 class选择器 id选择器 复合选择器 通配符选择器 color颜色设置 border边框设置 width/heigth 内/外边距 C…...
AcWing 1073 树的中心 树形dp (详解)
这道题目非常有新意,在过去,我们通常先访问子节点去更新父节点的状态,但是这道题我们还需要从父节点去更新子节点。 我们可以想象为向上和向下两个方向,我们任取一点,先向下走,再回来更新上面的点…...
modelscope下载Qwen2.5 72B 模型方法
conda create -n modelscope python=3.10 conda activate modelscopepip install modelscope执行这个python代码: from modelscope.hub.snapshot_download import snapshot_download# 下载模型到当前路径 model_dir = snapshot_download(...
重学SpringBoot3-整合 Elasticsearch 8.x (二)使用Repository
更多SpringBoot3内容请关注我的专栏:《SpringBoot3》 期待您的点赞👍收藏⭐评论✍ 整合 Elasticsearch 8.x (二)使用Repository 1. 环境准备1.1 项目依赖1.2 Elasticsearch 配置 2. 使用Repository的基本步骤2.1 创建实体类2.2 创…...
为什么说模拟电路的难点就在开通过程和关断过程?难在什么地方?
模拟电路中开通过程和关断过程之所以困难,主要有以下几个方面的原因: 1. 瞬态响应特性复杂 - 在开通和关断瞬间,电路中的电流和电压会发生快速变化,产生复杂的瞬态响应。这些瞬态响应可能包含过冲、下冲、振铃等现象,…...
CubeIDE BUG-project‘hello‘has no explict encoding set hello
projecthellohas no explict encoding set hello 解决方法: 点击红色处注册账号后登录,删除原本文件后重新生成即可。...
在线PDF转图片网站
https://www.ilovepdf.com/download/qgxkmbzgxt6yb3s8l9f7fc3q9606hq0bfh4b33mnrf3p7tp8l0d4qy386b5dxqwjbhq7j3j4tp20m4dnb89wA9jjw25br1gtAw42l0m1sq047nvld4qqrm8kzjplkAhw9458p4wjgbmn08g49l23c1khsggdx4A7z3m9xh19mgzdlllyA6r1/52 在线excel转图片 https://www.zamzar.c…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
