NOIP2004普及组复赛试题1

【不高兴的津津】 此题属于信息学竞赛中的基础算法题，主要考察学生对数据处理和简单逻辑判断的能力。题目描述津津的日程安排，如果每天上课时间超过8小时，津津就会不高兴。任务是检查津津一周的日程，判断她是否会不高兴，以及哪一天最不高兴。 输入文件unhappy.in包含津津一周每天的上课时间，共7行，每行2个非负整数。程序需要读取这些数据，计算每天的总上课时间，如果超过8小时，则标记该天为不高兴。然后找出最不高兴的一天，输出对应的一天编号（周一为1，周日为7）。 解题策略可以是遍历一周的每一天，累加津津的上课时间，同时记录下最不高兴的日期。如果遇到上课时间超过8小时的天数，更新最不高兴的日期。最后输出这个日期。 【花生采摘】 这道题是路径规划和优化问题，涉及到动态规划和贪心策略。题目设定一只猴子多多在花生田里采摘花生，目标是在限定时间内采摘最多的花生。田地被表示为矩形网格，猴子可以从一株花生跳到相邻的花生，或者返回路边。 输入文件peanuts.in包含花生田的尺寸MxN以及限定时间K，以及每株花生的数量。程序需要找到最优路径，使得在限定时间内采摘的花生数量最多。 解题的关键在于设计一个算法来确定猴子的采摘顺序。可以采用贪心策略，每次选择当前剩余花生最多的植株进行采摘，同时考虑猴子移动的效率。需要注意的是，猴子只能在限定时间内行动，因此需要计算每一步操作的时间消耗。 【FBI树】 FBI树是一种特殊的二叉树，根据给定的全0、全1或混合的"01"串来构建。题目要求根据给定的长度为2N的"01"串，按照FBI树的构造规则构建树，并输出其后序遍历序列。 输入文件fbi.in提供了一个整数N，代表字符串的长度。构建FBI树的过程是递归的，需要将字符串分为两半，分别构建左子树和右子树，直到字符串长度为1。输出后序遍历序列，即先遍历左子树，再遍历右子树，最后访问根节点。 解题时，可以使用递归函数来构建树，每次将字符串均分为两部分，构建子树，最后输出后序遍历结果。对于输出，可以使用栈来辅助实现后序遍历的顺序。 这三道题涵盖了信息学竞赛中常见的数据结构和算法，包括基本的数据处理、路径规划优化以及树的构造与遍历，对于提高学生的编程能力和问题解决能力有着很好的锻炼作用。