算法竞赛补题解析：牌面得分与数字反转问题

1. 训练赛补题背景与赛况回顾作为大二寒假期间参加牛客寒假训练赛的选手我的水平在参赛选手中属于中上等。每场比赛后我都会把那些有能力解决但比赛时没能完成的题目进行补题。这次是第一场训练赛的补题记录我选择了B题和G题两道题目进行深入分析。比赛过程中我完成了6道题目最终排名在1500名左右这个成绩我已经比较满意了。不过通过赛后补题我发现这两道题目其实都在我的能力范围内没能当场解出来主要是因为长时间没有练习导致思维不够敏捷以及对题意理解出现偏差。2. B题解析牌面得分组合问题2.1 题目理解与赛时误区B题的题目描述大致是这样的有两个数组a和b每个数组包含n个数字。我们需要将a数组的数字与b数组的数字进行某种配对配对规则是如果a[i] b[j]则得1分如果a[i] b[j]则不得分。关键在于一张b数组的牌如果没有被任何a数组的牌击败它会一直保留在牌堆中。我的第一个误区是误以为每张牌只能使用一次。实际上题目并没有这个限制一张b数组的牌如果没有被击败可以参与后续的配对。这个理解错误导致我在比赛时越想越复杂最终没能解出这道题。2.2 正确解题思路正确的解法其实非常简洁首先将a数组从大到小排序找出b数组中的最小值minb统计a数组中大于minb的数字数量numd和小于等于minb的数字数量numx最终结果就是numd! × numx!即两部分数字排列组合数的乘积这个解法的核心观察点是只要a数组中有一个数字大于minb那么这个数字一定能得到1分因为它可以击败minb。而小于等于minb的数字无论如何排列都不会影响得分因为它们无法击败任何b数组的牌minb是最小的。2.3 关键点与注意事项取模运算由于结果可能很大需要在计算阶乘的过程中不断取模题目给定的模数是998244353排列顺序虽然内部可以任意排列但必须保证所有大于minb的数字都排在小于等于minb的数字前面这样才能确保minb不会被浪费时间复杂度这个解法的时间复杂度是O(n)完全可以处理题目给定的数据范围注意在实际编码时要特别注意数据类型的选用。由于n可能很大阶乘结果会快速膨胀所以要使用long long类型来避免溢出。2.4 代码实现解析#includebits/stdc.h using namespace std; typedef long long ll; const int MOD998244353; void solve() { ll n; cinn; vectorlla(n); vectorllb(n); for(auto t:a) cint; for(auto t:b) cint; auto tempmin_element(b.begin(),b.end()); ll minb*temp; ll numd0,numx0; for(auto t:a) { if(tminb) numd; else numx; } ll ans1; for(int i1;inumd;i) { ans(ans*i)%MOD; } for(int i1;inumx;i) { ans(ans*i)%MOD; } coutansendl; }这段代码清晰地实现了上述思路。首先读取输入数据然后找到b数组的最小值minb接着统计a数组中大于和小于等于minb的数字数量最后计算两个阶乘的乘积并输出。3. G题解析最大折叠数问题3.1 题目理解与赛时困惑G题的题目要求是给定两个数字L和R我们需要找到一个数字X满足L ≤ X ≤ R且X的反转数即数字倒过来读是所有满足条件的数字中最大的。我在比赛时的思路过于复杂试图将各种情况分类处理导致逻辑混乱最终只通过了30%的测试用例。实际上这个问题有更简洁的解法。3.2 正确解题思路正确的解法可以总结为以下几个步骤特殊情况处理如果R是形如100...000的数字即首位是1后面全是0那么如果L和R位数不同最优解是R-1即99...999如果L和R位数相同最优解只能是1因为X必须等于R一般情况处理如果L和R位数不同将L视为与R同位数的最小数字即100...001从高位到低位比较L和R的每一位数字找到第一个R[i] L[i]的位置i如果i后面的数字不全是9则将R[i]减1后面所有位设为9反转最终得到的数字并去除前导零3.3 关键点与注意事项数字反转题目要求的是反转后的数字最大而不是数字本身最大前导零处理反转后的数字要去除前导零这是容易被忽略的细节边界情况特别是当R是10的幂次方时需要特殊处理位数差异当L和R位数不同时可以简化为只考虑R的情况提示在处理这类数字问题时将数字转换为字符串处理通常会更方便可以轻松访问每一位数字。3.4 代码实现解析#includebits/stdc.h using namespace std; typedef long long ll; void solve() { ll l,r; cinlr; string Lto_string(l); string Rto_string(r); ll numlL.size(); ll numrR.size(); // 处理特殊情况R是100...000 if(R[0]1) { bool all_zero true; for(int i1;iR.size();i) { if(R[i]!0) all_zerofalse; } if(all_zero) { if(numlnumr) { coutr-1endl; return; } if(numlnumr) { cout1endl; return; } } } // 处理位数不同的情况 if(numlnumr) { L string(numr-1,0); L 1 L; } // 寻找第一个不同的位置 for(int i0;inumr;i) { if(R[i]!L[i]) { bool all_nine true; for(int ji1;jnumr;j) { if(R[j]!9) all_ninefalse; } if(all_nine) { reverse(R.begin(),R.end()); coutRendl; return; } else { for(int ji1;jnumr;j) { R[j]9; } R[i]--; reverse(R.begin(),R.end()); // 去除前导零 int start0; while(startR.size() R[start]0) start; if(startR.size()) cout0; else { for(int jstart;jR.size();j) coutR[j]; } coutendl; return; } } } // 如果L和R完全相同直接反转 reverse(R.begin(),R.end()); // 去除前导零 int start0; while(startR.size() R[start]0) start; if(startR.size()) cout0; else { for(int jstart;jR.size();j) coutR[j]; } coutendl; }这段代码完整实现了上述思路。它首先处理特殊情况然后处理一般情况最后对结果进行反转和去除前导零的操作。代码结构清晰逻辑严谨。4. 比赛经验与反思4.1 题意理解的重要性这两道题目给我的最大教训就是仔细阅读题目。在B题中我因为对题目规则的理解错误导致完全走偏在G题中我因为没有准确把握反转数这个核心概念而陷入复杂的分类讨论。在实际比赛中建议至少阅读题目两遍用自己的话复述题目要求用简单例子验证自己的理解特别注意题目中的限制条件和特殊说明4.2 思维方式的优化在解决G题时我的思路过于碎片化试图为每一种可能的情况编写特殊处理逻辑。这种分情况讨论的方法虽然有时有效但往往会导致代码复杂且容易出错。更好的方法是寻找问题的本质和规律尝试用统一的逻辑处理大多数情况只对真正特殊的边界情况进行单独处理在编码前先用几个测试用例验证思路的正确性4.3 编码实践建议变量命名使用有意义的变量名如numd表示大于minb的数量numx表示小于等于的数量模块化将不同功能的代码分离如将特殊情况的判断单独处理注释对关键步骤添加简要说明方便后期review测试编写代码时同步考虑测试用例特别是边界情况5. 算法竞赛训练建议5.1 日常训练方法定期练习保持每周至少10小时的专注练习时间分类突破针对薄弱环节如贪心、动态规划进行专项训练赛后复盘每场比赛后分析所有错题和未完成的题目代码重构对于AC的题目尝试用不同的方法重新实现5.2 比赛策略题目选择先快速浏览所有题目从简单题开始时间分配设定每道题的时间上限超时就暂时跳过调试技巧学会使用print调试和assert验证中间结果心态管理保持冷静不要因为一道题卡住而影响整体发挥5.3 资源推荐在线判题系统牛客网、Codeforces、AtCoder、LeetCode学习平台OI Wiki、CP-Algorithms、GeeksforGeeks书籍推荐《算法竞赛入门经典》、《挑战程序设计竞赛》社区交流加入算法竞赛相关的QQ群、Discord群组通过这次训练赛的补题过程我深刻认识到自己在思维全面性和代码实现能力上的不足。这两道题目虽然现在看起来解法很清晰但在比赛的高压环境下要保持清晰的思路并不容易。这需要更多的练习和经验积累。在接下来的训练中我会更加注重对题目本质的理解和简洁高效解法的探索。