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

牛牛与玩偶

分析

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

时间复杂度

O(n)

参考代码

复制代码

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

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)

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

#include

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)

参考代码

复制代码

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

#include

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)

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

#include

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)

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

#include

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)

参考代码

复制代码

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

49

50

51

52

53

54

55

56

57

58

59

60

61

#include

using namespace std;

char s[505][5];

bool ok[505][505];

int root[505];

vector 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就好了。

参考代码

复制代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

#include

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;

}