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

A-面试

提交记录：45258014

思路

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

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。

可以写出如下代码

if(cntd || cntc >= 2) {
    cout << "failed" << endl;
}
else if(!cntd && cnta >= 3) {
    cout << "sp offer" << endl;
}
else {
    cout << "offer" << endl;
}

代码

#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

代码

#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;
}

参考资料

• 7606B 纸牌游戏题解 - wzkdh 的牛客博客

C-涨薪

提交记录： 45259535

思路

分析

• 当 $m \geq 2$ 时，会有 $n-(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 = 1$ 时，没有员工被开除，需要计算以下内容：

$$\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(n \log m)$ 的复杂度。

代码模板

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

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

代码

#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;
}

参考资料

• 模意义下取幂 - 快速幂 - OI Wiki

D-变换

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