下载文档原格式
noip初三试题及答案一、选择题（每题2分，共10分）1. 在计算机编程中，以下哪个选项不是数据结构的类型？A. 线性表B. 树C. 图D. 函数答案：D2. 以下哪种排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 插入排序D. 选择排序答案：C3. 在C++编程语言中，以下哪个关键字用于定义类？A. structB. classC. unionD. enum答案：B4. 在数据库管理系统中，以下哪个操作用于从表中删除数据？A. SELECTB. INSERTC. UPDATED. DELETE答案：D5. 以下哪种网络协议用于在互联网上传输数据？A. HTTPB. FTPC. TCPD. SMTP答案：C二、填空题（每题3分，共15分）1. 在计算机科学中，_________算法是一种用于解决最优化问题的算法，它通过不断迭代逼近最优解。
答案：梯度下降2. 在HTML中，用于定义网页头部的标签是_________。
答案：<head>3. 在Python中，_________函数用于计算列表中所有元素的和。
答案：sum4. 在关系型数据库中，_________是一种用于存储和管理数据的表格结构。
答案：表5. 在操作系统中，_________是指计算机系统在执行任务时，能够同时处理多个任务的能力。
答案：多任务三、简答题（每题5分，共20分）1. 请简述什么是递归，并给出一个递归函数的例子。
答案：递归是一种在函数中调用自身的编程技巧，它允许函数在解决更小规模的问题时重复调用自身。
例如，计算阶乘的递归函数可以表示为：```pythondef factorial(n):if n == 0:return 1else:return n * factorial(n - 1)```2. 描述什么是二叉树，并给出它的一个应用场景。
答案：二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
１.质因数分解描述已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。
格式输入格式输入只有一行包含一个正整数n。
输出格式输出只有一行包含一个正整数p, 即较大的那个质数。
样例1样例输入121样例输出17限制1S提示【数据范围】对于60%的数据，6 ≤n ≤1000。
对于100%的数据，6 ≤n ≤2*10的9次方问题分析：如果一个数n是两个素数的乘积，那么其中一个素数必然小于或等于n的开平方。
AC的C++程序如下：1.#include <iostream>2.#include <cmath>3.ing namespace std;5.6.int main()7.{8.long n;9.10. cin >> n;11.12.if(n % 2 == 0)13. cout << n / 2 << endl;14.else {15.int start = sqrt(n) / 2;16. start = start * 2 + 1;17.18.for(int i=start; i>=3; i-=2) {19.if(n % i == 0) {20. cout << n / i << endl;21. }22. }23. }24.25.return 0;26.}2.级数求和问题分析：简单的求和比较问题。
程序说明：需要注意类型。
描述已知：Sn= 1＋1／2＋1／3＋…＋1／n。
显然对于任意一个整数K，当n足够大的时候，Sn大于K。
现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。
格式输入格式输入k输出格式输出n样例1样例输入11样例输出12限制每个测试点1sAC的C++程序如下：1.#include <iostream>2.ing namespace std;4.5.int main()6.{7.int k;8.long n = 0;9.double sum = 0;10.11. cin >> k;12.while(sum <= k) {13. n++;14. sum += 1 / (double) n;15. }16.17. cout << n << endl;18.19.return 0;20.}3. 奖学金描述某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。
noip普及组初赛试题及答案一、选择题（每题5分，共50分）1. 在计算机科学中，以下哪个选项是数据结构中常用的数据类型？A. 整数B. 浮点数C. 字符串D. 所有选项答案：D2. 下列哪种排序算法的时间复杂度为O(nlogn)？A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C3. 在C++中，以下哪个关键字用于声明一个类？A. structB. classC. enumD. union答案：B4. 在计算机编程中，以下哪个选项是递归算法的典型应用？A. 计算阶乘B. 打印输出C. 循环遍历D. 数据输入答案：A5. 在数据库管理系统中，SQL语言用于执行哪种类型的操作？A. 存储数据B. 检索数据C. 修改数据D. 所有选项答案：D6. 在计算机科学中，算法的时间复杂度通常用来描述什么？A. 算法的运行时间B. 算法的执行步骤C. 算法的内存使用量D. 算法的效率答案：D7. 在编程语言中，以下哪个选项不是控制结构？A. 条件语句B. 循环语句C. 函数定义D. 异常处理答案：C8. 在操作系统中，进程和线程的主要区别是什么？A. 进程是资源分配的单位，线程是执行的单位B. 进程是执行的单位，线程是资源分配的单位C. 进程和线程没有区别D. 进程和线程是同一种概念答案：A9. 在计算机网络中，HTTP协议通常用于什么？A. 文件传输B. 电子邮件传输C. 网页浏览D. 远程登录答案：C10. 以下哪种数据结构最适合实现一个不重复元素集合？A. 数组B. 链表C. 栈D. 哈希表答案：D二、填空题（每题5分，共30分）1. 在C++中，用于定义常量的关键字是________。
答案：const2. 一个算法的空间复杂度是指算法在执行过程中所需的________。
答案：存储空间3. 在数据结构中，________是一种可以存储多个数据元素的线性结构。
答案：数组4. 在计算机程序设计中，________是一种将复杂问题分解为更小、更易于管理的部分的方法。
noip普及组复赛试题及答案一、选择题1. 在计算机科学中，以下哪个概念与数据结构最相关？A. 算法B. 操作系统C. 网络协议D. 编译原理答案：A2. 以下哪种排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序答案：D3. 在C++中，以下哪个关键字用于定义类？A. structB. unionC. enumD. typedef答案：A4. 以下哪个选项不是数据库管理系统（DBMS）的特性？A. 数据持久性B. 数据共享C. 数据加密D. 数据独立性答案：C5. 在计算机网络中，TCP和UDP协议分别属于哪一层？A. 传输层B. 应用层C. 网络层D. 物理层答案：A二、填空题1. 在计算机程序中，______ 用于定义数据的存储方式和组织形式。
答案：数据结构2. 一个算法的时间复杂度为O(1)，表示该算法的执行时间与输入数据的规模______。
答案：无关3. 在C++中，______ 是一种特殊的类，它提供了一种方式来定义数据类型。
答案：typedef4. 数据库管理系统（DBMS）通常包含数据定义语言（DDL）、数据操纵语言（DML）和______。
答案：数据控制语言（DCL）5. 在计算机网络中，______ 协议负责在网络层进行数据包的路由选择。
答案：IP三、简答题1. 请简述面向对象编程（OOP）的三个基本特征。
答案：封装、继承、多态2. 描述二分查找算法的基本步骤。
答案：二分查找算法的基本步骤包括：首先确定数组是有序的，然后取中间元素与目标值比较，如果中间元素等于目标值，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找，直到找到目标值或查找范围为空。
四、编程题1. 编写一个函数，实现对整数数组的排序。
答案：以下是一个简单的冒泡排序算法实现：```cppvoid bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);}}}}```2. 编写一个函数，实现计算一个整数的阶乘。
NOIP2008一、单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确答案）。
1．在以下各项中，（）不是操作系统软件。
A．Solaris B．Linux C．Sybase D．Windows Vista E．Symbian2．微型计算机中，控制器的基本功能是（）。
A．控制机器的各个部件协调工作B．实现算数运算与逻辑运算C．存储各种控制信息D．获取外部信息E．存放程序和数据3．设字符串S=“Olympic”，S的非空字串的数目是（）。
A．29 B．28 C．16 D．17 E．74．完全二叉树有2*N-1的结点，则它的叶子结点数目是（）。
A．N-1 B．2*N C．N D．2N-1 E．N/25．将数组{8，23，4，16，77，-5，53，100}中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换（）次。
A．4 B．5 C．6 D．7 E．86．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（）。
A．6 B．5 C．4 D．3 E．27．与十进制数28.5625相等的四进制数是（）A．123.21 B．131.22 C．130.22 D．130.21 E．130.208．递归过程和函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。
A．队列B．多维数组C．线性表D．链表E．栈9．TCP/IP 是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际互联协议（IP）。
TCP/IP协议把Internet网络系统描述成具有4个层次功能的网络模型，其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。
A．链路层B．网络层C．传输层D．应用层E．会话层10．对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率情况下，查找成功的平均查找长度（平均比较次数）是（）。
noip普及组初赛试题及答案一、选择题（每题5分，共50分）1. 在计算机系统中，CPU的中文意思是什么？A. 中央处理器B. 存储器C. 输入输出设备D. 操作系统答案：A2. 下列关于二进制数的描述，错误的是？A. 二进制数只有0和1两个数字B. 二进制数的每一位代表2的幂次C. 二进制数的运算规则与十进制数相同D. 二进制数可以表示计算机中的数据答案：C3. 在编程语言中，用于控制程序流程的语句是？A. 赋值语句B. 条件语句C. 循环语句D. 所有选项答案：D4. 下列哪种数据结构不属于线性数据结构？A. 数组B. 链表C. 树D. 图答案：D5. 在计算机程序中，用于存储临时数据的存储区域是？A. 硬盘B. 内存C. 缓存D. 寄存器答案：B6. 以下哪个算法的时间复杂度是O(n^2)？A. 快速排序B. 归并排序C. 插入排序D. 线性查找答案：C7. 在数据库中，用于存储数据的表之间的关系称为？A. 索引B. 视图C. 外键D. 触发器答案：C8. 下列关于递归函数的描述，正确的是？A. 递归函数不能包含循环B. 递归函数必须有终止条件C. 递归函数可以无限递归D. 递归函数可以没有递归调用答案：B9. 在操作系统中，用于管理内存的机制是？A. 文件系统B. 进程调度C. 内存管理D. 网络通信答案：C10. 在网络通信中，TCP协议的主要作用是？A. 传输文件B. 建立连接C. 错误检测D. 路由选择答案：B二、填空题（每题5分，共30分）1. 在计算机中，一个字节由____位二进制数组成。
答案：82. 一个完整的算法应该包含输入、____和输出三个基本部分。
答案：处理3. 在编程中，____是一种常用的数据结构，用于存储具有相同数据类型的元素集合。
答案：数组4. 在面向对象编程中，封装、继承和____是三个基本特征。
答案：多态5. 在关系型数据库中，____是一种特殊的表，用于定义表之间的关系。
noip普及组初赛试题及答案### NOIP 普及组初赛试题及答案#### 一、选择题（每题2分，共10分）1. 题目：计算机程序设计语言中，哪种语言是由Dennis Ritchie在1970年代初期开发的？- A. Java- B. C语言- C. Python- D. Ruby答案：B2. 题目：在计算机科学中，算法的时间复杂度是指什么？- A. 算法执行所需的内存大小- B. 算法执行所需的时间长短- C. 算法的可读性- D. 算法的可扩展性答案：B3. 题目：以下哪个是计算机网络中的数据交换技术？- A. TCP- B. UDP- C. FTP- D. HTTP答案：A4. 题目：在HTML中，用于定义文档类型声明的标签是哪一个？- A. `<!DOCTYPE>`- B. `<html>`- C. `<head>`- D. `<body>`答案：A5. 题目：以下哪个是操作系统的五大基本功能之一？- A. 邮件服务- B. 文件系统管理- C. 网络服务- D. 办公自动化答案：B#### 二、填空题（每空2分，共20分）1. 在C语言中，用于定义一个整型变量的关键字是 int。
2. 数据结构中的栈是一种后进先出（LIFO）的数据结构。
3. 在Java中，一个类可以继承另一个类的属性和方法，这体现了面向对象程序设计的继承特性。
4. 在数据库管理系统中，SQL代表结构化查询语言，它是用于管理关系数据库的标准语言。
5. 计算机网络中的DNS服务用于将域名解析为IP地址。
#### 三、简答题（每题10分，共20分）1. 题目：请简述什么是二叉树，并给出二叉树的两种主要遍历方式。
答案：二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
二叉树的两种主要遍历方式是前序遍历和后序遍历。
前序遍历的顺序是先访问根节点，然后是左子树，最后是右子树。
noip初赛试题及答案**NOIP初赛试题及答案**一、选择题（每题2分，共40分）1. 计算机中存储数据的最小单位是（）。
A. 字节B. 位C. 字D. 双字答案：B2. 在计算机中，1KB等于（）。
A. 1024字节B. 512字节C. 256字节D. 1000字节答案：A3. 下列哪种设备不是计算机的输入设备（）。
A. 键盘B. 鼠标C. 显示器D. 扫描仪答案：C4. 在计算机中，二进制数1011转换为十进制数是（）。
A. 11B. 12C. 13D. 14答案：A5. 计算机病毒是一种（）。
A. 计算机硬件B. 计算机软件C. 生物病毒D. 计算机程序答案：D6. 下列哪种文件格式不是图片格式（）。
A. JPGB. BMPC. MP3D. PNG答案：C7. 计算机操作系统的主要功能是（）。
A. 管理计算机硬件B. 管理计算机软件C. 管理计算机资源D. 所有选项都是答案：D8. 以下哪个选项不是计算机网络的组成部分（）。
A. 网络协议B. 网络硬件C. 网络软件D. 网络用户答案：D9. 在计算机编程中，以下哪个关键字用于定义一个类（）。
A. classB. functionC. structD. interface答案：A10. 在计算机编程中，以下哪个关键字用于定义一个方法（）。
A. classB. functionC. methodD. procedure答案：C二、填空题（每题2分，共20分）1. 在计算机中，一个字节由____位组成。
答案：82. 计算机的CPU是计算机的____。
答案：中央处理器3. 计算机的RAM是____存储器。
答案：随机访问4. 在计算机编程中，____是一种用于存储数据的数据结构。
答案：数组5. 在计算机编程中，____是一种用于存储键值对的数据结构。
答案：哈希表6. 计算机的USB接口是一种____接口。
答案：通用串行总线7. 在计算机编程中，____是一种用于控制程序流程的语句。
初赛习题精选（1）一、一、 选择题选择题1、接到Internet 上的每台计算机都必须有一个＿＿＿地址，该地址共含＿＿＿＿个字节。
＿个字节。
前面若干个字节表示＿＿＿＿；前面若干个字节表示＿＿＿＿；前面若干个字节表示＿＿＿＿；后面若干字节表示＿＿＿＿。
后面若干字节表示＿＿＿＿。
后面若干字节表示＿＿＿＿。
为了避为了避免使用数字，人们经常用字母替代，这些名字称为＿＿＿＿。
免使用数字，人们经常用字母替代，这些名字称为＿＿＿＿。
以上填空填（以上填空填（D D ）A ．IP IP、四、网络地址、计算机地址、网名、四、网络地址、计算机地址、网名、四、网络地址、计算机地址、网名B ．网络、四、．网络、四、IP IP 地址、网内计算机地址、域名地址、网内计算机地址、域名C ．网络、不超过十、网页、网址、网名．网络、不超过十、网页、网址、网名D ．IP IP、四、网络地址、网内计算机地址、域名、四、网络地址、网内计算机地址、域名、四、网络地址、网内计算机地址、域名2．《国家标准信息交换用汉字编码》系统共分＿＿＿＿个区，每个区＿＿＿＿个字符。
区位码的第一部份是＿＿＿＿，范围为＿＿＿；第二部份是＿＿＿＿，范围为＿＿＿＿。
以上填空填（范围为＿＿＿＿。
以上填空填（D D ）A ．3、2626、字母、、字母、、字母、00到2626、数字、、数字、、数字、00到9B ．9494、、5252、区码、由、区码、由0到9494、位码、由、位码、由0到94C ．3、9494、区码、由、区码、由0到9494、位码、由、位码、由0到94D ．9494、、9494、区码、由、区码、由0到9494、位码、由、位码、由0到944．Office2000中的“剪贴板”是（中的“剪贴板”是（B B ）A ．硬盘中的一块区域．硬盘中的一块区域B B ．内存中的一块区域．内存中的一块区域C ．Cache 中的一块区域中的一块区域D D ．CPU 中的一块区域中的一块区域5．产生100到300之间的随机函数（之间的随机函数（Random Random Random），且包含），且包含100100、、300两个整数的表达式是（达式是（C C ）A ．Random(100)+200B ．Random(200)+100C ．Random(201)+100D ．Random(300)6．若采用32*32点阵的汉字字模，点阵的汉字字模，存放存放1600个汉字信息需要的存储容量是个汉字信息需要的存储容量是（（B ）KB KB。
信息学奥赛基础知识习题(答案版)一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上）1．我们把计算机硬件系统和软件系统总称为 C 。
(A)计算机CPU (B)固件(C)计算机系统 (D)微处理机2．硬件系统是指 D 。
(A)控制器，运算器 (B)存储器，控制器(C)接口电路，I/O设备 (D)包括(A)、(B)、(C)3. 计算机软件系统包括 B 。
A) 操作系统、网络软件 B) 系统软件、应用软件C) 客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D 。
(A)高级语言 (B)符号语言(C)汇编语言 (D)机器语言5．硬盘工作时应特别注意避免 B 。
(A)噪声 (B)震动 (C)潮湿 (D)日光6．计算机中数据的表示形式是 C 。
(A)八进制 (B)十进制 (C)二进制 (D)十六进制7．下列四个不同数制表示的数中，数值最大的是 A 。
(A)二进制数11011101 (B)八进制数334(C)十进制数219 (D)十六进制数DA8．Windows 9x操作系统是一个 A 。
(A)单用户多任务操作系统 (B)单用户单任务操作系统(C)多用户单任务操作系统 (D)多用户多任务操作系统9．局域网中的计算机为了相互通信，必须安装___B__。
（A）调制解调器（B）网卡（C）声卡（D）电视卡10．域名后缀为edu的主页一般属于__A____。
（A）教育机构（B）军事部门（C）政府部门（D）商业组织11. 香港在世界上注册的顶级域名是__A____。
（A）hk（B）cn（C）tw（D）com12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D ）。
（A）采用超大规模集成电路（B）采用CPU作为中央核心部件（C）采用操作系统（D）存储程序和程序控制13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。
模拟一序列(sequence.exe)问题描述有一个非递减的整数序列S1，S2，S3，……，S n+1（S i<=S i+1）。
定义序列m1，m2，…，m n为S的“M序列”，其中m i=(S i+S i+1)/2。
例如，S=(1, 3, 3, 5)，则m=(2, 3, 4)。
现在给你序列m，要你求有多少个S序列的“M序列”是序列m。
输入(sequence.in)第一行一个整数n，下接n行，每行一个整数m i输出(sequence.out)一个整数，表示有多少个S序列的“M序列”是序列m样例2，2，8，10；1，3，7，11；0，4，6，12；-1，5，5，13。
数据范围50%的数据n<=1000，m i<=20000100%的数据2<=n<=100000，m i<=109.连分数(faction.exe)问题描述Cindy新学了无理数，老师教她了一种用有理数逼进无理数的方法：找到这个无理数相应的无限循环连分数。
例如，我们可以通过分别取出连分数中的一层、两层、三层、……，而忽略其他部分，这样就可以得到一个有理数序列，我们称之为该连分数的渐近分数序列。
黄金分割数215-的渐近分数是1/1，1/2，2/3，3/5，5/8，8/13……。
数据范围60%的数据，m<=105100%的数据，n<=10，m <=109词链（link.exe）问题描述给定一个仅包含小写字母的英文单词表，其中每个单词最多包含50个字母。
如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。
例如下面的单词组成了一个词链：iintinteger而下面的单词不组成词链：integerintern请在给定的单词表中取出一些词，组成最长的词链。
最长的词链就是包含单词数最多的词链。
数据保证给定的单词表中，单词互不相同，并且单词按字典顺序排列。
输入(link.in)第一行一个整数n，表示单词表中单词数下接n行每行一个单词。
输出(link.out)一个整数，表示最长词链长度。
样例数据范围50%的数据，n<=1000100%的数据，n<=10000Geodetic集合(geo.exe)问题描述图G是一个无向连通图，没有自环，并且两点之间至多只有一条边。
我们定义顶点v,u最短路径就是从v到u经过边最少的路径。
所有包含在v-u的最短路径上的顶点被称为v-u的Geodetic顶点，这些顶点的集合记作I(v, u)。
我们称集合I(v, u)为一个Geodetic集合。
例如下图中，I(2, 5)={2, 3, 4, 5}，I(1, 5)={1, 3, 5}，I(2, 4)={2, 4}。
给定一个图G和若干点对v,u，请你分别求出I(v, u)。
输入(geo.in)第一行两个整数n,m，分别表示图G的顶点数和边数（顶点编号1-n）下接m行，每行两个整数a,b表示顶点a和b之间有一条无向边。
第m+2行有一个整数k，表示给定的点对数。
下接k行，每行两个整数v,u。
输出(geo.out)共k行，每行对应输入文件中每一个点对v,u，按顶点编号升序输出I(v, u)。
同一行的每个数之间用空格分隔。
样例数据范围100%的数据，n<=40各题简要分析：sequence 序列：令S 序列的第一项为k ，那么后面几项就可以写成关于k 的多项式： S1=kS2=2*m1-kS3=2*m2-2*m1+k ……然后根据S 序列的非递减性质，有S1<=S2<=S3<=…. 所以有k<=2*m1-k2*m1-k<=2*m2-2*m1+k ……可以得到n 个关于k 的不等式，而且都是有规律的，可以在O(n)的时间内解出形如 a<=k<=b 的结果。
由于k 的值和S 序列是一一对应的，所以k 的取值的个数(b-a)就是满足要求的S 序列的个数。
faction 连分数：本题是原创的，重点考察递推和用矩阵乘法优化递推。
由递推式：111--+=m m k mmy x p y x k = (m-1) mod n + 1可得1-=m m y x ; m m k m x y p y +=-1*直接按照这个递推式计算，复杂度O(m)，预计得分60%。
上面的递推式对应的矩阵运算是：所以有⎥⎦⎥⎢⎣⎢=⎥⎦⎤⎢⎣⎡⎪⎪⎭⎫ ⎝⎛=∏n m n k k m m p c y x 1110**)1,0(),( 其中c 是(m mod n)部分的余式矩阵的乘积。
由于计算矩阵幂时间复杂度为O(logm)，所以总的算法复杂度是O(n+logm)，预计得分100%。
⎪⎪⎭⎫ ⎝⎛=--k m m m m p y x y x 110*),(),(11Link词链：本题用动态规划是容易的，设f(i)表示前i个单词可以构成包含第i个单词的最长词链。
F(i)=max{1，F(j)+1,当word[j]是word[i]的前缀}Ans=max{F(i)}这样算法的复杂度是O(n2)，预计得分50%。
其实本题有很简单的贪心算法。
用一个栈存储当前的以第i个单词结尾的最长词链，第i+1个单词加在栈的结尾（通过出栈保持栈所存储的是一个词链）。
例如：i 栈：iint 栈：i intinteger 栈：i int intergerintern 栈：i int intern （interger出栈）internet 栈：i int intern internet可以证明，在第i个单词插入后，当前在栈中的词链就是包含第i个单词的最长词链。
这样由于每个单词进栈出栈分别一次，所以算法的复杂度是O(n)贪心算法预计得分100%Geodetic集合：本题是由pku上一道试题改编的，考察图的有关知识。
算法就是从每个点出发进行BFS 扩展，按得到的BFS序列进行递推。
设min[i, j]为从i到j的最短路长度设f[i, j]表示从i到j点的最短路覆盖的节点集合，f[i, j] = f[i, k] U {j} k={1..n} and (min[i, k]+1=min[i, j]）and (k,j)存在对于输入的每个v,u对，输出f[v,u]中的所有点就可以了。
模拟二奖金（Reward.pas/exe）【题目描述】由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z 心情好，决定给每位员工发奖金。
公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。
于是Mr.Z下令召开m方会谈。
每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。
每位员工奖金最少为100元。
【输入】第一行两个整数n,m，表示员工总数和代表数；以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。
【输出】若无法找到合法方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。
【样例输入】2 11 2【样例输出】201【数据范围】80％的数据满足n<=1000，m<=2000；100％的数据满足n<=10000，m<=20000。
编码（Encode.pas/exe）【问题描述】DEX国刚刚截获了KCAJ国与AW AW国之间的S.Message1。
D国S302情报机构情报员0072手里正拿着写有K国与A国之间Message的文件。
“什么？！居然被加密了！！”007忍不住说道，“KCAJ，你会出路的！”幸运的是K国与A国此次通讯时间远远超过了007所估计的30s，因此007又截获了大量的Message。
通过对这些Message的研究，007发现了其中的秘密：每一条S.Message原本由8个32-bit的正整数N1..N8组成，本来这8个整数可以由计算机直接破解得出相应的文字。
但对于每条信息，K国与A国另外使用了不同的密钥M来再次加密。
所谓“密钥”其实也是一个32-bit的整数，在传递讯息的时候，是将N1 Xor M、N2 Xor M、…、N8 Xor M、N9 Xor M这9个整数传给对方（其中N9为N1~N8这8个整数的和Mod 2^32）。
有了上面的发现，007马上意识到他可以破解出Message了！这实在是一个简单的工作，007决定让你——也就是他的助手来完成此工作。
【输入】输入文件按顺序输入9个整数N1..N9。
每个整数用16进制表示。
【输出】输出仅一个数，即密钥M。
同样用16进制表示。
【样例输入】3 4 4 7 7 b a 2 2e【样例输出】6【数据范围】40％的数据满足M<=500；100％的数据满足M<2^32；1S.Message是Seceret Message的缩写，绝对不是Short Message的缩写2此人极度神秘，目前只知道他的代号为302.007工作（Work.pas/exe）【题目描述】这次故事的主角是HG！转眼4年过去了，HG本科毕业了，于是找了份工作。
每天HG 会收到一份任务清单，清单上列出了n个可能需要他完成的任务。
每个任务包含3个信息：Ti、Ai、Bi，Ti表示完成此任务需要的时间，Ai表示此任务的到达时间，Bi表示此任务的最晚完成时间。
在某一时刻若HG手上没有任务，那么他可以选择一个已经到达且还能够在Bi时刻之前（或者恰好在Bi时刻）完成的任务来做。
由于HG有点懒（纯属虚构:D），他想尽量少的减少他的总工作时间，但是他不能在可以做任务的时候故意不做（这样会被炒鱿鱼的>_<），那么他该如何挑选任务来做呢？你的任务就是求出HG的最少工作时间（即总共有多少时间HG在做任务）。
【输入】第一行一个整数n表示任务数。
以下n行，每行三个整数Ti,Ai,Bi。
（n<=1000，0<=Ai,Bi<=1500，Ti>=1）【输出】输出仅一个数，即最少工作时间。
【样例输入】315 0 2550 0 9045 15 70【样例输出】50【数据范围】Ti>=1，0<=Ai,Bi<=1200；30%的数据满足n<=5；60％的数据满足n<=500；100％的数据满足n<=1000。
【说明】输入数据保证Bi-Ai要大于等于Ti，且小于2Ti。
求和（Sum.pas/exe ）【题目描述】高斯在他还是小P 孩的时候就求出了1+2+…+n ＝n*(n+1)/2；LT 在他还是小P 孩的时候就知道1/(1*2)+1/(2*3)+…+1/((n-1)*n)＝1-1/n ；现在，在你还是小P 孩的时候，你要求出)1()1(1211-+⨯⨯+⨯⨯⨯⨯m n n n m S ＋＋＝ 【输入】输入两个整数n,m 。
