本题是浙江理工大学ACM入队200题第八套中的J题
我们先来看一下这题的题面.
宁宁参加奥数班，他遇到的第一个问题是这样的：口口口+口口口=口口口，宁宁需要将1~9 九个数分别填进对应的空格内，使等式成立。现在宁宁填了一个算式，你能帮他验证是否正确么？
输入为多组测试数据。
分别输入三个三位数，依次表示等式里的三个数。
如果等式成立，输出：YES!，否则输出：NO!
173 286 459
YES!
这题很多朋友都想当然地以为只需要判断等式是否成立即可,都选择性的忽视了题目中明确写出的要求:将1~9九个数分别填进对应的空格内.
所以我们需要额外实现判断没有使用重复的数.
如何实现捏?首先我们需要依次取出每个数的各个十进制位,这里我已经有一篇博客给出明确的方法介绍了,不清楚的可以去看看(点我看鸭),这里不多赘述了.
接下来困住大多数朋友的都是判断重复数字了,很多朋友对此毫无思路.
我们先来想想我们人脑是怎么判断有没有数字重复的呢?打个比方我们要在一组数字中找第一个数是否重复,那么当我们看到这组数字中的一个数后,我们会接着往后去看有没有第二个这个数出现,如果有就是重复了,否则就是没有.
我们是否也可以这样实现我们这里判断重复的代码捏?答案是可行的,我们可以把这三个数的每个位合起来看成一个"数组"中的元素,然后从左到右遍历这个"数组",再对于每一个遍历到的数之后的数进行一次遍历,看看其中是否有和这个数相等的数存在.不过这种思路遍历次数较多,比较接近暴力算法,时间复杂度很高(可以理解成代码运行的速度很慢),属于一种无解算法.所以我们需要寻找一个更好的算法.(这种思路的代码就不贴了,想练代码可以自己写写试试,交上去不清楚会不会时间超限,没试过)
我们前面的算法慢在哪呢?慢在我们每次都对遍历到的数再启动了一次遍历,这使得我们遍历的次数过多.而且每次遍历都是在重复遍历这些数.我们是否可以避免这些重复的操作,以此提高速度呢?答案是可行的.
那如何避免重复操作呢?我们可以对遍历到的数进行一次记录,记录什么呢?我们上面这样判断的本质其实是在看有没有哪个数字重复出现了两次及以上,所以我们就记录每个数字出现了几次即可,这样仅通过一次遍历,我们便得到了可以判断是否有重复数字的数据,大大减少了遍历的次数.这其实便是所谓的用空间换时间的技巧.
那用什么记录呢?我们目前会的数据结构非常少,基本只有数组.那能否通过数组来记录呢?当前可以!我们希望记录的形式是"数字:数字出现次数"这样形式的一个对子,并且我们可以通过数字来访问到这个数字出现的次数.这个对子和数学上的映射很像.而这个映射完全可以由数组来完成,因为数组本身的随机访问也可以看成一种映射.
我们知道,当我们给定数组中某个元素的下标,我们即可得到这个下标对应的那个元素(即随机访问),这便是一种现成的映射.那我们自然可以通过把数字作为下标,把数字出现的次数作为下标对应的元素,来充分利用数组自带的这种映射实现我们需要的功能.即,我们使用一个长度为10的数组,在其下标1到9的各个元素中存储1到9各个数字出现的次数.这样我们就可以通过各个数字来直接访问到各个数字出现的个数了.在这里,这个数组也被称作桶,是不是很形象鸭?当然,如果有一定数据结构基础的朋友看到我们的需求,应该会马上联想到哈希表,不过这题没必要使用,因为桶广义地来讲也是一种哈希表(哈希函数返回这个数字本身).
下面给出了我自己做这道题时候的完整代码:
(仅作为参考,一定要自己写一下奥,作弊没意思,害人又害己)
#include <stdio.h>
#include <string.h>
// 数组最好定义在main外面(以后你们会知道为啥的)
int num[10]; // 作为桶,下标所对应的元素储存着下标这个数字出现的次数,由此形成一个一一映射
int main()
{
int a, b, c;
while (scanf("%d%d%d", &a, &b, &c) != EOF)
{
if (a + b != c) // 如果不满足加法式,直接输出然后输入下一组
{
printf("NO!\n");
continue; // 跳过本组处理,开始下一组的输入
}
for (int i = 0; i < 3; i++) // 各个数字依次取出各个位
{
num[a % 10]++; // 下标为该数字的元素储存着该数字出现的次数,将该数字的出现次数加一
a /= 10;
num[b % 10]++;
b /= 10;
num[c % 10]++;
c /= 10;
}
int i; // 为了判断for是否正常退出这里我i定义在外面,也可以在单独搞一个变量来记录是否有数重复
for (i = 1; i < 9; i++)
{
if (num[i] > 1) // 如果一个数字出现了两次
{
printf("NO!\n");
break; // 直接跳出这个for循环,不用再找有没有重复了(只要一组重复就不满足了)
}
}
if (i == 9) // for正常退出时i应为9,如果不为9就是被break强行退出了
{
printf("YES!\n");
}
memset(num, 0, sizeof(num)); // 桶初始化(别忘了鸭!不然就会连着上次输入一起累加了)如果不会用memset也可以考虑直接写一个for循环把每一元素设置为0
}
return 0;
}
"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德
这篇题解就到这里了,各位朋友如果有问题欢迎到acm成员群中提问哦!
所有题目均有五种语言实现。C实现目录、C++实现目录、Python实现目录、Java实现目录、JavaScript实现目录题目n行m列的矩阵，每个位置上有一个元素你可以上下左右行走，代价是前后两个位置元素值差的绝对值.另外，你最多可以使用一次传送阵(只能从一个数跳到另外一个相同的数)求从走上角走到右下角最少需要多少时间。输入描述：第一行两个整数n,m，分别代表矩阵的行和列。后面n行，每行m个整数，分别代表矩阵中的元素。输出描述：一个整数，表示最少需要多少时间。
我试图在我的RubyonRails应用程序中调试一个极其缓慢的请求调用。我已设法根据自己的喜好优化Controller方法，Rails的日志告诉我它已在XX毫秒内完成操作(Completed200OKin5049ms(Views:34.9ms|ActiveRecord:76.3ms)).但是，在加载页面时，在浏览器中实际呈现任何内容之前打印此消息很长；最多约15秒的等待时间。Rackmini-profiler证实了这一点，告诉我GET操作(不计算完成Controller操作所花费的时间)花费了14秒左右。(分析器还确认Controller操作的执行时间约为5秒)。我可以接受Contro
我正在使用SendgridParseAPI和Griddlergem来接受传入的电子邮件。在大多数情况下，这工作正常；但是，如果您未使用状态代码200响应Sendgrid，他们将假定该应用程序未正确接收POST请求并继续尝试进行POST3天。我正在尝试使用状态代码进行响应，但遇到了问题。在常规的RESTful路由中，您可以执行类似...render:status=>200但是，我认为这必须在Controller中完成才能识别渲染方法。Griddler建议您创建一个EmailProcessor模型并使用“处理”方法来处理电子邮件。据我了解，您不能在模型中使用渲染方法。因此，我使用类方法创建
1.深度优先搜索(DFS)深度优先遍历主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。例题P1605迷宫题目描述给定一个N×MN\timesMN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。第二行为四个正整数SX,S
我正在我的应用程序中实现一个简单的API来与Android应用程序通信。我主要尝试使用AbstractController::Metal来提高性能。我遇到的问题是渲染忽略了我传递的状态选项。非常简单的例子:classApi::V1::ApiController打电话curl-v-XGEThttp://app.dev:3000/api/v1/sessions.json我希望收到401，但我却收到200OK:>GET/api/v1/sessions.jsonHTTP/1.1>User-Agent:curl/7.30.0>Host:app.dev:3000>Accept:*/*>有什么想法吗
为学习贯彻党的二十大工作报告中关于加快发展数字经济、促进数字经济和实体经济深度融合的重要指示，不断推进数字化转型与金融科技创新，桂林银行联合全国大学生数学建模竞赛广西赛区组委会、广西应用数学中心（广西大学）共同主办2023年“桂林银行杯”数据建模大赛暨全国大学生数学建模竞赛广西赛区热身赛。本次大赛旨在向学科专业竞赛靠拢，鼓励大学生向创新型、应用型、复合型人才发展，更好地提升大学生的创新意识和金融科技能力，为数据分析与建模人才提供更广阔的发挥平台，为建设数字中国、数字广西提供新动能。赛道说明：赛道A：个人消费贷款申贷客户识别。此赛道面向本科及以下学历的高校在校生。赛道B：Z世代的信用卡消费行为分
最近收到好多学员的一些提问，零基础没经验，能不能转行到网络工程师？发展前景怎么样？薪资能有多少？应该有不少朋友都有这个疑问，那么，今天我尽量给大家做出一个详细的解答，希望能有所帮助。内容可能比较长，大家可以点赞收藏，再慢慢阅读。零基础没经验，能不能转行到网络工程师？想要快速学习并入门网工行业，最快速也是效率做高的方法就是考取行业的相关证书。就像其他行业一样，也有属于网工的认证。网络工程师这个行业，现在最具有含金量并被行业承认的两个认证：思科和华为。简单说一下两者的区别： 从含金量角度来看。两者的含金量其实差不多，HCIE是华为认证的最高等级证书，CCIE是思科认证的最高等级证书，两者在网
作为一个10年老运维，在开始这篇文章之前，先送给大家一句话：干啥不好，非要做运维，听人劝，吃饱饭，趁年轻，换行吧！好了，不开玩笑了，回到正文中来。当谈到运维职业发展情况时，很多人都会说运维做不长久，然后劝人做两年就赶快转研发吧！总之是全面唱衰运维！但作为一个老运维，我想说的是：运维转开发确实是一个不错的选择，但运维做不长久则完全是对运维的偏见了!很多人有运维做不长久的偏见的原因其实和运维职业的特性有关，运维有三个老生常谈的特点：打杂，背锅，睡的少！说运维打杂，是说运维工作比较宽泛，运维职业门槛不高，什么都得会一点。公司里但凡跟计算机有关的事，可能都会找到运维，这就导致了运维工作比较杂！至于背黑
智慧医院不良事件精细化管理平台——微信小程序总结一、实现的功能二、项目收获三、总结（经历分享）一、实现的功能到目前为止，微信小程序开发，到此就算是结束了，其中实现了不少功能，如下：1.1角色与权限（后端同学实现的，写这个方便介绍后面的功能）平台可以配置不同的用户角色并授予其不同的操作权限。每个用户在使用平台时都需要指定一个角色。1.2可视范围——根据角色绑定的权限菜单全体职工可以查看自己上报的事件（待审核、已通过、被驳回）。质控人员可以查看所有的事件（待审核、待评价、已通过、已驳回、已评价）。职能人员可以查看自己/自己部门负责的事件（待整改、待评价、已评价）。各科室医务人员可以查看本科室相关的
1．下列定义变量的语句中错误的是______。A、int_intB、doubleint_C、charForD、floatUS$答案：D知识点：常量、变量和标识符2．以下不合法的用户标识符是______。A、j2_KEYB、DoubleC、4dD、_8_答案：C知识点：常量、变量和标识符3．以下4组用户定义标识符中，全部合法的一组是______。A、_mainencludesinB、If-maxturboC、txtREAL3COMD、intk_2_001???答案：A知识点：常量、变量和标识符4．以下定义语句中正确的是______。A、chara='A'b='B';B、floata=b=10.0