爱奇艺2020秋招笔试真题

1、切割块

【题目描述】有一个x*y*z的立方体，要在这个立方体上砍k刀，每一刀可以看作是用一个平行于立方体某一面的平面切割立方体，且必须在坐标为整数的位置切割，如在x=0.5处用平面切割是非法的。

问在切割k刀之后，最多可以把立方体切割成多少块。

输入描述

输入仅包含一行，一行包含4个正整数x,y,z,k分别表示x*y*z的立方体和切割k刀。（1<=x,y,z<=10^6,0<=k<=10^9）

输出描述

    输出仅包含一个正整数，即至多切割成多少块。

输入样例1

2 2 2 3

输出样例1

8

【解题思路】

由于必须按整数来切，所以

max块=x*y*z，实际就是体积的大小

max刀=(x-1)+(y-1)+(z-1)，就是保证切出来的==立方体体积最小=1==边长为3就要切2刀，2*2*2* 切3刀=8块，2*2*2* 切2刀=几块？

这需要在某一个边上少切一刀，是那一条边？（实践证明是最长的那条边）

【参考代码】

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a[5], k;
    long long int maxd, maxk, m = 104909296875;
    scanf("%d%d%d%d", &a[1], &a[2], &a[3], &k);
    //刀数
    maxd = (long long int)(a[1] - 1) + (a[2] - 1) + (a[3] - 1);
    //快数
    maxk = (long long int)a[1] * a[2] * a[3];
    // k超过刀数
    if (k >= maxd) {
        printf("%lld\n", maxk);
        return 0;
    } else
        while (maxd != k) {
            //找最长的那条边
            sort(a + 1, a + 4);
            //最长边减1
            a[3]--;
            //新的刀数和快数
            maxd = (long long int)(a[1] - 1) + (a[2] - 1) + (a[3] - 1);
            maxk = (long long int)a[1] * a[2] * a[3];
        }
    printf("%lld", maxk);
    return 0;
}

2、谁当裁判

【题目描述】假设有N个人要玩游戏，每轮游戏必须选出一个人当裁判，剩下的N-1个人作为玩家。现在第i个人要求作为玩家进行至少A_i轮游戏，那么至少需要进行多少轮游戏才能满足所有人的要求？

输入描述

第一行包含一个整数N，2≤N≤10⁵。

第二行包含N个空格隔开的整数A₁到A_N，0≤A_i≤10⁹。

输出描述

输出至少需要进行的游戏轮数。

输入样例

3
2 2 3

输出样例

4

【解题思路】

和值减去最大值即为答案。

【参考代码】

N=int(input().strip())
A=list(map(int,input().strip().split()))
print(sum(A)-max(A))

3、排列计数

【题目描述】给定一个大小为N-1且只包含0和1的序列A₁到A_N-1，如果一个1到N的排列P₁到P_N满足对于1≤i<N，当A_i=0时P_i<P_i+1，当A_i=1时P_i>P_i+1，则称该排列符合要求，那么有多少个符合要求的排列？

输入描述

第一行包含一个整数N，1<N≤1000。

第二行包含N-1个空格隔开的整数A₁到A_N-1，0≤A_i≤1。

输出描述

输出符合要求的排列个数对10⁹+7取模后的结果。

输入样例

4
1 1

输出样例

3

样例解释

符合要求的排列为{3 2 1 4}、{4 2 1 3}和{4 3 1 2}。

【解题思路】

根据数组中的值，对应dp即可。

【参考代码】

def main():
    mod = 1000000007
    N = int(input())
    flags = list(map(int, input().strip().split()))
    dp = [[0 for _ in range(N+1)] for _ in range(N)]
    for i in range(N):
        dp[0][i] = 1
 
    for i in range(1, N):
        if flags[i-1] == 1:
            for j in range(N-i-1, -1, -1):
                dp[i][j] += dp[i-1][j+1] + dp[i][j+1]