Skip to content

牛客网 - 7606. 2020 牛客 NOIP 赛前集训营 - 普及组(第二场)

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#A-面试

提交记录:45258014

#思路

统计 A B C D 四个字母的出现次数。

1
2
3
4
5
6
for(int i = 0 ; i < 4 ; i++) {
if(s[i] == 'A') cnta++;
else if(s[i] == 'B') cntb++;
else if(s[i] == 'C') cntc++;
else if(s[i] == 'D') cntd++;
}

根据题目中所描述的内容:

如果面试者在四轮中有一次发挥被评为 D,或者两次发挥被评为 C,就不会通过面试。如果面试者没有一次被评为 D,并且有三个或以上的 A,则会获得 special offer。其余情况会获得普通 offer。

可以写出如下代码

1
2
3
4
5
6
7
8
9
if(cntd || cntc >= 2) {
cout << "failed" << endl;
}
else if(!cntd && cnta >= 3) {
cout << "sp offer" << endl;
}
else {
cout << "offer" << endl;
}

#代码

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;

int main() {
int t, cnta, cntb, cntc, cntd;
string s;
cin >> t;
while(t--) {
cnta = cntb = cntc = cntd = 0;
cin >> s;
for(int i = 0 ; i < 4 ; i++) {
if(s[i] == 'A') cnta++;
else if(s[i] == 'B') cntb++;
else if(s[i] == 'C') cntc++;
else if(s[i] == 'D') cntd++;
}
if(cntd || cntc >= 2) {
cout << "failed" << endl;
}
else if(!cntd && cnta >= 3) {
cout << "sp offer" << endl;
}
else {
cout << "offer" << endl;
}
}
return 0;
}

#B-纸牌游戏

提交记录:45267496

#代码

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

using namespace std;

int main() {
int n, a[100010];
cin >> n;
for(int i = 0 ; i < n ; i++) {
cin >> a[i];
}
sort(a, a+n);
for(int i = 0 ; i < n ; i++) {
if(a[i] >= n-i-1) {
cout << n-i << endl;
return 0;
}
}
return 0;
}

#参考资料

#C-涨薪

提交记录: 45259535

#思路

#分析

  • m2m \geq 2 时,会有 n(x+y)n-(x+y) 名员工被辞退,需要计算以下内容:

{ai×3m(0i<x)ai×2m(xi<x+y)\left\{\begin{array}{lc}a_i\times 3^m&(0\leq i<x)\\ a_i\times 2^m&(x \leq i < x+y) \end{array}\right.

  • m=1m = 1 时,没有员工被开除,需要计算以下内容:

{ai×3(0i<x)ai×2(xi<x+y)ai(x+yi<n)\left\{\begin{array}{lc}a_i\times 3&(0\leq i<x)\\ a_i\times 2&(x \leq i < x+y)\\ a_i&(x+y \leq i < n) \end{array}\right.

如果纯暴力的话复杂度是 O(nm)O(nm) 所以用快速幂优化下,就变成了 O(nlogm)O(n \log m) 的复杂度。

#代码模板

快速幂板子(带 mod 版本):

1
2
3
4
5
6
7
8
9
10
11
long long binpow(long long a, long long b, long long mod) {
a %= mod;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

#代码

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

using namespace std;

const int mod = 1e9 + 7;

bool cmp(int a, int b) {
return a > b;
}

long long binpow(long long a, long long b) {
a %= mod;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

int main() {
long long n, m, x, y, a[100005], ans = 0;
cin >> n >> m >> x >> y;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n, cmp);
for (int j = 0; j < x; j++) {
a[j] *= binpow(3, m);
}
for (int j = x; j < x + y; j++) {
a[j] *= binpow(2, m);
}
for (int i = 0; i < x + y; i++) {
ans += a[i];
ans %= mod;
}
if (m < 2) {
for (int i = x + y; i < n; i++) {
ans += a[i];
ans %= mod;
}
}
cout << ans << endl;
return 0;
}

#参考资料

#D-变换

这道题没做出来,比赛结束后官方题解没看懂,待填坑。