2024-01-01 21:17 门头沟学院 golang

关注

24暑期实习(2023.4.15)米哈游笔试真题解析

T1 关于3

题目内容

在这个古老的民族中，数学不仅是一门学科，更是一种信仰和文化。他们相信，数字是宇宙中最基本的构成元素，任何事物的本质都可以用数字来描述和解释。

因此，这个民族对数字的研究非常深入。他们探索各种数学问题，包括数论、几何、代数等等，不断推进数学领域的发展。

其中一个有趣的问题是如何用若干个不相等的 3 的幂次方的和或差来表示任何正整数。这个问题引起了这个民族数学家们的极大兴趣，经过长期的研究和探索，他们最终得出了结论：任何正整数都可以用若干个不相等的 3 的幂次方的和或差表示。

这个发现深深地影响了这个民族的文化和信仰，成为他们数学研究和文化传承中的重要组成部分。为了纪念这个发现，这个民族经常使用 3 的幂次方作为他们文化的象征，并且在重要的节日和庆典中经常使用这个数字来表示祝福和祈愿。

今天，你有机会帮助这个民族解决一个实际的问题：给定一个正整数，你需要找到一种由若干个不相等的 3 的幂次方的和或差表示的方式，并按照每一项从大到小的顺序输出。

输入描述

一个正整数 $x(1\le x \le 10^9)$

输出描述

一个表达式，最终的答案必须等于 $x$ 。表达式的每一项必须是 3的幂，且不能有两项相同。

例如， 18 必须输出为 27−9 而不能是 9+9 。

样例

输入

输出

27+3

题解：三进制+递归拆解

对于一个数字x，它一定可以表示为若干个2的整数幂的和，比如 $7=2^2+2^1+2^0$ ，但是，它不一定能表示为若干个3的整数幂的和，比如 $30=3^3+3^1$ ，这个是可以表示成若干个3的整数幂的和的，但是对于 $2$ 这个数字来说，它不能被表示为若干个3的整数幂的和，但是可以被表示为 $26=3^3-3^0$

那么我们分析一下：什么样的数字可以被表示为若干个3的整数幂的和，我们设i为3的整数幂的最高次幂，那么它可以表示的最大数字不超过 $3^0+3^1+...+3^i=\frac{3^{i+1}-1}{2}$

因此，对于在该范围内的数字，是可以用若干个3的整数幂的和表示的，我们取 $i=log_3(x)$ ，那如果有 $x\ge \frac{3^{i+1}-1}{2}$ ，则我们需要向i+1借一位，然后让 $x=x-3^{i+1}$ ，然后再递归处理x，注意递归处理时，需要对x取绝对值，然后后面所得到的幂次也需要变换符号，比如加号变成减号，或者减号变成加号。

复杂度分析

时间复杂度：O(logn)

空间复杂度：O(1)

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
const int N=1E5+10;
int n;
vector<int>nums;
ll pow(int a,int b)
{
    ll res=1,t=a;
    while(b)
    {
        if(b&1)res*=t;
        t*=t;
        b>>=1;
    }
    return res;
}
void get_val(int x)
{
    int t=1;
    while(x>1)
    {
        int p=log(x)/log(3);
        if((pow(3,p+1)-1)/2<x)   //不能由1 3 ... 3^p 表示 需要向上借位
        {
            nums.push_back(pow(3,p+1)*t);
            t*=-1;
            x=pow(3,p+1)-x;
        }
        else
        {
            nums.push_back(pow(3,p)*t);
            x-=pow(3,p);
        }
    }
    if(x)nums.push_back(x*t);
}
int main()
{
    // 1+3+...+3^n=(3^(n+1)-1)/2
    cin>>n;
    get_val(n);
    bool flag=true;
    for(int &x:nums)
    {
        if(flag)
        {
            cout<<x;
            flag=false;
        }
        else
        {
            if(x>0)cout<<"+";
            cout<<x;
        }
    }
    return 0;
}

Java

import java.util.*;

public class Main {
    static int n;
    static List<Integer> nums = new ArrayList<>();

    static long pow(int a, int b) {
        long res = 1, t = a;
        while (b > 0) {
            if ((b & 1) == 1) res *= t;
            t *= t;
            b >>= 1;
        }
        return res;
    }

    static void get_val(int x) {
        int t = 1;
        while (x > 1) {
            int p = (int) (Math.log(x) / Math.log(3));
            if ((pow(3, p + 1) - 1) / 2 < x) {
                nums.add((int) pow(3, p + 1) * t);
                t *= -1;
                x = (int) pow(3, p + 1) - x;
            } else {
                nums.add((int) pow(3, p) * t);
                x -= pow(3, p);
            }
        }
        if (x != 0) nums.add(x * t);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        get_val(n);
        boolean flag = true;
        for (int x : nums) {
            if (flag) {
                System.out.print(x);
                flag = false;
            } else {
                if (x > 0) System.out.print("+");
                System.out.print(x);
            }
        }
    }
}

Python3

import math

def pow(a, b):
    res, t = 1, a
    while b:
        if b & 1:
            res *= t
        t *= t
        b >>= 1
    return res

def get_val(x):
    t = 1
    nums = []
    while x > 1:
        p = int(math.log(x) / math.log(3))
        if (pow(3, p + 1) - 1) / 2 < x:
            nums.append(pow(3, p + 1) * t)
            t *= -1
            x = pow(3, p + 1) - x
        else:
            nums.append(pow(3, p) * t)
            x -= pow(3, p)
    if x:
        nums.append(x * t)
    return nums

n = int(input())
nums = get_val(n)
flag = True
for x in nums:
    if flag:
        print(x, end='')
        flag = False
    else:
        if x > 0:
            print('+', end='')
        print(x, end='')

T2 a的组合方式

题目描述

在音乐创作过程中，有一种常见的技巧叫做“和声”。和声是指通过组合多个音符的声音来产生更加丰富的音乐效果。在和声中，相邻的音符通常被组合成和弦，而和弦的构成方式与音符的间隔密切相关。

假设在一首音乐作品中，有一段旋律由 $n$ 个音符组成，每个音符的音高由一个正整数表示。作曲家希望为这段旋律添加一些和声，以产生更加丰富的音乐效果。为了实现这个目标，他们想要找到一组和弦，使得这组和弦的构成方式与旋律的音符间隔完全匹配。

为了帮助作曲家实现这个目标，你需要编写一个程序来计算出可能的音符数组 $a$ 的组合方式数目。给定一个长度为 $n-1$ 的和弦数组 $b$ ，你的任务是计算出可能的音符数组 $a$ 的组合方式数目。其中，和弦数组 $b$ 中的每个元素 $b[i]=a[i]+a[i+1]$

作曲家们知道，在音乐中，和弦的构成方式是非常丰富多样的。因此，他们希望通过这个程序来快速地计算出所有可能的音符数组 $a$ 的组合方式数目，以便在创作过程中进行参考

输入描述

第一行输出为一个整数 $n(1\le n \le 10^5)$ 。

第二行输出为 $n-1$ 个整数，第 $i$ 个整数为 $b_i(1\le b_i\le 10^9)$

输出描述

输出为一个整数，表示数组 $a$ 有多少种可能

样例

输入

3
2 2

输出

样例说明

a,b之间的关系，且a必须为正整数

题解：思维题

$b_1=a_1+a_2$

$b_2=a_2+a_3$

$b_3=a_3+a_4$

...

可以得到：

$a_2=b_1-a_1$

$a_3=b_2-b_1+a_1$

...

已知所有的 $b_i$ ，因此所有 $a_i$ 的可能其实就是取决于 $a_1$ 可以取的值的个数

根据所有的 $a_i>0$ 可以不断地去计算 $a_1$ 取值的上界和下界，然后一边读取 $b_i$ ，一边更新上下界即可

复杂度分析

时间复杂度： $O(n)$

空间复杂度： $O(n)$

C++

#include <algorithm>
#include <climits>
#include <iostream>

using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    long long upper = LONG_MAX, lower = 0;
    long long bSum = 0;
    for (int i = 1; i < n; ++i)
    {
        int bi = 0;
        cin >> bi;
        if (i & 1)
        {
            bSum += bi;
            upper = min(upper, bSum);
        }
        else
        {
            bSum -= bi;
            lower = max(lower, bSum);
        }
    }
    // 如果lower >= upper - 1, 输出0.
    long long answer = max(0ll, upper - lower - 1);
    cout << answer << endl;
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long upper = Long.MAX_VALUE, lower = 0;
        long bSum = 0;
        for (int i = 1; i < n; ++i) {
            int bi = scanner.nextInt();
            if ((i & 1) == 1) {
                bSum += bi;
                upper = Math.min(upper, bSum);
            } else {
                bSum -= bi;
                lower = Math.max(lower, bSum);
            }
        }
        // 如果lower >= upper - 1, 输出0.
        long answer = Math.max(0, upper - lower - 1);
        System.out.println(answer);
    }
}

Python

n = int(input())
upper = float('inf')
lower = 0
bSum = 0
for i in range(1, n):
    bi = int(input())
    if i % 2 == 1:
        bSum += bi
        upper = min(upper, bSum)
    else:
        bSum -= bi
        lower = max(lower, bSum)
# 如果lower >= upper - 1, 输出0.
answer = max(0, upper - lower - 1)
print(answer)

T3 奇妙糖果

题目内容

在一个神奇的糖果工厂中，有一种特殊的糖果叫做“奇妙糖果”。这种糖果非常受欢迎，因为它的口感和味道都非常好。

奇妙糖果的制作非常复杂，制造过程中要求每种原料的出现次数必须是 $k$ 的倍数，其中 $k$ 是一个给定的正整数。

在制造奇妙糖果的过程中，制造商们发现，他们可以通过选择不同的原料配方来制造出不同的口感和味道的糖果。他们想要快速计算出可以制造的所有糖果的数量，以便在生产计划中进行参考。

为了实现这个目标，他们需要编写一个程序来计算出可以制造的所有奇妙糖果的数量。

给定 $n$ 个原料和正整数 $k$ ，以及每个原料的种类 $a_i$ ，你的任务是计算出可以制造的所有的奇妙糖果的数量。

注意，这里的“奇妙糖果”是指使用 $n$ 个原料的任意非空子序列制造出的糖果，其中每种原料的出现次数都是 $k$ 的倍数。

子序列定义是数组中选择若干个元素按照原顺序组成的新数组。

输入描述

第一行输出为两个整数 $n(1\le n\le 50)$ 和 $k(1\le k \le 50)$ ，表示原料的个数。

第二行输出为 $n$ 个整数，第 $i$ 个整数为 $a_i(1\le a_i\le 50)$ ，表示该原料的种类的编号

输出描述

输出为一个整数，表示有多少使用 $n$ 个原料的任意非空子序列制造出的糖果，其中每种原料的出现次数都是 $k$ 的倍数。

样例

输入

4 2
1 2 1 2

输出

说明三种方案分别为：{1,1}, {2,2}, {1,2,1,2}

题解：组合数学计数

每个糖果的数量必须是 $k$ 的倍数即为 $0,k,2k ... nk$

因此考虑枚举每种糖果的方案数 然后基于乘法原理累乘即可

对于第 $i$ 种糖果 $a_i$ 对应的答案应该是 $C(a_i,0)+C(a_i,k)+C(a_i,2k)+...$

注意 最终答案需要-1(因为不能一个糖果都不选)

因为本题数据量不大，可以直接预处理组合数计算即可（如果本题数据范围为 $10^5$ ，对于C++和Java选手则需要使用乘法逆元处理）

复杂度分析

时间复杂度: $O(n^2)$

空间复杂度： $O(n)$

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55;
ll n,w[N],f[N][N],k;
unordered_map<int,int>cnts;
void init()  
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j)f[i][j]=1;
            else f[i][j]=(f[i-1][j]+f[i-1][j-1]);
        }
        
    }
}
int main()
{
    cin>>n>>k;
    init();
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        cnts[x]++;
    }
    ll res=1;
    for(auto &[u,v]:cnts)
    {
        if(v<k)continue;
        ll s=0;
        for(int i=0;i<=v;i+=k)s+=f[v][i];
        res*=s;
    }
    res--;  //去掉空集
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = 55;
    static long[][] f = new long[N][N];
    static Map<Integer, Integer> cnts = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        init();
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            cnts.put(x, cnts.getOrDefault(x, 0) + 1);
        }
        long res = 1;
        for (Map.Entry<Integer, Integer> entry : cnts.entrySet()) {
            int v = entry.getValue();
            if (v < k) continue;
            long s = 0;
            for (int i = 0; i <= v; i += k) {
                s += f[v][i];
            }
            res *= s;
        }
        res--;  // Remove the empty set
        System.out.println(res);
    }

    static void init() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    f[i][j] = 1;
                } else {
                    f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
                }
            }
        }
    }
}

Python

from collections import defaultdict
import math
n , k = list(map(int , input().split()))
a = list(map(int , input().split()))
cnt = defaultdict(int)
for x in a:
	cnt[x] += 1
ans = 1
# 枚举 每个数
for x in cnt.keys():
	t = 0
    # 枚举次数
	for y in range(0 , cnt[x] + 1 , k):
        # 求组合数
		t += math.comb(cnt[x] , y)
	ans *= t

if ans == 0:
	print(ans)
else:
	print(ans - 1)

以上内容均来自笔试刷题指南

#秋招##米哈游##笔试##互联网#

互联网笔试真题题解文章被收录于专栏

收录近两年互联网公司笔试真题解析，并提供Java，Python，C++三种语言版本的代码