内容发布更新时间 : 2024/5/18 18:06:37星期一 下面是文章的全部内容请认真阅读。
只允许用iostream 、fstream、cstdio 运行时间1s 内存：32M 1.Ordered Fractions
Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N. Here is the set when N = 5:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.
PROGRAM NAME: frac.cpp INPUT FORMAT
One line with a single integer N.
SAMPLE INPUT (file frac.in)
5
OUTPUT FORMAT
One fraction per line, sorted in order of magnitude.
SAMPLE OUTPUT (file frac.out)
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
2.集合
给定N个整数集合（S[1],S[2],…,S[N]）及M个集合操作，编写程序计算这些操作执行后N个集合的值。
一个集合操作是一个三元组（k,x,y），其中k表示对集合S[x]和S[y]所进行的操作。
- 当k=1时，更新S[x]的值为union(S[x],S[y]) - 当k=2时，更新S[x]的值为insersect(S[x],S[y]) - 当k=3时，更新S[x]的值为complement(S[x],S[y]) 对于两个集合A和B，我们如下定义三种运算：
- union(A,B)中的元素可以在A中，或在B中，或同时在A和B中 - intersect(A,B)中的元素既在A中也在B中 - complement(A,B)中的元素在B中但不在A中 程序文件名：set.cpp 输入格式
第1行是两个正整数N和M
第2行到第N+1行定义了N个集合最初的值
第i行（ 2<=i<=N+1）以一个非负整数c开始，接下来是c个互不相同的非负整数a[1]，a[2],...,a[c],表示S[i]={a[1],a[2],...,a[c]}
第N+2行到第 M+N+1行定义了M个集合操作 第j行(N+2<=j<=M+N+1)包含三个正整数k、x和y
输入中所有整数都是小于1000,30%的测试数据中的整数都小于300
样例输入（文件set.in） 3 3
5 10 20 30 40 50 3 60 40 20 3 10 20 30 2 3 2 3 3 2 1 1 3 输出格式
输出N行，其中第 i 行为集合S[i]的大小。 样例输出（文件set.out） 6 3 2
样例解释
开始时，三个集合状态如下： S[1]={10,20,30,40,50} S[2]={20,40,60} S[3]={10,20,30}
- 对于操作{2,3,3},更新S[3]的值为intersect(S[3],S[2])，即{20}
- 对于操作{3,3,2},更新S[3]的值为complement(S[3],S[2])，即{40,60}
- 对于操作{1,1,3},更新S[1]的值为union(S[1],S[3])，即{10,20,30,40,50,60}
3.迷宫
小红和小明在迷宫里迷路了。迷宫是一个无向连通图，边的长度为1个单位长度。小红和小明站在图的两个顶点上。他们需要走到一个公共的顶点会合。 小红和小明行走的最大速度都是每秒1个单位长度。他们可以同时行走，但不能在边的中途停下。
给定该图和二人所在的位置，编写程序计算他们会合所需的最短时间T(以秒为单位)。
程序文件名：maze.cpp 输入格式
第1行包含一个正整数M，表示图中边的数目
第2行到第M+1行，每行包含两个正整数X和Y，表示X和Y之间有一条边 第M+2行包含两个正整数A和B，分别表示小红和小明所在的顶点位置
顶点编号是任意的，且边会以任意顺序给出。输入中所有整数都小于10000，30%的测试数据中的整数都小于3000
样例输入（文件maze.in）
8 1 2 2 3 4 5 6 5 3 4 7 2 7 5 6 4 2 6
输出格式
输出仅有一行，为整数T(二人会合所需最短时间)
样例输出（文件maze.out）
2
样例解释
他们可以在3、4、5、7这四个点中的任意一个顶点会合，其中一个人需要行走2秒，另一个人可以行走1秒，再等待1秒。