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

参考资料

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版本):

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

参考资料

D-变换

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