记三道2020年某企业秋招笔试题

 Algorithm
 

1 ~ n 中每位数字乘积最大的值

  • 描述：

99°是一位爱好爬山的小青年，他每次在爬山过程中都会遇到很多小猴子，小猴子们喜欢向他提这样一种问题：在1 ~ n中找一个数字m，使得m的各个数位乘积最大。99°不擅长回答这种问题，你能帮他写一个程序得到结果吗？

  • 样例输入1：

100

  • 样例输出1：

81

提示：9 * 9 = 81

  • 样例输入2：

6

  • 样例输出2：

6

  • 解题思路：贪心

    • 尽量把每一位变成9，每次都向前借一位来减
    • n比10小就返回n，n为0就返回1

  • 参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll solve(int n) {
    if(n==0) return 1;
    if(n<10) return n;
    else return max(solve(n/10-1)*9,solve(n/10)*(n%10));
}

int main() {
    int n;
    scanf("%d",&n);
    printf("%lld",solve(n));
    return 0;
}

完成可能有前置任务的任务

  • 描述：

99°要完成n个任务，它制定了一个计划，计划第i天完成第i个任务，每个任务可能有前置任务，在完成第i个任务时，必须先完成它的前置任务才行。问99°要想实现它的计划，每天至少要完成多少个任务？

  • 输入：

一个整数n，表示要完成的任务数，2<=n<=10000。接下来n行，每行第一个数字k表示该任务的前置任务数，剩下的k个数字分别表示前置任务编号。

  • 输出：

n个数字，每个数字以一个空格间隔，表示每天至少完成的任务数。

  • 样例输入：

3
1 2
0
2 1 2

  • 样例输出：

2 0 1

说明：任务1有1个前置任务2，第1天要想完成任务1，需先完成任务2，所以第1天至少完成2个任务。第2天计划完成任务2，因为任务2已在第一天完成，且任务2无前置任务，所以第2天至少完成0个任务。第3天计划完成任务3，任务3有两个前置任务1、2，在前两天都已完成，所以这一天只需完成任务3，至少完成1个任务即可。

  • 样例输入：

5
4 2 3 4 5
1 1
2 1 2
0
1 3

  • 样例输出：

5 0 0 0 0

说明：第1个任务有4个前置任务2、3、4、5，要想完成1，需先完成2、3、4、5，那么第1天至少完成5个任务。接下来的第2、3、4、5天每天完成0个任务，因为在第1天已完成全部5个任务。

  • 解题思路：开哈希数组

  • 参考程序：

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
#include<bits/stdc++.h>
using namespace std;

const int N=10005;
int n,res[N],v[N];

int main() {
    int k,x;
    memset(res,0,sizeof res);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&k);
        while(k--) {
            scanf("%d",&x);
            if(!v[x]) {
                v[x]=1;
                res[i]++;
            }
        }
        if(!v[i]) {
            res[i]++;
            v[i]=1;
        }
    }
    for(int i=1;i<=n;i++) {
        printf("%d ",res[i]);
    }
    printf("\n");
    return 0;
}

将数组元素变为非递减

  • 描述

99°给出一个包含$n$个整数的数组$a_i$，99°每次可以选择数组中若干个下标不同的元素，对选中的每个元素执行下列改变：假设选中的元素为$x$，那么就将$x$替换为$(x+1) mod m$，即选中的每个元素自增1，如果变为$m$则归零。
请问最少执行多少次操作，99°可以把这个数组变为一个数组元素非递减的数组。

  • 输入：

第一行两个整数$n$和$m$，用一个空格分隔；
第二行$n$个整数$a_1$,$a_2$,…,$a_n$表示数组，每两个整数之间用一个空格分隔。
输入满足$1<=n,m<=300000;0 <= a_i < m$ 。

  • 输出：

一个整数，表示最少需要的操作次数。

  • 输入样例1：

6 8
7 5 6 3 2 1

  • 输出样例1：

3

  • 输入样例2：

3 2
1 0 1

  • 输出样例2：

1

  • 输入样例3：

3 2
1 0 0

  • 输出样例3：

1

  • 解题思路：线性dp

  • 参考程序：

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
#include<bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f
const int N=300005;
int n,m,a[N],dp[N];

inline int move(int i,int j) {
    int ans=j-a[i];
    if(a[i]>j) ans+=m;
    return ans;
}

int main() {
    int t,ans=INF;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<m;i++)   //初始化dp数组
        dp[i]=move(0,i);
    for(int i=1;i<n;i++) {
        t=dp[0];
        for(int j=0;j<m;j++) {
            t=min(t,dp[j]);
            dp[j]=max(t,move(i,j));
        }
    }
    
    for(int i=0;i<m;i++)
        ans=min(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}
 Previous

Dynamic Programming