![题解：洛谷 P1211 [USACO1.3] 牛式 Prime Cryptarithm](http://pic.xiahunao.cn/yaotu/题解：洛谷 P1211 [USACO1.3] 牛式 Prime Cryptarithm)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1211 [USACO1.3] 牛式 Prime Cryptarithm - 洛谷【题目描述】下面是一个乘法竖式如果用我们给定的那n个数字来取代*可以使式子成立的话我们就叫这个式子为牛式。*** x ** ---------- *** *** ---------- ****数字只能取代*当然第一位不能为 0况且给定的数字里不包括 0。注意一下在美国的学校中教的“部分乘积”第一部分乘积是第二个数的个位和第一个数的积第二部分乘积是第二个数的十位和第一个数的乘积。请计算出牛式的数量。【输入】第一行一个正整数n表示可用的数集。第二行n个正整数ai表示可用的数。【输出】输出一行一个整数表示牛式的总数。【输入样例】5 2 3 4 6 8【输出样例】1【核心思想】问题分析给定n nn个可用数字不含 0要求找出满足特定乘法竖式的牛式数量。竖式形式为一个三位数乘以一个两位数得到两个部分积均为三位数和一个最终积四位数且所有出现的数字都必须在给定的数集中。这是一个枚举 数位验证问题。算法选择暴力枚举枚举所有可能的三位数i ∈ [ 111 , 999 ] i \in [111, 999]i∈[111,999]和两位数j ∈ [ 11 , 99 ] j \in [11, 99]j∈[11,99]数位拆分验证将数字逐位拆分检查每一位是否都在给定的可用数字集合中桶标记快速判断用布尔数组a [ d ] a[d]a[d]标记数字d dd是否可用实现O ( 1 ) O(1)O(1)数位查询关键步骤读入与标记读入n nn个可用数字用桶数组a [ d ] 1 a[d] 1a[d]1标记定义验证函数check(x, k)若x ≥ 10 k x \geq 10^kx≥10k返回false保证位数恰好为k kk位逐位拆分x xx若某位数字d dd满足a [ d ] 0 a[d] 0a[d]0则返回false全部通过返回true双重枚举外层i ii从111 111111到999 999999被乘数三位数内层j jj从11 1111到99 9999乘数两位数验证五个条件check(i, 3)被乘数是三位数且各位可用check(j, 2)乘数是两位数且各位可用check(i * (j % 10), 3)第一部分积个位相乘是三位数且各位可用check(i * (j / 10), 3)第二部分积十位相乘是三位数且各位可用check(i * j, 4)最终积是四位数且各位可用全部满足则ans输出结果牛式总数a n s ansans时间/空间复杂度时间复杂度O ( 900 × 90 × log 10 ( max ) ) ≈ O ( 10 5 ) O(900 \times 90 \times \log_{10}(\text{max})) \approx O(10^5)O(900×90×log10(max))≈O(105)枚举量小数位验证为常数级空间复杂度O ( 1 ) O(1)O(1)仅需桶数组和少量变量枚举验证的核心思想竖式约束转化将乘法竖式的位数要求转化为五个独立的数位验证条件桶数组加速用a [ d ] a[d]a[d]标记可用数字避免每次线性查找实现O ( 1 ) O(1)O(1)判断位数精确控制check(x, k)中先判断x 10 k x 10^kx10k确保不超出k kk位再通过循环拆分确保不短于k kk位因不含 0不会出现前导零问题范围剪枝i ii从111 111111开始而非100 100100j jj从11 1111开始而非10 1010因可用数字不含 0自然排除含 0 的数适用于数字谜题、竖式还原、数位约束枚举等问题【解题思路】【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;intn,t,ans0;inta[15];boolcheck(intx,intk)// 定义判断数位的函数{if(xpow(10,k))returnfalse;// 如果这个数x大于等于10^k则返回falsewhile(x0){// 使用数位拆分if(a[x%10]0)returnfalse;// 依次判断每个数都在n个数字中如果不在的话直接返回falsexx/10;// 数位拆分}returntrue;// 如果没有不满足的话那就返回true}intmain(){cinn;// 输入nfor(inti1;in;i){// 遍历n个数cint;// 输入每个数a[t]1;// 并使用桶排序方法存到桶中后面需要判断该数字是否有}for(inti111;i999;i){// 遍历所有的三位数for(intj11;j99;j){// 遍历所有的二位数if(check(i,3)check(j,2)check(i*(j%10),3)check(i*(j/10),3)check(i*j,4)){// 根据题目要求判断两个数是否为一个为3位数一个为2位数3位数乘上2个位的个位和十位都是3位数以及3位数乘2位数为4位数ans;// 统计结果自增1只有222*22满足此要求}}}coutansendl;return0;}【运行结果】5 2 3 4 6 8 1
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1211 [USACO1.3] 牛式 Prime Cryptarithm - 洛谷【题目描述】下面是一个乘法竖式如果用我们给定的那n个数字来取代*可以使式子成立的话我们就叫这个式子为牛式。*** x ** ---------- *** *** ---------- ****数字只能取代*当然第一位不能为 0况且给定的数字里不包括 0。注意一下在美国的学校中教的“部分乘积”第一部分乘积是第二个数的个位和第一个数的积第二部分乘积是第二个数的十位和第一个数的乘积。请计算出牛式的数量。【输入】第一行一个正整数n表示可用的数集。第二行n个正整数ai表示可用的数。【输出】输出一行一个整数表示牛式的总数。【输入样例】5 2 3 4 6 8【输出样例】1【核心思想】问题分析给定n nn个可用数字不含 0要求找出满足特定乘法竖式的牛式数量。竖式形式为一个三位数乘以一个两位数得到两个部分积均为三位数和一个最终积四位数且所有出现的数字都必须在给定的数集中。这是一个枚举 数位验证问题。算法选择暴力枚举枚举所有可能的三位数i ∈ [ 111 , 999 ] i \in [111, 999]i∈[111,999]和两位数j ∈ [ 11 , 99 ] j \in [11, 99]j∈[11,99]数位拆分验证将数字逐位拆分检查每一位是否都在给定的可用数字集合中桶标记快速判断用布尔数组a [ d ] a[d]a[d]标记数字d dd是否可用实现O ( 1 ) O(1)O(1)数位查询关键步骤读入与标记读入n nn个可用数字用桶数组a [ d ] 1 a[d] 1a[d]1标记定义验证函数check(x, k)若x ≥ 10 k x \geq 10^kx≥10k返回false保证位数恰好为k kk位逐位拆分x xx若某位数字d dd满足a [ d ] 0 a[d] 0a[d]0则返回false全部通过返回true双重枚举外层i ii从111 111111到999 999999被乘数三位数内层j jj从11 1111到99 9999乘数两位数验证五个条件check(i, 3)被乘数是三位数且各位可用check(j, 2)乘数是两位数且各位可用check(i * (j % 10), 3)第一部分积个位相乘是三位数且各位可用check(i * (j / 10), 3)第二部分积十位相乘是三位数且各位可用check(i * j, 4)最终积是四位数且各位可用全部满足则ans输出结果牛式总数a n s ansans时间/空间复杂度时间复杂度O ( 900 × 90 × log 10 ( max ) ) ≈ O ( 10 5 ) O(900 \times 90 \times \log_{10}(\text{max})) \approx O(10^5)O(900×90×log10(max))≈O(105)枚举量小数位验证为常数级空间复杂度O ( 1 ) O(1)O(1)仅需桶数组和少量变量枚举验证的核心思想竖式约束转化将乘法竖式的位数要求转化为五个独立的数位验证条件桶数组加速用a [ d ] a[d]a[d]标记可用数字避免每次线性查找实现O ( 1 ) O(1)O(1)判断位数精确控制check(x, k)中先判断x 10 k x 10^kx10k确保不超出k kk位再通过循环拆分确保不短于k kk位因不含 0不会出现前导零问题范围剪枝i ii从111 111111开始而非100 100100j jj从11 1111开始而非10 1010因可用数字不含 0自然排除含 0 的数适用于数字谜题、竖式还原、数位约束枚举等问题【解题思路】【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;intn,t,ans0;inta[15];boolcheck(intx,intk)// 定义判断数位的函数{if(xpow(10,k))returnfalse;// 如果这个数x大于等于10^k则返回falsewhile(x0){// 使用数位拆分if(a[x%10]0)returnfalse;// 依次判断每个数都在n个数字中如果不在的话直接返回falsexx/10;// 数位拆分}returntrue;// 如果没有不满足的话那就返回true}intmain(){cinn;// 输入nfor(inti1;in;i){// 遍历n个数cint;// 输入每个数a[t]1;// 并使用桶排序方法存到桶中后面需要判断该数字是否有}for(inti111;i999;i){// 遍历所有的三位数for(intj11;j99;j){// 遍历所有的二位数if(check(i,3)check(j,2)check(i*(j%10),3)check(i*(j/10),3)check(i*j,4)){// 根据题目要求判断两个数是否为一个为3位数一个为2位数3位数乘上2个位的个位和十位都是3位数以及3位数乘2位数为4位数ans;// 统计结果自增1只有222*22满足此要求}}}coutansendl;return0;}【运行结果】5 2 3 4 6 8 1
![题解：洛谷 P1218 [USACO1.5] 特殊的质数肋骨 Superprime Rib](http://pic.xiahunao.cn/yaotu/题解：洛谷 P1218 [USACO1.5] 特殊的质数肋骨 Superprime Rib)
