Skip to content

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

题解969 字
# 数学 # 模拟 # 牛客网 # 比赛
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#A-面试

提交记录：45258014

#思路

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

C++
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。

可以写出如下代码

C++
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;
}

#代码

C++
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

#代码

C++
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

#思路

#分析

  • 当 m≥2m \geq 2 时，会有 n−(x+y)n-(x+y) 名员工被辞退，需要计算以下内容：

{ai×3m(0≤i<x)ai×2m(x≤i<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(0≤i<x)ai×2(x≤i<x+y)ai(x+y≤i<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(nlog⁡m)O(n \log m) 的复杂度。

#代码模板

快速幂板子（带 mod 版本）：

C++
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;
}

#代码

C++
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-变换

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