NOIP2009复赛试题详解：多项式输出等四题

"09年NOIP复赛试题包含四道题目，分别为多项式输出、分数线划定、细胞分裂和道路游戏，分别用英文表示为poly、score、cell和game。每道题都有对应的输入和输出文件，时限为1秒，且有多个测试点。题目类型均为传统，需要使用Pascal、C或C++编写程序。提交的源程序文件名根据语言不同，例如Pascal的文件后缀为pas，C的为c，C++的为cpp。编译命令中使用了fpc、gcc和g++，并链接了lm库。运行内存限制为128MB。参赛者需要注意文件名全为小写，C/C++的main()函数返回值类型应为int，正常结束时返回0。评测时的机器配置为CPU1.9GHz，内存1GB，各省自测时可按实际配置调整时限。" 这些题目是针对全国信息学奥林匹克联赛（NOIP）2009年提高组复赛的，比赛旨在检验参赛者的编程能力和算法理解。以下是这四道题目的基本介绍： 1. **多项式输出**（poly）：可能需要参赛者处理数学上的多项式运算，如加减乘除，或者要求将多项式以特定格式输出。可能涉及到的数据结构有链表或数组，用于存储多项式的系数。 2. **分数线划定**（score）：题目可能涉及到分数计算或排序，参赛者可能需要设计算法来确定分数线，这可能涉及到统计分析和数据处理。 3. **细胞分裂**（cell）：此题目可能与生物或模拟相关，参赛者可能需要编写程序模拟细胞分裂的过程，包括时间步进和状态更新。这可能需要理解和使用递归或动态规划等复杂算法。 4. **道路游戏**（game）：这是一道涉及游戏规则的题目，可能需要参赛者编写一个解决特定游戏策略的程序。可能涉及到图论、搜索算法（如深度优先搜索或广度优先搜索）以及博弈论概念。 每道题目的测试点数和分值不同，例如“多项式输出”和“分数线划定”各有10个测试点，每个点10分；“细胞分裂”同样有10个测试点，但每个点10分；而“道路游戏”则有20个测试点，每个点5分。这意味着参赛者不仅需要保证代码正确性，还需要考虑效率，以在限定的1秒内完成每个测试点。 在编程时，参赛者必须按照指定的文件格式输入和输出数据，并确保程序在128MB内存限制下运行。使用Pascal、C或C++编程时，编译器分别为Free Pascal Compiler (fpc)、GCC (with math library) 和GNU C++编译器，且需要遵循特定的编译命令。 最后，为了确保程序能在全国统一评测中顺利运行，参赛者必须注意代码的通用性和规范性，如文件名全小写，C/C++程序的main()函数返回值必须是int类型，正常结束时返回0。此外，各地在自行测试时可根据本地硬件配置适当调整时限。