【蓝桥杯】十四招式冲刺之 “第七招”《打表法与模拟法》

招式冲刺之 “第七招”《打表法与模拟法》"/>

【蓝桥杯】十四招式冲刺之 “第七招”《打表法与模拟法》

前言

-🏀大家好，我是BXuan，热爱编程与篮球的软件工程大二学生一名
-📚近期在准备4月份的蓝桥省赛，本章与大家一起聊聊有关打表法与模拟法(优化的暴力法)！
-🏃‍放弃不难，但坚持一定很酷。

---

文章目录

• 🚀打表法与模拟法
• 📚知识点
• 😁真题模拟
• • 1️⃣算式问题
  • 2️⃣求值
  • 3️⃣既约分数
  • 4️⃣天干地支
• 👏小结

🚀打表法与模拟法

📚知识点

• 打表法的使用与简单举例
• 模拟法的使用与简单举例

😁真题模拟

1️⃣算式问题

这是 2012 年蓝桥杯国赛 的一道问题。

题目描述：
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
看这个算式：
☆☆☆ + ☆☆☆ = ☆☆☆
如果每个五角星代表 1 ~ 9 的不同的数字。这个算式有多少种可能的正确填写方法？
173 + 286 = 459
295 + 173 = 468
173 + 295 = 468
183 + 492 = 675
以上都是正确的填写法！

注意：111+222=333 是错误的填写法！因为每个数字必须是不同的！也就是说：1 ~ 9 中的所有数字，每个必须出现且仅出现一次！
注意：不包括数字 “0”。
注意：满足加法交换率的式子算两种不同的答案。 所以答案肯定是个偶数！

运行限制：

1. 最大运行时间：1s
2. 最大运行内存: 128M

java实现

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;public class Main {static int check(int a, int b, int c){int flag[]=new int[11];for(int i=0;i<10;i++) flag[i]=0;flag[0]=1;while(a!=0){if(flag[a%10]==1) return 0;else flag[a%10]=1;if(flag[b%10]==1) return 0;else flag[b%10]=1  ;if(flag[c%10]==1) return 0;else flag[c%10]=1  ;a=a/10;b=b/10;c=c/10;}return 1;}public static void main(String[] args) {int ans=0;for(int a=123;a<=987;a++)for(int b=123;b<=987-a;b++){int c=a+b;if(check(a,b,c)==1){ans++;System.out.println(a+"+"+b+"="+c);}}System.out.println(ans);}
}

2️⃣求值

这是 蓝桥杯 2019 国赛 的一道题目。

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为 St​。

例如 S1=1,S2=2,S3=4,S4=6，⋅⋅⋅

现在小明想知道，当 t=100 时，S1​00 是多少？

运行限制：

1. 最大运行时间：1s
2. 最大运行内存：128M

题目分析
这道题乍一看，是一道数论题目，实际上他确实一道数论题目，但是由于是道填空题，所以我们采用模拟法打表做。
题目中的描述是找约数，那我们定义个找约束个数的函数，然后枚举即可。
这样不考虑时间复杂度，我们采取暴力法，尽快完成题目，让程序去跑答案，节省下时间来去做其他的题目。

java实现

package company;public class Main {static int cnt(int a){int ans = 0;for (int j = 1; j <= a; j++)if (a % j == 0)ans++;return ans;}public static void main(String[] args) {for(int i=1;true;i++){System.out.println(cnt(i)+" "+i);if(cnt(i)==100) break;}}
}

提交代码

package company;public class Main {public static void main(String[] args) {System.out.println(45360);}}

3️⃣既约分数

这是 2020 年省赛 的一个题目。
题目描述：

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如3/4,1/8,7/1都是即约分数

请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？
运行限制

1. 最大运行时间：1s
2. 最大运行内存：128M

题目解析
我们看到这种题，现在一眼就知道只是到纯暴力的题目，即暴力枚举然后依据题目要求模拟即可。
但是这种简单题在比赛中是来送分的，我们要花很少的时间做完，才有时间做其他的题目，这就要求我们对这种题目的熟练度极高，要做到，看到题目，想到思路手里能直接写出来才可以。
这里有一个巧妙的方法是因为分子与分母是对称的我们可以少枚举一半，不过有些同学可能没想明白，没关系，我们用普通的办法，只要能够快速的编程并找到答案，思路正确性能够保证的话，其他的都是可有可无的。
这题目我们首先要两个数是否互质，即最小公约数为 1，我们就定义一个 GCD() 求最小公约数的算法，这里我们采用的是递归的方法。

java实现

public class Main {static int gcd(int a, int b){int temp;while(b>0){/*利用辗除法，直到b为0为止*/temp = b;b = a % b;a = temp;}return a;}public static void main(String[] args) {int ans=0;for(int a=1;a<=2020;a++){for( int b=1;b<=2020;b++){if(gcd(a,b)==1) ans++;}}System.out.println(ans);}
}

4️⃣天干地支

这个题目是 2020 国赛的模拟题。
题目描述：
古代中国使用天干地支来记录当前的年份。
天干一共有十个，分别为：甲（jiǎ）、乙（yǐ）、丙（bǐng）、丁（dīng）、戊（wù）、己（jǐ）、庚（gēng）、辛（xīn）、壬（rén）、癸（guǐ）。

地支一共有十二个，分别为：子（zǐ）、丑（chǒu）、寅（yín）、卯（mǎo）、辰（chén）、巳（sì）、午（wǔ）、未（wèi）、申（shēn）、酉（yǒu）、戌（xū）、 亥（hài）。

将天干和地支连起来，就组成了一个天干地支的年份，例如：甲子。
2020 年是庚子年。
每过一年，天干和地支都会移动到下一个。例如 2021 年是辛丑年。
每过 60 年，天干会循环 6 轮，地支会循环 5 轮，所以天干地支纪年每 60 年轮回一次。例如 1900 年，1960 年，2020 年都是庚子年。
给定一个公元纪年的年份，请输出这一年的天干地支年份。

输入描述：

输入一行包含一个正整数，表示公元年份。

其中有 ，输入的公元年份为不超过 9999 的正整数。

输出描述：

输入一行包含一个正整数，表示公元年份。

输入输出样例：

输入
2020

输出
gengzi

运行限制

1. 最大运行时间：1s
2. 最大运行内存: 128M
   java实现

import java.util.Scanner;public class Main {static String []tg = new String []{"geng", "xin", "ren", "gui", "jia", "yi" , "bing", "ding", "wu", "ji"};static String dz[] = new String []{ "shen", "you", "xu", "hai", "zi", "chou", "yin", "mou", "chen", "si", "wu", "wei"};public static void main(String[] args){int year;Scanner in =new Scanner(System.in);year = in.nextInt();System.out.println(tg[year%10]+""+dz[year%12]);}
}

👏小结

对于这种简单的模拟题，不需要借助算法，只要暴力的题目，我们都可以打表模拟，然后提交答案。