瞎搞的机试复习

保研的事情令人头疼,还不知道能不能去自己心仪的学校,每天要复习一下机试,看着近期的比赛好像出了一些很有意思的点也不能去学,真的难受,只能硬着头皮复习其他的一些不感兴趣的知识,我太难了。。

格式问题

scanf函数输入的是字符串的时候,也就是”%s”的时候,变量前不需要加&;另外在%d之间插入数字来读取特定位数的数字的技巧有时候可以利用,比如%2d代表的是从这串数字串中获取两位数字出来。

printf函数使用的时候注意变量前不需要&,不然会输出地址,如果在某些输出小数需要保留多少位,则需要注意格式的串是这样的%.3lf,是在小数点后加上数字3

gets函数以回车结束。空格是可以读进去的,最好加上getchar()消除回车

排序类

这种题型一般使用C++内置的sort函数,根据题目使用自己构造的排序函数,一般有两种方法,一种是自定义cmp函数,另一种是直接在结构体里面运算符重载。好像对于堆这种数据结构有点不同。

nI0E9A.png

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
#include <bits/stdc++.h>

using namespace std;
struct Stu{
char name[20];
int age;
int score;
bool operator < (const Stu &A) const{
if(score != A.score) return score<A.score;
else if(!strcmp(name,A.name)) return strcmp(name,A.name)<0;
else return age<A.age;
}
}buff[100];


int main(){
int N;
while(scanf("%d",&N)!=EOF){
for(int i = 0; i< N; i++){
scanf("%s %d %d",buff[i].name,&buff[i].age,&buff[i].score);
}
sort(buff,buff+N);
for(int i = 0; i< N;i++){
printf("%s %d %d\n",buff[i].name,buff[i].age,buff[i].score);
}
}

return 0;
}

日期类

nI0UBT.png

最大的一个特点就是找一个统一起点,一般都是以0年1月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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;
#define ISYEARP(x) x % 4 == 0&& x%100 != 0 || x % 400 ==0 ?1:0

int day0fmonth[13][2]={
0,0,
31,31,
28,29,
31,31,
30,30,
31,31,
30,30,
31,31,
31,31,
30,30,
31,31,
30,30,
31,31,
};

struct Date{
int year;
int month;
int day;
void Nextday(){
day++;
if(day > day0fmonth[month][ISYEARP(year)]){
month++;
day = 1;
if(month > 12){
month = 1;
year++;
}
}
}
};

int buff[5001][13][32]; //最好放全局,不然有可能爆栈

char monthname[13][20] = {
"",
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December",
};

char weekname[7][20] = {
"Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday",
};



int main(){
Date tmp;
tmp.year = 0;
tmp.month = 1;
tmp.day = 1;
int cnt = 0;
while(tmp.year != 5000){
buff[tmp.year][tmp.month][tmp.day] = cnt++; //从第零天开始
tmp.Nextday();
}
int d,y,m;
char s[10];
while(scanf("%d %s %d",&d,s,&y)!=EOF){
for(int i = 1 ; i <= 12 ;i++){
if(strcmp(s,monthname[i]) == 0){
m = i;
break;
}
}
int count = buff[y][m][d] - buff[2019][9][16] + 1; //找一个周一好算
puts(weekname[(count % 7 + 7) %7]); //保证是非负数
}


return 0;
}

Hash的应用

当排序超过千万级别的时,可以使用Hash,这一类的题目都是在一个区间内的整数,且各不相同,如果涉及到负数可以使用偏移量去解决

nI0s3R.png

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
#include <bits/stdc++.h>

using namespace std;
#define OFFSET 500000
int Hash[1000001];



int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
for(int i = -500000; i <= 500000; i++){
Hash[i + OFFSET] = 0;
}
for(int i = 0; i < n; i++){
int x;
scanf("%d",&x);
Hash[x+OFFSET] += 1;
}

for(int i = 500000 ; i >= -500000; i--){
if(Hash[i+OFFSET] != 0){
while(Hash[i+OFFSET]){
printf("%d",i);
Hash[i+OFFSET] --;
m--;
if(m != 0) printf(" ");
else {
printf("\n");
break;
}
}
if( m == 0) break;
else continue;
}
}

}



return 0;
}

排版题

关键是推算出行之间的关系,每一行内容里面的关系,一般机试考的不多

nI0fED.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

int main(){
int n;
while(scanf("%d",&n)!=EOF){
int Maxline = n + (n - 1) *2;
for(int i = 1 ; i <= n; i++){
for(int j = 1 ; j <= Maxline ; j++){
if(j <= Maxline -(n + (i - 1) * 2))
printf(" ");
else
printf("*");
}
printf("\n");
}
}
return 0;
}

查找类

普通的数组遍历不用说,但在复杂度提升的情况下需要更高效的搜索方法,这里我们主要练习的还是二分搜索法,但我们需要注意的是使用二分搜索需要先进行排序,主要的二分搜索结构如下:

1
2
3
4
5
6
7
int base= 0, top = size;
while(base<=top){
int mid = (base+top)/2;
if(buff[mid] <= target) base = mid+1;
else top = mid -1;
}
int ans = buff[top];

nokrBF.png

noACNj.png

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
#include <bits/stdc++.h>

using namespace std;
struct Stu{
char num[4];
char name[7];
char sex[2];
int age;
bool operator < (const Stu &A) const{
return strcmp(num,A.num)<0;
}
}buff[1000];


int main(){
int N,M;
while(scanf("%d",&N)!=EOF){
for(int i = 0 ; i < N ;i ++){
scanf("%s %s %s %d",buff[i].num,buff[i].name,buff[i].sex,&buff[i].age);
}
sort(buff,buff+N);
scanf("%d",&M);
char find[4];
for(int i = 0 ; i< M; i++){
scanf("%s",find);
int base = 0, top = N-1;
int ans = -1;
while(base <= top){
int mid = (base+top)/2;
if(strcmp(find,buff[mid].num)==0){
ans = mid;
break;
}else if(strcmp(find,buff[mid].num)<0){
top = mid -1;
}else base = mid+1;
}
if(ans == -1) printf("No Answer!\n");
else printf("%s %s %s %d\n",buff[ans].num,buff[ans].name,buff[ans].sex,buff[ans].age);

}
}

return 0;
}

贪心类

这类题目的一个特点也是需要排序,可见排序的重要性,但是值得注意的是贪心发得到的结果不一定是最优解,可能是一个近似的最优解,这里见到了两种题,一种是固定钱数买最高价格的东西,另一种是固定时间看节目数最多的,反正本质是一样的,第一个是以单价作为排序标准,第二个是以结束时间作为排序标准

noK8Bt.png

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
#include <bits/stdc++.h>
using namespace std;

struct goods{
double price;
double mass;
double mass_one;
bool operator < (const goods &A) const{
return mass_one > A.mass_one;
}
}buff[100];


int main(){
double m;
int n;
while(scanf("%lf %d", &m, &n)!=EOF){
if(m == -1 && n == -1) break;
for(int i= 0 ;i < n; i++){
scanf("%lf %lf",&buff[i].mass,&buff[i].price);
buff[i].mass_one = buff[i].mass/buff[i].price;
}
sort(buff,buff+n);
int idx = 0;
double ans = 0;
while(idx < n && m > 0){
if(m > buff[idx].price){
ans += buff[idx].mass;
m -= buff[idx].price;
}else{
ans += m*buff[idx].mass_one;
m = 0;
}
++idx;
}
printf("%.3lf\n",ans);
}



return 0;
}

听说,打赏我的人最后都成了大佬。



文章目录
  1. 1. 格式问题
  2. 2. 排序类
  3. 3. 日期类
  4. 4. Hash的应用
  5. 5. 排版题
  6. 6. 查找类
  7. 7. 贪心类