近5年NOIP试题解析：表达式求值与算法应用

"本文主要分析了近五年的NOIP（全国青少年信息学奥林匹克联赛）普及组的试题，涉及表达式求值、数字统计、接水问题和导弹拦截等多个编程题目。" 1. **表达式求值** 这个问题是NOIP2013年的题目，目标是编写程序计算只包含加法和乘法的算术表达式的值。输入的表达式只含有0~9的数字、加号"+"和乘号"*"，且没有括号。所有数字都在0到2^31-1之间。程序应确保处理的数据合法，并在输出时遵循特定格式：当答案超过四位时，仅输出最后四位，且不输出前导零。 解决此类问题通常采用**中缀表达式转后缀表达式（逆波兰表示法）**的方法，再通过**堆栈**来求解。首先，遍历输入的中缀表达式，遇到数字则入栈，遇到运算符则比较栈顶两个元素的优先级，如果当前运算符优先级更高则入栈，否则弹出栈顶元素进行运算并将结果入栈。最后，栈内剩余的单个元素即为表达式的结果。 2. **数字统计** NOIP2010年的数字统计题要求统计给定范围内所有整数中数字2出现的次数。可以实现一个函数，对每个数进行分离数字，每遇到数字2就累加计数。例如，对于整数n，可以通过不断地除以10并取余来分离数字，每一步检查余数是否为2。 ```cpp void count(int n) { int ans = 0; while (n > 0) { if (n % 10 == 2) ans++; n /= 10; } } ``` 3. **接水问题** 这个问题要求模拟一个有多个水龙头的场景，同学们按照一定的顺序接水，当一个同学接满水后，下一个同学立即接替。关键在于理解当有人完成接水时，其他同学不会停止，而是无缝过渡到下一个。可以使用数组记录每个同学的接水量和当前正在接水的人，然后用贪心策略每次选择当前未完成接水且时间最短的同学进行操作。 4. **导弹拦截** 最后是导弹拦截问题，需要确定两套导弹拦截系统的工作半径以拦截所有导弹，同时使代价（所有半径的平方和）最小。这个问题可能涉及到**动态规划**或**二分搜索**来确定最优工作半径，需要考虑系统的限制和导弹的分布情况。 以上四道题目都是NOIP普及组的典型编程题目，涵盖了基础的算法和数据结构，如中缀转后缀、堆栈应用、循环和条件判断以及优化策略等，对于参赛者来说是很好的训练材料。