NOIP2013年普及组初赛题目及答案分析
【贪心】----(字典序)最大整数
【题目描述】
设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213；
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613
【输入】
两行，第一行n。表示有n个数。
第二行是 n个数。
【输出】
连接成的多位数
【输入样例】
3 13 312 343
【输出样例】
34331213
数组的不确定长度输入
【贪心】 导弹拦截
【题目描述】
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：
虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。
所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。
计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
【输入】
n颗依次飞来的高度（1≤n≤1000）。
【输出】
要拦截所有导弹最小配备的系统数k。
【输入样例】
389 207 155 300 299 170 158 65
【输出样例】
2
【提示】
输入：导弹高度： 4 3 2
输出：导弹拦截系统k=1
【贪心】区间覆盖
【题目描述】
给定一个长度为m的区间，再给出n条线段的起点和终点（本题考虑闭区间），求最少使用多少线段可以将整个区间完全覆盖。
【输入】
第一行是区间长度m。第二行是n,表示有n个可选区间。后面跟着n行数据，每行包含两个值，第一个是当前区间的起始端点值，第二个是当前区间的结束端点值。
【输出】
能覆盖m的最少的区间个数
【输入样例1】
8 6 2 6 1 4 3 6 3 7 6 8 2 4 3 5
【输出样例1】
3
【题解】会场安排
【贪心】区间选点
【题目描述】
数轴上有n个闭区间[ai, bi]，取尽量少的点，使得每个区间内都至少有一个点。（不同区间内含的点可以是同一个，1<=n<=10000，1<=ai<=bi<=10^9）。求最少点的个数。
【输入】
n
n项工作的开始与结束时间
【输出】
最多参与的工作项数
【输入样例1】
Bash
4 3 13 6 20 4 14 1 10
【输出样例1】
1
【输入样例2】
Bash
3 4 7 6 8 11 20
【输出样例2】
2
【贪心】区间调度
【题目描述】
有n项工作，每项工作分别在si时间开始，在ti时间结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（即使是开始与结束的瞬间重叠也是不允许的）。
你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？1<=n<=100000，1<=si<=ti<=10^9。
【输入】
n
n项工作的开始与结束时间
【输出】
最多参与的工作项数
【输入样例】
5 1 3 2 5 4 7 6 9 8 10
【输出样例】
3
【题解—深搜】马走日
【题目描述】
马在中国象棋以日字形规则移动。
请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
【输入】
第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m < 10, n < 10)。
【输出】
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。
【输入样例】
1 5 4 0 0
【输出样例】
32