牛客寒假算法基础集训(白给)营2象征性题解

本来这场是挺简单的,结果我被一个很水的模拟题卡到自闭,一直到最后都没能找出bug来,晚上在本地对拍也是全过,后来在lsr大佬的帮助下找到了程序的bug并且补了这题。


D 处女座与重修费

链接:https://ac.nowcoder.com/acm/contest/327/D

来源:牛客网

题目描述

期末考试结束了,处女座发现很多人挂了大物,只能等着第二年重修,还要交400元的重修费。处女座突然想起有个学长和他讲过,如果学校哪一年缺钱了,那一年的大物试卷就会特别难。现在处女座有了所有人的成绩,处女座想知道如果所有挂科的人都在第二年重修,学校能赚多少重修费?

挂科是指一门课的分数小于60分。

输入描述:

第一行一个整数n,表示考试的人数。
第二行n个整数,表示每个人的成绩。
1<=n<=10000
学生的成绩为0-100(包括0和100)之间的整数

输出描述:

一行,学校能赚的重修费用

示例1

输入

4
60
56
100
59

输出

800

真实签到题。统计一下里面有多少个60分以下然后有一个就+400就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 23333
using namespace std;
int n;
int a;
long long int ans = 0;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a;
if (a < 60)
ans += 400;
}
cout << ans;
return 0;
}

J 处女座的期末复习

链接:https://ac.nowcoder.com/acm/contest/327/J
来源:牛客网

题目描述

快要期末考试了,处女座现在有n门课程需要考试,每一门课程需要花ai小时进行复习,考试的起始时间为bi,处女座为了考试可以不吃饭不睡觉,处女座想知道他能否复习完所有的科目(即在每一门考试之前复习完该科目)。每一门课的考试时间都为两小时。

输入描述:

第一行一个整数n

第二行n个整数a1,a2,…,an,表示每门课需要复习的时间

第三行n个整数b1,b2,…,bn,表示每门课考试的时间

1<=n<=105

0<=ai<=109
0<=bi<=109

输出描述:

如果处女座能复习完,输出”YES”,否则输出”NO”

示例1

输入

3
0 1 1
2 6 4

输出

YES

说明

在0-1小时复习第2门课,

在1-2小时复习第3门课,

在2-4小时考第1门课,

在4-6小时考第3门课,

在6-8小时考第2门课

备注

考试时不能复习,保证考试时间不会重叠。

复习可以拆开,只要复习时间够了即可。

能搞懂这个时间轴这题就算解决了。我的思路和正解不太一样。根据一个显然的策略,哪场先考就先复习哪场,可以考虑把每一门课做成一个结构体,然后按照考试时间顺序排序。这样可以得到一个考试安排的时间轴,类似上图。对于任何一门考试,其有效的复习时间是它之前的时间段。假设现在要准备考试A,那么对于考试A的准备时间就是A考试前面的那一段。如果这一段时间无法满足复习时间要求那显然就直接不可以了。假设这里是满足的并且还有时间剩余,那么就是上图的情况,用去了绿色的一段,剩下黄色的一段,这段时间就可以留着准备B考试。对于A考试后续的所有考试,假设目前考虑到第i场考试,这场考试可以用来准备时间一定是等于第i-1场考试与第i场考试间隔的时间加上准备第i-1场考试用剩下的时间。准确的说,是从第1场到第i-1场省下的所有时间。那么就可以滚动地记录之前的剩余时间,每次循环到第i场考试再计算一下当前的空余时间,两者相加就是可以用来准备第i场考试的时间,将这个时间与所需复习时间进行比对,如果可以复习完则将这些时间全部当作“之前剩下的时间”,并且减去当前所用的复习时间,然后去考虑第i+1场考试,如果中间任何一场考试的复习时间出现问题,就立即输出NO。可以证明这个思路是正确且最优的。

那为什么我卡了三个多小时呢?原因出在下面。

我在考虑问题的时候特殊判断了一下复习时间为0的情况,我当时认为如果复习时间为0,那么这一科的复习就可以完全不用管。看似正确,但是按照上面的理论,我忘记了一点:当复习时间为0时,复习下一场考试所剩余的时间仍然可能会更新。但是我并没有这么做,而是直接在复习时间为0时continue了,这样就导致了迷之WA,对拍都检测不出来那种。。

最终代码:

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
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 233333
#define debug cout << "ok" << endl;
using namespace std;
struct lesson {
long long int fx;
long long int ks;
bool operator<(const lesson &rhs)const {
return ks < rhs.ks;
}
};
lesson a[maxn];
long long int n;
long long int used = 0;
bool fail = false;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].fx;
}
for (int i = 1; i <= n; i++) {
cin >> a[i].ks;
}
sort(a + 1, a + n + 1);
long long int last_remain = 0;
if (a[1].fx != 0) { // the first
if (a[1].ks < a[1].fx)
fail = true;
}
last_remain = a[1].ks - a[1].fx;
if (!fail) {
for (int i = 2; i <= n; i++) {
// fx time bushi 0
long long int now_remain = a[i].ks - a[i - 1].ks - 2;
last_remain += now_remain;
if (last_remain >= a[i].fx) {
last_remain -= a[i].fx;
}
else {
fail = true;
break;
}
}
}

if (fail)
cout << "NO";
else
cout << "YES";
return 0;
}

B 处女座与cf

链接:https://ac.nowcoder.com/acm/contest/327/B

来源:牛客网

题目描述

众所周知,处女座经常通过打cf来调节自己的心情。今天处女座又参加了一场cf的比赛,他知道了所有的提交记录,他想知道自己的得分和排在第几名。你知道处女座的cf账号是cnz

Codeforces规则如下:

  1. 比赛一共2小时
  1. 比赛有5题,A题500分,B题1000分,C题1500分,D题2000分,E题2500分。
  1. 得分规则如下:

在第0分钟完成某一题可以得到全部的分数,每过一分钟每题的分值会衰减1/250,比如在第3分钟完成A题,能够得到500-2*3=494分

  1. 如果一道题是的返回结果WA或者TLE被称为错误的提交,CE视为无效的提交,AC,WA和TLE 都视为有效的提交。如果一道题你最后通过了,你会得到这道题衰减之后的分值再减去你错误提交次数*50,就是每次错误的提交会有50分的罚时。
  1. 如果你通过了一道题,你的得分不会低于该题分值的30%。比如你在第50分钟通过了A,你有7次错误的提交,你的得分为max(500×0.3,500-2×50(得分衰减)-7×50(错误提交的罚时))=150分。
  1. 由于hack机制的存在,你每进行一次提交,对于这一题之前的有效提交(AC,WA,TLE)都视为错误的提交。
  1. 一个人只有提交(AC,WA,TLE,CE)过代码,才被视为参加比赛。

处女座又了解到一些信息:

本场比赛没有任何选手hack别人,并且没有任何的提交fst(即只要是某题的最后一次提交通过,就视为通过这道题)

输入描述:

第一行两个整数n和m,n为报名比赛的人数,m为提交的个数

接下来n行,每行一个字符串,表示报名比赛的人的昵称。(字符串只包含小写字母,且长度小于20)

接下来m行,每行的格式为Time,Submiter,Problem,Verdict。

Time为提交的时间,是1到120中的一个正整数(包含1和120),保证Time按顺序给出

Submiter为提交者昵称

Problem为题目名称,是’A’,’B’,’C’,’D’,’E’中的一个字母。

Verdict为返回的结果,为”AC”,”WA”,”TLE”,”CE”中的一个。

2<=n<=500

1<=m<=10000

输出描述:

如果处女座参加了比赛,输出两行:

第一行为处女座的得分

第二行格式x/y,其中x为处女座的排名,y为参加比赛的总人数。如果分> 数相同那么排名并列。

如果处女座没有参加比赛,输出”-1”

示例1

输入

3 7
cnz
cuber
moon
3 cnz A AC
5 cuber A AC
6 cnz B CE
10 cuber C AC
20 cnz B AC
30 cuber D TLE
100 cnz E AC

输出

2914
1/2

真实巨型模拟题。情况很多很复杂,我尽量写的能让大家看懂一点。

upd:
写了一整个下午。。我都快要吐了。。

目前思路应该是没问题的,输出上出了点小毛病。。

根据输入的数据先判断cnz有没有参赛,如果cnz没有参赛就输出-1,参赛了就对下边的输入数据进行处理,根据输入的内容判断此人这题应该是计罚时,还是AC后计成绩,还是CE代表无效提交,但是无论如何这都算是这个人参过赛的,最后要计算的时候我是使用了vector保存实际参赛的人,然后进行排序并且输出。

代码比较长。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#define MAXN 23333
#define FAIL -1
#define SUCCESS 1
#define SUBMITER 1
#define PROBLEM 2
#define PROBLEM_A 500
#define PROBLEM_B 1000
#define PROBLEM_C 1500
#define PROBLEM_D 2000
#define PROBLEM_E 2500

#define debug cout << "ok" << endl;
using namespace std;

struct submiterStatus {
string coderName;
bool isJoinContest;
int fashi_A, fashi_B, fashi_C, fashi_D, fashi_E;
int finalScore;

bool operator<(const submiterStatus &rhs)const {
return finalScore > rhs.finalScore;
}
};

submiterStatus submitStatus[MAXN];
int signUpUsersNnumber;
int submitStatusNumber;
bool isCnzSignUp;

int calcProblemScore(string problemId, int fashi, int time) {
int calcAns = -1;
if (problemId == "A") {
calcAns = max((int)(PROBLEM_A * 0.3), PROBLEM_A - (time * PROBLEM_A / 250) - fashi * 50);
}
else if (problemId == "B") {
calcAns = max((int)(PROBLEM_B * 0.3), PROBLEM_B - (time * PROBLEM_B / 250) - fashi * 50);
}
else if (problemId == "C") {
calcAns = max((int)(PROBLEM_C * 0.3), PROBLEM_C - (time * PROBLEM_C / 250) - fashi * 50);
}
else if (problemId == "D") {
calcAns = max((int)(PROBLEM_D * 0.3), PROBLEM_D - (time * PROBLEM_D / 250) - fashi * 50);
}
else if (problemId == "E") {
calcAns = max((int)(PROBLEM_E * 0.3), PROBLEM_E - (time * PROBLEM_E / 250) - fashi * 50);
}
return calcAns;
}

int getSubmiterNum(string name) {
for (int index = 1; index <= signUpUsersNnumber; index++) {
if (submitStatus[index].coderName == name)
return index;
}
return FAIL;
}

// --------------------------------- //

void handleSubmissions(int index, int time, string submiter, string problem, string verdict) {
int submiterId = getSubmiterNum(submiter);
//说明此人已参赛
submitStatus[submiterId].isJoinContest = true;
if (verdict == "WA" || verdict == "TLE") {
//这两种情况是错误的有效提交,应当记录相应题目的罚时
if (problem == "A") {
submitStatus[submiterId].fashi_A++;
}
else if (problem == "B") {
submitStatus[submiterId].fashi_B++;
}
else if (problem == "C") {
submitStatus[submiterId].fashi_C++;
}
else if (problem == "D") {
submitStatus[submiterId].fashi_D++;
}
else if (problem == "E") {
submitStatus[submiterId].fashi_E++;
}
}
else if (verdict == "AC") {
//这种情况是正确的有效提交,应当根据相应状态记录分数
if (problem == "A") {
submitStatus[submiterId].finalScore += calcProblemScore(problem, submitStatus[index].fashi_A, time);
}
else if (problem == "B") {
submitStatus[submiterId].finalScore += calcProblemScore(problem, submitStatus[index].fashi_B, time);
}
else if (problem == "C") {
submitStatus[submiterId].finalScore += calcProblemScore(problem, submitStatus[index].fashi_C, time);
}
else if (problem == "D") {
submitStatus[submiterId].finalScore += calcProblemScore(problem, submitStatus[index].fashi_D, time);
}
else if (problem == "E") {
submitStatus[submiterId].finalScore += calcProblemScore(problem, submitStatus[index].fashi_E, time);
}
}
}

void initDataStructure() {
isCnzSignUp = false;
for (int index = 1; index <= signUpUsersNnumber; index++) {
submitStatus[index].fashi_A = 0;
submitStatus[index].fashi_B = 0;
submitStatus[index].fashi_C = 0;
submitStatus[index].fashi_D = 0;
submitStatus[index].fashi_E = 0;
submitStatus[index].finalScore = 0;
submitStatus[index].isJoinContest = false;
}
}

void inputDataStructure(int mode) {
if (mode == SUBMITER) {
cin >> signUpUsersNnumber >> submitStatusNumber;
for (int index = 1; index <= signUpUsersNnumber; index++) {
cin >> submitStatus[index].coderName;
if (submitStatus[index].coderName == "cnz")
isCnzSignUp = true;
}
}
else if (mode == PROBLEM) {
int Time;
string Submiter, Problem, Verdict;
for (int index = 1; index <= submitStatusNumber; index++) {
cin >> Time >> Submiter >> Problem >> Verdict;
handleSubmissions(index, Time, Submiter, Problem, Verdict);
}
}
}

void outputTheAnswer(int status) {
if (status == FAIL) {
cout << "-1" << endl;
}
else if (status == SUCCESS) {
//该分支有bug
vector<submiterStatus> actualSubmiters;
actualSubmiters.clear();
for (int index = 1; index <= signUpUsersNnumber; index++) {
if (submitStatus[index].isJoinContest == true) {
actualSubmiters.push_back(submitStatus[index]);
}
}
int actualSubmitersNum = actualSubmiters.size();
sort(actualSubmiters.begin(), actualSubmiters.end());
int indexCnt = 1;
for (int vindex = 0; vindex < actualSubmitersNum; vindex++) {
if (actualSubmiters[vindex].coderName == "cnz") {
cout << actualSubmiters[vindex].finalScore << endl;
cout << indexCnt << "/";
break;
}
indexCnt++;
}
cout << actualSubmitersNum << endl;
}
}

int main() {
ios::sync_with_stdio(false);
initDataStructure();
inputDataStructure(SUBMITER);
if (isCnzSignUp == false) {
outputTheAnswer(FAIL);
}
else {
inputDataStructure(PROBLEM);
outputTheAnswer(SUCCESS);
}
system("pause");
return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:牛客寒假算法基础集训(白给)营2象征性题解

文章作者:Shawn Zhou

发布时间:2019年01月25日 - 11:01

最后更新:2019年01月25日 - 20:01

原始链接:http://shawnzhou.xyz/2019/01/25/19-01-25-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%