结合26年3月GESP七级第二题以及2024年CSP-J第三题讲解下考试技巧之一打表找规律首先来看2024年CSP-J第三题数据范围和测试点性质首先拿道题之后要去看数据范围这个题的数据范围指向非常明显。我们可以尝试找找n是7的倍数时候的规律。不难发现8这个数字需要的木棍数量是7可以猜测为了使数字最小我们应该尽量拼8。但除此之外还有什么规律呢我们可以尝试暴力打表找找每个数字需要的木棍数然后记录下来相同的木棍数下最少的数字是多少。暴力代码如下#includebits/stdc.h using namespace std; ​ // mp[s] 表示使用 s 根火柴棒能组成的最小正整数 mapint,int mp; ​ int main(){ // a[i] 表示数字 i 需要多少根火柴棒 (0-9) // 对应数字: 0 1 2 3 4 5 6 7 8 9 // 火柴棒数: 6 2 5 5 4 5 6 3 7 6 int a[10] {6,2,5,5,4,5,6,3,7,6}; // 枚举所有可能的正整数 (1 到 10^7) for(int i 1; i 10000000; i){ int t i, s 0; // 计算数字 i 的每一位所需火柴棒之和 while(t){ s s a[t % 10]; // 加上当前位数字的火柴棒数 t t / 10; // 去掉最后一位 } ​ // 如果 s 根火柴棒还没有对应数字或者 i 更小则更新 if(mp[s] 0){ mp[s] i; // 首次记录使用 s 根火柴棒的最小数字 }else{ mp[s] min(mp[s], i); // 保持最小的那个数字 } } // 输出使用 1~50 根火柴棒分别能组成的最小正整数 for(int i 1; i 50; i){ cout i mp[i] endl; } return 0; }输出如图所示我们可以观察输出的结果发现好多规律首先规律和7的余数有关20以内规律不明显可以直接暴力枚举。到这里这个题就写出来了。考试时候我们可以先写一个程序尝试找找规律不一定要手算。26年三月七级第一题也是类似思路这个题很多同学第一反应也是要写dp但仔细读题会发现不可能。输出格式里说都很清楚我们要找拆分后正整数之积的最大值取模之后的结果。如果我们在dp的过程中一边取模一边求max这样答案大概率是错误的。所以提示我们一定要先想明白怎么拆分才是最优的。很多学过奥数的小朋友都知道应该拆成3但很多孩子不知道或者忘了怎么办我们可以写一个暴力的程序看看。比如下面的程序#includebits/stdc.h using namespace std; ​ int ans; // 存储当前最大乘积结果 int vis[50]; // 标记数组注此代码中未实际使用 vectorint t; // 存储最优拆分方案最终的数字组合 ​ // 深度优先搜索函数 // x: 当前剩余待拆分的数值 // cnt: 当前已累积的乘积 // w: 当前拆分路径已选择的数字列表 void dfs(int x, int cnt, vectorint w) { // 当剩余值为0时说明拆分完成 if(x 0) { // 如果当前乘积大于历史最大值更新最优解 if(ans cnt) { ans cnt; // 更新最大乘积 t w; // 保存当前最优拆分方案 } return; } // 枚举所有可能的拆分从1到x尝试将i作为当前拆分的数字 for(int i 1; i x; i) { w.push_back(i); // 将i加入当前路径 dfs(x - i, cnt * i, w); // 递归剩余值减i乘积乘i w.pop_back(); // 回溯撤销选择尝试下一个i } return; } ​ int main() { // 遍历1到25的所有整数求解每个数拆分成若干正整数之和的最大乘积 for(int i 1; i 25; i) { ans 0; // 重置最大乘积 vectorint w; // 初始化空路径 dfs(i, 1, w); // 对数字i进行深度优先搜索初始乘积为1 // 输出结果最大乘积 和 对应的拆分方案 cout i ans ; // 输出最大乘积 for(auto p: t) { cout p ; // 输出最优拆分方案中的每个数字 } cout endl; } return 0; }输出结果考试时候这个技巧是为了帮助咱们找到解题的突破口如果能根据这个输出理解整个题目也知道规律的原因最后AC是最好的。但如果不太理解起码先把这个题解决掉。独自尝试环节:P9635 「yyOI R1」youyou 的异或 - 洛谷