1.2018期末机考题目网址：
(1)普通班：http://dsa.openjudge.cn/final20181223
(2)实验班：http://dsa.openjudge.cn/final2018ht
2.参考资料下载地址
(1)http://media.openjudge.cn/upload/DSMooc/DSCode_ZhangWangZhao2008_06.rar
(2)http://media.openjudge.cn/upload/DSMooc/DScodeCversion.rar (C语言代码包)
(3)http://media.openjudge.cn/upload/DSMooc/201810cplusplus.zip (C++手册)
(4)http://media.openjudge.cn/upload/DSMooc/DSAlgoWeissMark.pdf (英文教材)
3.OJ上2018期末考试没有开放，但是有些题目在别的小组能找到，题目网址附在题目后。
网址：http://bailian.openjudge.cn/practice/2804/
你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是，你有一本词典可以帮助你。
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
cat
eh
loops
1 # include <iostream>
2 # include <cstdio>
3 # include <algorithm>
4 # include <string.h>
5 using namespace std;
6
7 //type: DIC
8 typedef struct{
9 char w1[12], w2[12];
10 } DIC;
11
12 //d1.w1 < d2.w1
13 bool cmp(DIC d1, DIC d2){
14 return (strcmp(d1.w2, d2.w2) < 0);
15 }
16
17
18 DIC d[100010]; //dictionary: increasing order
19 int n = 0; //n pairs of words in dic
20 char s[25]; //input strings s[]
21
22 //initialize dictionary: separate 2 words
23 void IniDic(int num){
24 int pos;
25 for(pos = 0; s[pos] != ‘ ‘; ++pos);
26 strncpy(d[num].w1, s, pos);
27 strncpy(d[num].w2, s+pos+1, 11);
28 }
29
30 //binary search: lookfor word s[]
31 void SearchWord(){
32 int r = 0, l = n - 1, m, t; //first, last, middle
33 while(r < l){
34 m = (r + l) / 2;
35 if((t = strcmp(s, d[m].w2)) == 0){
36 printf("%s\n", d[m].w1);
37 return; //find s = d[m].w1
38 }
39 else if(t > 0) //s > d[m].w1
40 r = m + 1;
41 else //s < d[m].w1
42 l = m - 1;
43 }
44 if(strcmp(s, d[r].w2) == 0)
45 printf("%s\n", d[r].w1);
46 else
47 printf("eh\n");
48 return;
49 }
50
51 int main(){
52 while((s[0] = cin.get()) != ‘\n‘){
53 cin.getline(s+1, 24);
54 IniDic(n++);
55 }
56 //cout << n << endl;
57 sort(d, d+n, cmp); //sort dictionary
58 //for(int i = 0; i < n; ++i)
59 //printf("dic[%d]: %s %s\n", i, d[i].w1, d[i].w2);
60 while(cin >> s){
61 SearchWord();
62 }
63 return 0;
64 }
1.空行的识别,get(),cin.getline()等
2.单词排序：定义比较函数<template T> bool cmp(T t1, T t2);
3.单词查找：二分查找
来源：USACO 2016 US Open contest，没找到开放的在线测评网站
Farmer John‘s N cows (5≤N≤50,000) are all located at distinct positions in his two-dimensional field. FJ wants to enclose all of the cows with a rectangular fence whose sides are parallel to the x and y axes, and he wants this fence to be as small as possible so that it contains every cow (cows on the boundary are allowed). FJ is unfortunately on a tight budget due to low milk production last quarter. He would therefore like to build an even smaller fenced enclosure if possible, and he is willing to sell up to three cows from his herd to make this possible. Please help FJ compute the smallest possible area he can enclose with his fence after removing up to three cows from his herd (and thereafter building the tightest enclosing fence for the remaining cows). For this problem, please treat cows as points and the fence as a collection of four line segments (i.e., don‘t think of the cows as "unit squares"). Note that the answer can be zero, for example if all remaining cows end up standing in a common vertical or horizontal line.
农夫约翰的N(5<=N<=50000)头牛被定在了平面内的不同的位置。他想用栅栏(平行于x和y轴)围住所有的牛。他想这个栅栏尽可能小(牛在边界上也被视作围住)。
他因为牛奶产量低而感到经费紧张，所以他想卖掉三头牛再围起剩下的牛。请算出栅栏围出的最小面积。(面积有可能为0，例如，最后剩下的牛排成一排或一列。）
第一行输入正整数n
剩下2-n+1行，输入每头牛的坐标位置(x,y) ( 1<= x,y<=40000的整数）
6
1 1
7 8
10 9
8 12
4 100
50 7
12
按x、y的大小分别排序，每次去掉xmin/xmax/ymin/ymax的一头牛，dfs或者直接枚举
(只在本地测试了一些数据)
1 # include <iostream>
2 # include <algorithm>
3 using namespace std;
4 #define MAXSPACE 2000000000
5
6 //cow‘s position
7 typedef struct{
8 int x, y;
9 } COW;
10
11 //compare cow‘s x
12 bool cmpx(COW c1, COW c2){
13 return c1.x < c2.x;
14 }
15
16 //compare cow‘s y
17 bool cmpy(COW c1, COW c2){
18 return c1.y < c2.y;
19 }
20
21 int n;
22 COW * c;
23
24 //find min from 4 values
25 int MyMin(int a, int b, int c, int d){
26 if(a < b){
27 if(a < c){
28 if(a < d) return a;
29 else return d;
30 }
31 else{
32 if(c < d) return c;
33 else return d;
34 }
35 }
36 else{
37 if(b < c){
38 if(b < d) return b;
39 else return d;
40 }
41 else{
42 if(c < d) return c;
43 else return d;
44 }
45 }
46 }
47
48 //calculate min space needed after selling r cows from c[s~e-1]
49 int MinSpace(int s, int e, int r){
50 if(r == 0){ //no cows to sell
51 int x1, x2, y1, y2;
52 sort(c+s, c+e, cmpx);
53 x1 = c[s].x;
54 x2 = c[e-1].x;
55 sort(c+s, c+e, cmpy);
56 y1 = c[s].y;
57 y2 = c[e-1].y;
58 return (x2-x1)*(y2-y1);
59 }
60 int mx1 = MAXSPACE, mx2 = MAXSPACE, my1 = MAXSPACE, my2 = MAXSPACE;
61 sort(c+s, c+e, cmpx);
62 //sell the cow with min-x
63 //if c[s].x == c[s+3].x, then selling cow s won‘t make space smaller (from x‘s perspective)
64 if(s+3 < e && c[s].x != c[s+3].x)
65 mx1 = MinSpace(s+1, e, r-1);
66 //sell the cow with max-x
67 if(s+3 < e && c[e-4].x != c[e-1].x)
68 mx2 = MinSpace(s, e-1, r-1);
69 sort(c+s, c+e, cmpy);
70 //sell the cow with min-y
71 if(s+3 < e && c[s].y != c[s+3].y)
72 my1 = MinSpace(s+1, e, r-1);
73 //sell the cow with max-y
74 if(s+3 < e && c[e-4].y != c[e-1].y)
75 my2 = MinSpace(s, e-1, r-1);
76 return MyMin(mx1, mx2, my1, my2);
77 }
78
79 int main(){
80 cin >> n;
81 c = new COW[n+1];
82 for(int i = 0; i < n; ++i)
83 cin >> c[i].x >> c[i].y;
84 cout << MinSpace(0, n, 3) << endl;
85 delete [] c;
86 return 0;
87 }
有很多重复的sort，非常耗时
1 # include <iostream>
2 # include <algorithm>
3 # include <cstdio>
4 using namespace std;
5 #define MAXSPACE 2000000000
6
7 //cow‘s position
8 typedef struct{
9 int x, y;
10 } COW;
11
12 //compare cow‘s x
13 bool cmpx(COW c1, COW c2){
14 return c1.x < c2.x;
15 }
16
17 //compare cow‘s y
18 bool cmpy(COW c1, COW c2){
19 return c1.y < c2.y;
20 }
21
22 int n, ans = MAXSPACE;
23 COW * c;
24
25 //min value of a & b
26 int MyMin(int a, int b){
27 if(a < b) return a;
28 else return b;
29 }
30
31 //calculate space needed
32 //after selling x1 cows with min-x, x2 cows with max-x,
33 //and selling y1 cows with min-y, y2 cows with max-y
34 void Space(int x1, int x2, int y1, int y2){
35 sort(c, c+n, cmpx);
36 sort(c+x1, c+n-x2, cmpy);
37 int miny = c[x1+y1].y, maxy = c[n-x2-y2-1].y;
38 sort(c+x1+y1, c+n-x2-y2, cmpx);
39 int minx = c[x1+y1].x, maxx = c[n-x2-y2-1].x;
40 int s = (maxx - minx) * (maxy - miny);
41 /* testing code */
42 /*
43 printf("%d %d %d %d %d\n", x1,x2,y1,y2, s);
44 printf(" x: %d-%d, y: %d-%d\n ", minx,maxx, miny, maxy);
45 for(int i=0; i<n; ++i)
46 printf("(%d,%d) ", c[i].x, c[i].y);
47 printf("\n");
48 */
49 ans = MyMin(s, ans);
50 }
51
52 int main(){
53 cin >> n;
54 c = new COW[n+1];
55 for(int i = 0; i < n; ++i)
56 cin >> c[i].x >> c[i].y;
57 for(int i = 0; i <= 3; ++i)
58 for(int j = 0; i+j <= 3; ++j)
59 for(int k = 0; i+j+k <= 3; ++k)
60 Space(i, j, k, 3-i-j-k);
61 cout << ans << endl;
62 delete [] c;
63 return 0;
64 }
枚举要去掉的牛的位置和个数
网址：http://bailian.openjudge.cn/practice/2299/
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 5
9
1
0
5
4
3
1
2
3
0
6
0
1 # include <cstdio>
2 using namespace std;
3
4 int main(){
5 int n, a[500000], cnt, tmp;
6 scanf("%d", &n);
7 while(n){
8 cnt = 0;
9 for(int i = 0; i < n; ++i)
10 scanf("%d", a + i);
11 for(int i = n - 1; i; --i)
12 for(int j = 0; j < i; ++j){
13 if(a[j] > a[j+1]){
14 tmp = a[j];
15 a[j] = a[j+1];
16 a[j+1] = tmp;
17 ++cnt;
18 }
19 }
20 printf("%d\n", cnt);
21 scanf("%d", &n);
22 }
23 return 0;
24 }
1 # include <cstdio>
2 using namespace std;
3
4 int main(){
5 int n, a[500000], cnt, tmp;
6 bool f; //flag
7 scanf("%d", &n);
8 while(n){
9 cnt = 0;
10 for(int i = 0; i < n; ++i)
11 scanf("%d", a + i);
12 for(int i = n - 1; i; --i){
13 f = 1; //flag
14 for(int j = 0; j < i; ++j){
15 if(a[j] > a[j+1]){
16 tmp = a[j];
17 a[j] = a[j+1];
18 a[j+1] = tmp;
19 ++cnt;
20 f = 0; //flag
21 }
22 }
23 if(f) break;
24 }
25 printf("%d\n", cnt);
26 scanf("%d", &n);
27 }
28 return 0;
29 }
冒泡(复杂度O(n^2))妥妥TLE
换了归并(复杂度O(nlgn))，终于AC
1 # include <cstdio>
2 using namespace std;
3
4 //length n, array a[], temp array t[]
5 int n, a[500000], t[500000];
6
7 //Merge(start, middle, end)
8 long long Merge(int s, int m, int e){
9 int i = s, j = m+1, k = s;
10 long long cnt = 0;
11 while(i <= m && j <= e){
12 if(a[i] < a[j])
13 t[k++] = a[i++];
14 else{
15 t[k++] = a[j++];
16 cnt += j - k; //a[j] go to a[k] needs j-k exchanges
17 }
18 }
19 while(i <= m) t[k++] = a[i++];
20 while(j <= e) t[k++] = a[j++];
21 for(int l = s; l <= e; ++l)
22 a[l] = t[l];
23 return cnt;
24 }
25
26 //Divide & sort & merge
27 long long MergeSort(int s, int e){
28 if(s >= e) return 0; //exit of recursion
29 int m = (s + e) / 2;
30 long long ret = 0;
31 ret += MergeSort(s, m); //sort a[s~m]
32 ret += MergeSort(m + 1, e); //sort a[m+1~e]
33 ret += Merge(s, m, e); //merge a[s~m] & a[m+1~e]
34 return ret;
35 }
36
37 int main(){
38 scanf("%d", &n);
39 while(n){
40 for(int i = 0; i < n; ++i)
41 scanf("%d", a + i);
42 printf("%lld\n", MergeSort(0, n-1));
43 scanf("%d", &n);
44 }
45 return 0;
46 }
1.注意数据类型用long long (亲测int会WA)
2.采用归并排序，记录归并过程中记录交换次数(AC代码第16行：cnt += j-k 或 cnt += m-i+1)
网址：http://dsa.openjudge.cn/tree/0609/
众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树：
+
/ \
a *
/ \
b c
现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。
a+b*c
3
a 2
b 7
c 5
abc*+
+
/ a *
/ b c
37
1 # include <iostream>
2 # include <cstdio>
3 # include <stack>
4 using namespace std;
5
6 char a[20], b[20], c; //input a[], answer b[]
7 char ** pic; //picture of tree
8 int v[30], n, t;//v[] store values
9 int len; //len = lenght of b[]
10 int pos; //current index when biulding tree
11 int dep = 0; //depth of tree
12 stack<int> st1; //help calculate
13
14 //define Node of binary tree
15 typedef struct NODE{
16 char c; //symbol of node
17 int d; //depth of node
18 NODE *l, *r;//pointer to children
19 } Node;
20
21 Node * root, * cur;
22
23 //biuld the subtree with root b[l]
24 Node * BiuldSubtree(int d){
25 Node * tmp = new Node;
26 tmp->c = b[pos--]; //set node‘s symbol
27 tmp->d = d; //set node‘s depth
28 if(d > dep) dep = d; //renew depth of tree
29 if(tmp->c >= ‘a‘ && tmp->c <= ‘z‘)
30 tmp->l = tmp->r = NULL; //leaf nodes (variables)
31 else{ //branch nodes (operators)
32 tmp->r = BiuldSubtree(d+1);
33 tmp->l = BiuldSubtree(d+1);
34 }
35 return tmp;
36 }
37 //Biuld binary tree
38 void BiuldTree(){
39 pos = len-1; //current position of b[]
40 root = BiuldSubtree(0);
41 //printf("depth = %d\n", dep);
42 }
43 //delete Tree
44 void DelTree(Node * ptr){
45 if(ptr == NULL) return;
46 DelTree(ptr->l);
47 DelTree(ptr->r);
48 delete ptr;
49 }
50 //Draw the subtree ptr pointing to from (si, sj) in pic[][]
51 void DrawSubtree(Node * ptr, int si, int sj){
52 if(ptr == NULL) return; //draw nothing
53 int i = si, j = sj + (1<<(dep-ptr->d)) - 1;
54 pic[i][j] = ptr->c;
55 if(ptr->l == NULL) return; //leaf node
56 pic[i+1][j-1] = ‘/‘;
57 pic[i+1][j+1] = ‘\\‘;
58 DrawSubtree(ptr->l, i+2, sj);
59 DrawSubtree(ptr->r, i+2, j+1);
60 }
61 //print binary tree
62 void PrintTree(){
63 int h = dep*2+1, w = 1<<(dep+1);
64 int i, j;
65 //initialize pic[][]
66 pic = new char * [h];
67 for(i = 0 ; i < h; ++i){
68 pic[i] = new char[w];
69 for(j = 0; j < w; ++j)
70 pic[i][j] = ‘ ‘;
71 }
72 //draw nodes in pic[][]
73 DrawSubtree(root, 0, 0);
74 //don‘t print ending spaces
75 for(i = 0 ; i < h; ++i){
76 for(j = w-1; pic[i][j] == ‘ ‘; --j);
77 pic[i][j+1] = ‘\0‘;
78 printf("%s\n", pic[i]);
79 }
80 }
81
82
83 //print reverse Polish notation b[]
84 void PrintB(){
85 stack<char> st;
86 len = 0;
87 for(int i = 0; a[i]; ++i){
88 switch(a[i]){
89 case ‘(‘: st.push(a[i]); break;
90 case ‘)‘:
91 while((c = st.top()) != ‘(‘){
92 b[len++] = c;
93 st.pop();
94 }
95 st.pop(); break;
96 case ‘+‘:
97 case ‘-‘:
98 while(!st.empty() && (c = st.top()) != ‘(‘){
99 b[len++] = c;
100 st.pop();
101 }
102 st.push(a[i]); break;
103 case ‘*‘:
104 case ‘/‘:
105 while(!st.empty() && ((c = st.top()) == ‘*‘ || c == ‘/‘)){
106 b[len++] = c;
107 st.pop();
108 }
109 st.push(a[i]); break;
110 default: //variables
111 b[len++] = a[i];
112 }
113 }
114 while(!st.empty()){ //don‘t forget remaining symbols
115 b[len++] = st.top();
116 st.pop();
117 }
118 printf("%s\n", b);
119 }
120
121 //calculate t3 = t1 op t2
122 void Cal2Nums(char op){
123 int t1, t2, t3;
124 //t1 under t2, pop t2 first
125 t2 = st1.top(); st1.pop();
126 t1 = st1.top(); st1.pop();
127 switch(op){
128 case ‘+‘: t3 = t1 + t2; break;
129 case ‘-‘: t3 = t1 - t2; break;
130 case ‘*‘: t3 = t1 * t2; break;
131 case ‘/‘: t3 = t1 / t2; break;
132 default:
133 printf("Error in Cal2Nums\n!!");
134 exit(0);
135 }
136 st1.push(t3);
137 }
138 //calculate answer of b[]
139 void CalAns(){
140 for(int i = 0; b[i]; ++i){
141 if(b[i] >= ‘a‘ && b[i] <= ‘z‘)
142 st1.push(v[b[i]-‘a‘]);
143 else
144 Cal2Nums(b[i]);
145 }
146 printf("%d\n", st1.top());
147 st1.pop();
148 }
149
150
151 int main(){
152 cin >> a >> n;
153 for(int i = 0; i < n; ++i){
154 cin >> c >> t;
155 v[c-‘a‘] = t;
156 }
157 PrintB();
158 BiuldTree();
159 PrintTree();
160 DelTree(root);
161 CalAns();
162 return 0;
163 }
思路不难，就是麻烦，估计考试的时候写不完quq
再次没找到可在线测评的网址
奶牛Bessie设计了一个游戏：“愤怒的奶牛”。游戏的原型是：有一些可爆燃的草堆分布在一条数轴的不同坐标，玩家用弹弓把奶牛发射到数轴上。牛奶砸到数轴上的冲击波会引发附近的草堆燃爆，并有可能引起附近的草堆连环燃爆。游戏的目标是玩家用一些奶牛燃爆所有的草堆。 有N个草堆在数轴的不同位置，坐标为x1,x2,….,xn。如果玩家把奶牛发射到坐标是x，能量是R，就会引爆半径R以内的的草堆，即坐标范围[x-R, x+R]的草堆都会燃爆。 现在有K头奶牛，每头奶牛的能量都是R，请计算
7 2
20
25
18
8
10
3
1
5
1 # include <cstdio>
2 # include <algorithm>
3 using namespace std;
4
5 int N, K, x[50010];
6 int minr, maxr, midr;
7
8 int FindNext(int tmp, int r){
9 int i;
10 for(i = tmp; i < N && x[i] - x[tmp] <= (2*r); ++i);
11 return i;
12 }
13
14 int main(){
15 scanf("%d %d", &N, &K);
16 for(int i = 0;i < N; ++i)
17 scanf("%d", x + i);
18 sort(x, x + N);
19 minr = 0;
20 maxr = (x[N-1] - x[0] + 1) / (2 * K);
21 //use binary search to find r
22 while(minr < maxr){
23 midr = (minr + maxr) / 2;
24 int cnt = 0, tmp = 0;
25 while(tmp < N){
26 cnt++;
27 tmp = FindNext(tmp, midr);
28 }
29 if(cnt <= K) maxr = midr;
30 else minr = midr + 1;
31 }
32 printf("%d\n", minr);
33 return 0;
34 }
作为一个新广告项目的一部分，氪星的一家大公司打算把自己的logo在城市的某个地方展示。这家公司打算把这一整年的广告预算都花在这个大logo上，所以它将会非常非常的大。公司的一位高管打算使用整个建筑作为logo的一部分。
Logo由n个不同高度的柱子构成，从左到右编号为1到n。logo可以用编号1，2，……，n的一个排列（s1,s2...,sn)描述。其中s1代表最矮的柱子，s2是第二矮的，以此类推sn是最高的柱子。柱子的实际高度并不重要。
氪星的主干道旁有m栋建筑，很奇怪的是这些建筑的高度是不同的。现在的问题是找到所有可以与logo匹配的建筑的位置。
帮助公司找到建筑序列中所有可以与logo匹配的连续的部分，要求如下：s1最矮，s2是第二矮的，以此类推。例如一组建筑的高度为5，10，4和用排列（3，1，2）描述的logo是匹配的，因为3号建筑高为4，是最矮的，1号建筑是第二矮的而建筑2是最高的。
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
2
2 6
1 # include <cstdio>
2 # include <iostream>
3 # include <algorithm>
4 using namespace std;
5
6 int main(){
7 int n, m, * s, * h;
8 int tmp, cnt = 0, * ans;
9 bool f;
10 scanf("%d %d", &n, &m);
11 s = new int[n+2];
12 h = new int[m+2];
13 ans = new int[m-n+2];
14 for(int i = 0; i < n; ++i)
15 scanf("%d", s + i);
16 for(int i = 0; i < m; ++i)
17 scanf("%d", h + i);
18 for(int i = -1; i < m - n; ++i){
19 f = 1; //start from i is OK
20 tmp = h[i+s[0]]; //current height
21 for(int j = 1; j < n; ++j){
22 if(tmp >= h[i+s[j]])
23 { f = 0; break; }
24 else
25 tmp = h[i+s[j]];
26 }
27 if(f)
28 ans[cnt++] = i+2;
29 }
30 printf("%d\n", cnt);
31 for(int i = 0; i < cnt; ++i)
32 printf("%d ", ans[i]);
33 delete [] s;
34 delete [] h;
35 delete [] ans;
36 return 0;
37 }
太暴力了，没地方测试，但感觉会TLE... 毕竟去年考试只有14人通过orz
求快把题目放出来！
原文：https://www.cnblogs.com/tanshiyin-20001111/p/11923124.html