爱奇艺2018春季校招笔试编程题参考代码

牛牛与玩偶

分析

根据题意，只会有两种重量的玩偶，对于每一种重量，维护该重量的玩偶总数和最后一个该重量玩偶的序号，最后找到数量为1的那种玩偶对应的序号就可以了。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>
using namespace std;

int w[1000005];
int main() {
    int n;
    int w1, w2, num1 = 0, num2 = 0, ans1, ans2;
    scanf("%d", &n);
    scanf("%d", &w[1]);
    w1 = w[1];
    num1 = 1;
    ans1 = 1;
    for(int i = 2; i <= n; i++) {
        scanf("%d", &w[i]);
        if(w[i] == w1) {
            num1++;
            ans1 = i;
        } else {
            w2 = w[i];
            num2++;
            ans2 = i;
        }
    }
    if(num1 == 1)
        printf("%d\n", ans1);
    else
        printf("%d\n", ans2);
    return 0;
}

彩色队伍

分析

挨着扫一遍, 统计当前字符跟前一个字符不同的个数。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    int cnt = 0;
    for(int i = 1; i < s.size(); i++) {
        if(s[i - 1] == s[i]) {
            cnt++;
            i++;
        }
    }
    cout << cnt << endl;
    return 0;
}

牛牛学洗牌

分析

按照题目所说的，每一次把前Xi张牌和剩下的牌分开，再一张一张从两叠牌轮流放回去即可。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>
using namespace std;

int a[15];
int temp[2][15];
int len[2];

int main() {
    int n;
    bool f;
    for(int i = 1; i <= 13; i++) scanf("%d", &a[i]);
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &len[0]);
        len[1] = 13 - len[0];
        for(int i = 1; i <= len[0]; i++) temp[0][i] = a[i];
        for(int i = 1; i <= len[1]; i++) temp[1][i] = a[i + len[0]];
        f = 0;
        for(int i = 13; i >= 1; i--) {
            if(len[f] == 0) f=!f;
            a[i] = temp[f][len[f]];
            len[f]--;
            f = !f;
        }
    }
    for(int i = 1; i <= 13; i++) {
        printf("%d", a[i]);
        if(i == 13)
            printf("\n");
        else
            printf(" ");
    }
    return 0;
}

三个整数

分析

设X为最后三个数都变为的数。
所以总共需要的操作次数为(3X - (A + B + C)) / 2。注意到X肯定大于等于A, B, C三个数的最大值, 我们现在要最小化X, 并且两个操作都不改变A + B + C的奇偶性。
设A, B, C的最大值为Ma = max(A, max(B, C))
所以3 Ma与 A + B + C相同奇偶性的话, X = Ma, 否则X = Ma + 1。
然后输出(3Ma - (A + B + C)) / 2即可。

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if ((a[2] - a[1] + a[2] - a[0]) % 2 == 0)
        cout << (a[2] - a[1] + a[2] - a[0]) / 2;
    else
        cout << (a[2] - a[1] + a[2] - a[0] + 3) / 2;
    return 0;
}

字典序最大子序列

分析

贪心。每次取当前剩余字典序最大的字符。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    ostringstream ss;
    while(!s.empty()) {
        string::iterator it = max_element(s.begin(), s.end());
        ss << *it;
        s.erase(s.begin(), it + 1);
    }
    cout << ss.str() << endl;
    return 0;
}

牛牛配点心

分析

合法的点心盒一共有三种：一甜一苦一酸/两甜一苦(酸)/三甜。

为了最大化点心盒的数量，我们肯定是优先组成第一种点心盒，再考虑第二种点心盒，最后剩下的甜点心每三个组成一个点心盒。

于是问题转化为，最多能同时组成多少对一苦一酸的点心，并且每对点心都不冲突。
我们可以借助二分图匹配的模型，考虑在任意一对个不冲突且一苦一酸的点心之间连一条边，然后求最大匹配。
最后根据最大匹配的数量、多余的苦(酸)点心的数量、和甜点心的数量算出答案。

时间复杂度

O(n^3)

参考代码

#include <bits/stdc++.h>
using namespace std;

char s[505][5];
bool ok[505][505];
int root[505];
vector <int> vec[505];
bool life[505];

bool solve(int x) {
    life[x] = 1;
    for(int i = 0; i < vec[x].size(); i++) {
        if(life[vec[x][i]])
            continue;
        else
            life[vec[x][i]] = 1;
        if(!root[vec[x][i]] || solve(root[vec[x][i]])) {
            root[vec[x][i]] = x;
            return 1;
        }
    }
    return 0;
}
int main() {
    int n, m, u, v;
    int numdl = 0, numdc = 0, numds = 0, ans = 0;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%s", s[i]);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        ok[u][v] = 1;
        ok[v][u] = 1;
    }
    for(int i = 1; i <= n; i++) {
        if(s[i][0] == 'K') {
            numdc++;
            for(int j = 1; j <= n; j++) {
                if(s[j][0] == 'S' && !ok[i][j])
                    vec[i].push_back(j);
            }
        } else {
            if(s[i][0] == 'T') numdl++;
            else numds++;

        }
    }
    for(int i = 1; i <= n; i++) {
        memset(life, 0, sizeof(life));
        if(s[i][1] == 'C' && solve(i)) ans++;  
    }
    if(ans >= numdl)
        printf("%d\n", numdl);
    else
    {
        if((numdl - ans) / 2 >= (numdc + numds - ans * 2))
            printf("%d\n", numdc + numds - ans + (numdl - ans - (numdc + numds - ans * 2) * 2) / 3);
        else
            printf("%d\n", ans + (numdl - ans) / 2);
    }
    return 0;
}

牛牛配糖果

分析

可以通过母函数求解或者直接用背包dp就好了。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long f[2][105];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        memset(f[i & 1], 0, sizeof(f[i & 1]));
        int l, r;
        scanf("%d%d", &l, &r);
        for (int k = l; k <= r; k++)
            for (int j = m; j >= k; j--)
                f[i & 1][j] += f[i + 1 & 1][j - k];
    }
    printf("%lld\n", f[n & 1][m]);
    return 0;
}