字符串处理:从string.in
文件里读入两个字符串,字符串除了数字还可能包括'-'、'E'、'e'、'.'
,相加之后输出到文件string.out
中,如果是浮点型,要求用科学计数法表示(最多保留10个有效数字)。
输入示例:
34.56
2.45e2
输出示例:
2.7956e2
本题用C++的输入输出比较难处理,用C语言中的scanf
、printf
进行处理,注意按照题目要求,去除指数表示中的底数部分小数点后多余的0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
using namespace std;
int main(int argc, char *argv[]) {
double a, b;
char buf[128];
FILE *infile = fopen("./string.in", "r");
FILE *outfile = fopen("./string.out", "w");
if (!infile || !outfile) exit(1);
fscanf(infile, "%lf", &a);
fscanf(infile, "%lf", &b);
sprintf(buf, "%.10e", a+b);
int i, j;
for (i = 0; buf[i] != '\0'; i++)
if (buf[i] == 'e')
break;
for (j = i-1; buf[j] == '0'; j--);
for (int k = 0; k <= j; k++)
fputc(buf[k], outfile);
fputc('e', outfile);
for (j = i+1; buf[j] != '\0'; j++)
fputc(buf[j], outfile);
return 0;
}
|
最大公约数:从number.in
文件中读入n个数,求出这n个数的最小值、最大值以及它们两的最大公约数,输出到文件number.out
中。number.in 中第一行为n,接下来为n个大于零的整数。
输入示例:
3
4 8 6
输出示例:
4 8 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <fstream>
#include <vector>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int main(int argc, char *argv[]) {
ifstream ifs("./number.in");
ofstream ofs("./number.out");
int n;
ifs >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
ifs >> a[i];
int minVal, maxVal;
minVal = maxVal = a[0];
for (int i = 1; i < n; i++) {
if (a[i] < minVal)
minVal = a[i];
if (a[i] > maxVal)
maxVal = a[i];
}
ofs << minVal << " " << maxVal << " " << gcd(maxVal, minVal);
return 0;
}
|
任务调度:从task.in
文件中读入任务调度序列,输出n个任务适合的一种调度方式到task.out
中。每行第一个表示前序任务,括号中的任务为后序任务,只有在前序任务完成的情况下,后序任务才能开始。若后序为NULL则表示无后序任务。
输入示例:
Task0(Task1,Task2)
Task1(Task3)
Task2(NULL)
Task3(NULL)
输出示例:
Task0 Task1 Task3 Task2
本题考察的是拓朴排序
的代码实现,对于该算法不熟悉的请参考这篇文章。在这里用dfs
和visit数组
来实现拓朴排序。
本题另外一个难点在于处理给定的文件形式,我们用多个unordered_map
来存储某个任务名字与对应结点号之间的映射关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <fstream>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<string, int> idxMap;
unordered_map<int, string> nameMap;
unordered_map<int, vector<int>> adjMap;
vector<int> q;
int curIdx = 0;
void parseLine(const string &line) {
string tmp;
int i, j;
for (i = 0; i < line.length(); i++)
if (line[i] == '(')
break;
tmp = line.substr(0, i);
if (!idxMap.count(tmp)) {
nameMap[curIdx] = tmp;
idxMap[tmp] = curIdx++;
}
int src = idxMap[tmp];
for (j = ++i; j <= line.length(); j++) {
if (line[j] == ',' || line[j] == ')') {
tmp = line.substr(i, j - i);
if (!idxMap.count(tmp)) {
nameMap[curIdx] = tmp;
idxMap[tmp] = curIdx++;
}
adjMap[src].push_back(idxMap[tmp]);
i = ++j;
}
}
}
void dfs(vector<int> &vis, int src) {
vis[src] = 1;
for (int next : adjMap[src]) {
if (next == -1)
break;
if (vis[next])
continue;
dfs(vis, next);
}
q.push_back(src);
}
int main(int argc, char *argv[]) {
ifstream ifs("./task.in");
ofstream ofs("./task.out");
idxMap["NULL"] = -1;
string line;
while (getline(ifs, line)) {
parseLine(line);
}
int size = curIdx;
vector<int> vis(size, 0);
for (int i = 0; i < size; i++) {
if (vis[i])
continue;
dfs(vis, i);
}
for (int i = q.size() - 1; i >= 0; i--) {
if (i != q.size()-1)
ofs << " ";
ofs << nameMap[q[i]];
}
return 0;
}
|
火车票订购:火车经过X站,火车的最大载客人数为m,有n个订票请求,请求订购从a站到b站的k张票,若能满足订购要求则输出1,否则输出0。数据从ticket.in
中输入,第一行有两个数字,分别是n,m。接下来有n行,每行三个数分别是a、b、k。结果输出到文件ticket.out
中。
输入示例:
5 10
4 10 9
8 12 2
8 12 1
14 20 8
30 300 15
输出示例:
1
0
1
1
0
用一个大数组来存储每一站的车上人数,在每一次运送乘客时先尝试是否有足够空位,如果有空位则将flag置为1,否则将flag置为0,如果尝试之后flag=1则可以搭载这波乘客。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <fstream>
#include <map>
#include <memory.h>
using namespace std;
int main(int argc, char *argv[]) {
ifstream ifs("./ticket.in");
ofstream ofs("./ticket.out");
int nums[10000];
memset(nums, 0, 10000);
int n, m;
ifs >> n >> m;
int a, b, c, flag;
for (int i = 0; i < n; i++) {
ifs >> a >> b >> c;
flag = 1;
for (int j = a; j < b; j++) {
if (nums[j] + c > m) {
flag = 0;
break;
}
}
if (flag) {
for (int j = a; j < b; j++) {
nums[j] += c;
}
}
ofs << flag << endl;
}
return 0;
}
|
最短路径:有n个城市和m条道路(n < 1000, m < 10000),每条道路有不同的长度,请找到从起点s到终点t的最短距离,并且输出经过的城市的序号,如果有多条,输出字典序最小的那条;若从s到t没有路径,则输出“can't arrive”。从文件road.in
中读入数据,第一行有四个数,分别为n、m、s、t。接下来有m行,每行三个数,分别为两个城市的序号和相互之间的距离,将结果输出结果到文件road.out
中。
输入示例:
3 3 1 3
1 3 3
1 2 1
2 3 1
输出示例:
2
1 2 3
使用floyed-warshall
算法,用road二维数组记录图的信息,用next二维数组记录下一跳。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <fstream>
#include <vector>
using namespace std;
#define INF 0x7fffffff
int main(int argc, char *argv[]) {
ifstream ifs("./road.in");
ofstream ofs("./road.out");
int cityCnt, roadCnt, src, dst;
ifs >> cityCnt >> roadCnt >> src >> dst;
vector<vector<int>> road(cityCnt+1, vector<int> (cityCnt+1, INF));
vector<vector<int>> next(cityCnt+1, vector<int> (cityCnt+1, -1));
for (int i = 0; i < roadCnt; i++) {
int a, b, c;
ifs >> a >> b >> c;
road[a][b] = c;
next[a][b] = b;
}
// floyed-warshall
for (int k = 1; k <= cityCnt; k++) {
for (int i = 1; i <= cityCnt; i++) {
for (int j = 1; j <= cityCnt; j++) {
if (road[i][k] != INF && road[k][j] != INF && road[i][k] + road[k][j] < road[i][j]) {
road[i][j] = road[i][k] + road[k][j];
next[i][j] = k;
}
}
}
}
ofs << road[src][dst] << endl;
int i = src;
while (i != dst) {
ofs << i << " ";
i = next[i][dst];
}
ofs << dst;
return 0;
}
|