牛客寒假算法基础集训(白给)营6题解(完结撒花)

最后一场,题目相对于前几场来说简单了不少,但是仍然白给。。

先%奆佬mxl学姐一波,最后一场以7题成绩喜提校榜Rank1 Orz


A 出题

原题:https://ac.nowcoder.com/acm/contest/332/A

坑点:无解不好判断,第一次判断很可能只能找到一半的条件

这道题在思索暴力构造无果下,无奈选择了推公式,以下列出推导过程:

已知的是小B共出了m道题,共n分,设六分题,七分题,八分题,九分题的数量分别为a,b,c,d,那么有下面的四元一次方程组成立:


a + b + c + d = m ①

6a + 7b + 8c + 9d = n ②

这里a,b,c,d可以取范围内任意正整数值。既然要求六分题的数量,我们就要试图把a求出来。这里使用消元法将两个式子合并。

①式变形,得


b = m - a - c - d ③

将③式代入②式,有


6a + 7(m - a - c - d) + 8c + 9d = n

整理,得


a = 7m - n + φ,其中φ = c + 2d

然后比赛中的我就懵掉了,这怎么还带个常数呢。。。

然后大胆猜想常数为0,答案就是7m-n,就对了……

此处有一细节,由于数据问题,7m-n并不一定是正数。如果它是非正数,则表明题目的分数的平均值大于等于7,即此时一定不存在6分题,所以答案是0。

最后在最前面加上无解判断就好。求一个平均值,如果它不位于6和9之间一定无解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 2333
using namespace std;
int main() {
ios::sync_with_stdio(false);
long long n,m;
cin >> n >> m;
long double avar = (long double)n / m;
if(avar < 6 || avar > 9)
cout << "jgzjgzjgz";
else {
long long ans = 7*m-n;
if(ans <= 0)
cout << 0;
else
cout << ans;
}
}

B 煤气灶

原题:https://ac.nowcoder.com/acm/contest/332/B

题外话(大雾):

本题的初衷应该不是让你用暴力过的,结果我真的用暴力过了这题。。。。虽然后面被告知会被hack。。。

那个可能没用的x就别管他了……开两个变量分别记录当天工资和已拥有总工资,然后叠叠叠叠叠叠。。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 23333
using namespace std;
long long int n,m,d,x;

int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> d >> x;
long long int ans = 1;
long long int sum = n;
while (sum < m) {
ans++;
n += d;
sum += n;
}
cout << ans << endl;
return 0;
}

C 项链

原题:https://ac.nowcoder.com/acm/contest/332/C

简单的贪心。题目可以等价于下面的这个情况:已知一个不递增的序列a,现在让你在里面取一个连续的长度为n的子序列,使序列和最大。

显然,这个子序列应该是选择的值越大,总和越大。下面是一个例子。

那么就可以对颜料按照喜爱度进行排序,然后依次选取。注意判断珠子不够的情况。

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 <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 233333
using namespace std;
struct color {
int remain;
int val;
bool operator<(const color &rhs)const {
return val > rhs.val;
}
};

color a[maxn];
int n,m;

int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i=1;i<=m;i++)
cin >> a[i].remain;
for (int i=1;i<=m;i++)
cin >> a[i].val;
sort(a+1,a+m+1);
long long int ans = 0;

for (int i=1;i<=m;i++) {
if (n == 0)
break;
else if (n > a[i].remain) {
n -= a[i].remain;
ans += a[i].val * a[i].remain;
}
else if (n < a[i].remain) {
ans += a[i].val * n;
n = 0;
}
}
cout << ans << endl;
return 0;
}

D 美食

原题:https://ac.nowcoder.com/acm/contest/332/D

这道题思路极其巧妙,说是贪心还不是单纯的贪心——需要吐槽一下,样例解释存在一些误导。

最早我的思路是这样,把美食按两个两个一对进行“分组”,然后判断两者是不是相等,相等则怎么吃步数都一样,直接统计答案。如果不等,则相等部分步数一样,多出来的部分单独处理。这样对于当前这两盘的较多一盘,最后应该是全吃完或者剩下一个1。

但是这个方法交上去之后并没有AC,说明方法是错误的。于是我开始思考有没有更多的步数。想一下,这个方法中间应该是没有再优化的可能,于是我开始思考这样吃完后的残局:最后的美食应该会变成0010100100101001010这样,仍然存在比较多的1,我想,这些1有没有可能整合在一起吃呢?

于是想到了正解:光盘行动。贪心策略改成“直到这一盘不能再吃为止,绝不动下一盘”。然后关键在下面这句:如果吃下一盘时上一盘有剩余,则第一口应该把之前剩的吃掉。这样做可以保证,如果上一盘有剩余,则它会被“转移”到下一盘,或者随着下一盘正好吃光。

这样做,除了上来就没得吃的10101这种奇葩数据,最后的结果应该是00000001这样。这样就能保证了最小的浪费,从而有最大的次数。

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
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 233333
#define debug cout << "ok" << endl;
using namespace std;
int n;
int a[maxn];
int main() {
ios::sync_with_stdio(false);
cin >> n;
long long int ans = 0;
for (int i=1;i<=n;i++){
cin >> a[i];
if (a[i-1] == 1 && a[i] > 0) {
a[i-1] = 0;
a[i]--;
ans++;
}
ans += a[i] / 2;
a[i] %= 2;

}
cout << ans << endl;
return 0;
}

I wzoi

原题:https://ac.nowcoder.com/acm/contest/332/I

原来看着感觉挺难的,后来仔细一分析发现这还是个贪心,而且需要用到栈。

要让得分尽量大,那就要让10分尽量的多。那就是让今天写的题和最近一次看的题类型相等。那怎么去记录这个“最近一次”的状态?栈顶啊!栈顶每次进来的都是新数据在顶上。

最后判断一下是不是整个序列都能这么做,如果不行那就是还有散落的5分题,统计一下就好。

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
#include <iostream>
#include <cstdio>
#include <stack>
#include <string>
using namespace std;

stack<char> st;
string a;
long long int sum = 0;
long long int ans = 0;
int main() {
ios::sync_with_stdio(false);
cin >> a;
int l = a.length();
for (int i = 0; i < l; i++) {
if (!st.empty() && a[i] == st.top()) {
sum++;
ans += 10;
st.pop();
}
else {
st.push(a[i]);
}
}
if (sum * 2 == a.size()) {
cout << ans << endl;
}
else
cout << ans + (a.size() / 2 - sum) * 5 << endl;
system("pause");
return 0;
}

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


本文标题:牛客寒假算法基础集训(白给)营6题解(完结撒花)

文章作者:Shawn Zhou

发布时间:2019年02月02日 - 18:02

最后更新:2019年02月03日 - 19:02

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

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

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