Tuesday, 3. April 2007, 12:38:16
NOIp 2005 普及组 problem2
校门外的树
(tree.pas/c/cpp)
【问题描述】
某校大门外长度为L 的马路上有一排树，每两棵相邻的树之间的间隔都是1 米。我们
可以把马路看成一个数轴，马路的一端在数轴0 的位置，另一端在L 的位置；数轴上的每
个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表
示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要
把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，
马路上还有多少棵树。
【输入文件】
输入文件tree.in 的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L
代表马路的长度，M 代表区域的数目，L 和M 之间用一个空格隔开。接下来的M 行每行包
含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
【输出文件】
输出文件tree.out 包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
【样例输入】
500 3
150 300
100 200
470 471
【样例输出】
298
【数据规模】
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
分析开一个布尔型数组，下标是0..10000的，初始值全设为ture表示这地方有树。读入L和M，以下开始循环M次：
读入a,b即为要搬走的初始地和结束地，数组中a..b设为false表示这地方没树，已经搬走了。
……
循环结束后，数组中值为ture的下标就是没搬走的树的编号。那么想办法输出……
代码program tree;
var
t:array[0..10000] of boolean;
m,l,a,b,i,j,k:integer;
begin
for i:=0 to 10000 do t[i]:=true;
read(l,m);
for i:=1 to m do
begin
read(a,b);
for j:=a to b do t[j]:=false;
end;
k:=0;
for i:=0 to l do
if t[i] then k:=k+1;
write(k);
end.
----------欧是Vitamin哥哥的乖乖分割线----------IOI 1994 day1 problenm1
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。
Input
输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
Output
输出最大的和。
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Source
翻译自 IOI 1994 的试题
分析从下往上模拟走一次。就是代码中的
if a[i+1,j]>=a[i+1,j+1]
then a[i,j]:=a[i,j]+a[i+1,j]
else a[i,j]:=a[i,j]+a[i+1,j+1];这一句。注意外循环的初值应赋成n-1，终值是1；内循环的初值是外循环值，终值也是1。
代码program triangle;
var
a:array[1..100,1..100]of integer;
n,i,j:integer;
begin
assign(input,'input.txt');
reset(input);
read(n);
for i:=1 to n do
for j:=1 to i do read(a[i,j]);
close(input);
for i:=n-1 downto 1 do
for j:=i downto 1 do
if a[i+1,j]>=a[i+1,j+1]
then a[i,j]:=a[i,j]+a[i+1,j]
else a[i,j]:=a[i,j]+a[i+1,j+1];
assign(output,'output.txt');
rewrite(output);
write(a[1,1]);
close(output);
end.
WIDGETIZE