腾讯真题汇总

一、翻转数列

小Q定义了一种数列称为翻转数列：给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4...每隔m个符号翻转一次, 最初符号为-。例如n = 8, m = 2，数列就是-1, -2, +3, +4, -5, -6, +7, +8；而n = 4, m = 1, 数列就是-1, +2, -3, +4。小Q现在希望你能帮他算算前n项和为多少。

import sys
while True:
    s = sys.stdin.readline().strip()
    if not s:
        break
    n, m = map(int, s.split(" "))
    print(n*m/2)

二、纸牌游戏

牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌，第i张纸牌上写着数字ai。牛牛和羊羊轮流抽牌，牛牛先抽，每次抽牌他们可以从纸牌堆中任意选择一张抽出，直到纸牌被抽完。他们的得分等于他们抽到的纸牌数字总和。现在假设牛牛和羊羊都采用最优策略，请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。

解：先排序，然后牛牛抽index为奇数的牌，羊羊抽index为偶数的牌。

import sys
while True:
    n = sys.stdin.readline().strip()
    s = sys.stdin.readline().strip()
    if not n or not s:
        break
    l = list(map(int, s.split(' ')))
    l.sort(reverse = True)
    ans = 0
    for i in range(len(l)):
        if i % 2 == 0:
            ans += l[i]
        else:
            ans -= l[i]
    print(ans)

三、贪吃的小Q

小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力？
输入描述：每个输入包含一个测试用例。每个测试用例的第一行包含两个正整数，表示父母出差的天数N (N <= 50000)和巧克力的数量M (N <= M <= 100000)。
输出描述：输出一个数表示小Q第一天最多能吃多少块巧克力。
$\color{red}{输入：3、7}$
$\color{red}{输出：4}$

解：小Q第一天最多吃m个，因为一共就m个巧克力。设小Q第一天吃的数量为i，将i从m往下不断递减，直到满足条件为止：
（1）第n天吃的数量仍然大于1。此时，只要 $m-total_n>0$ 即可；
（2）在第count天之前吃的数量已经等于1了。此时，只要剩余的巧克力数量大于剩余的天数，也就是 $m-total_k>n-count$ 即可。

import sys
while True:
    s = sys.stdin.readline().strip()
    if not s:
        break
    n, m = map(int, s.split(" "))
    for i in range(m, 0, -1):
        eat = 0
        today = i
        count = 0
        while count < n and today > 1:
            count += 1
            eat += today
            today = (today+1)//2
        if m - eat >= n - count:
            print(i)
            break

四、小Q的歌单

小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。
输入描述：每个输入包含一个测试用例。每个测试用例的第一行包含一个整数，表示歌单的总长度K (1 <= K <= 1000)。接下来的一行包含四个正整数，分别表示歌的第一种长度A (A <= 10)和数量X (X <= 100)以及歌的第二种长度B (B <= 10)和数量Y (Y <= 100)。保证A不等于B。
输出描述：输出一个整数，表示组成歌单的方法取模。因为答案可能会很大，输出对1000000007取模的结果。
$\color{red}{输入：5enter 2、3、3、3}$
$\color{red}{输出：9}$

import sys
while True:
    K = sys.stdin.readline().strip()
    s = sys.stdin.readline().strip()
    if not K or not s:
        break
    A, X, B, Y = map(int, s.split(" "))
    K = int(K)
    ans = 0
    i = 0
    while i <= X and i*A <= K:
        rem = K - i*A
        if rem % B == 0:
            j = rem // B
            if j <= Y:
                count_i, count_j = 1, 1
                for p in range(X, X-i, -1):
                    count_i *= p
                for q in range(i, 0, -1):
                    count_i //= q
                for p in range(Y, Y-j, -1):
                    count_j *= p
                for q in range(j, 0, -1):
                    count_j //= q
                ans += count_i * count_j
        i += 1
    print(ans % 1000000007)

最后编辑于：2020.09.05 14:32:11