「蓝桥·算法双周赛」第十七场分级赛——小白入门赛 ——前四道题

1. 桃园结义【算法赛】

问题描述
“俺老张最喜欢的就是喝酒吃肉，但今天这酒喝得有点晕乎，连自己有几个兄弟都数不清了。”张飞在桃园结义后，喝得酩酊大醉，竟忘了自己有几个结义兄弟。

刘备和关羽见状，决定逗逗张飞，让他数数结义兄弟一共有几个。张飞挠挠头，嘟囔着：“一个刘备，一个关羽，嗯…还有一个…呃，是谁来着？”

现在，请你帮助张飞，输出一个整数，表示桃园三结义的兄弟总数。

输入格式
无。

输出格式
输出一个整数，表示答案。

解题

签到题

print(3)

2. 北伐军费【算法赛】

问题描述
诸葛丞相正在筹备再次北伐，但军费开支庞大，让户部的官员们忧心忡忡。

户部尚书小心翼翼地说：“丞相，如今国库空虚，军费问题实在棘手…”

诸葛亮胸有成竹地回应：“无妨，我去向陛下借些。”

于是，诸葛亮来到了刘禅的寝宫。

“陛下，臣即将北伐，急需一笔军费…”诸葛亮恳求道。

刘禅面露难色：“啊，北伐确为大事，但朕最近斥巨资修建了一座宫殿，实在拿不出多少金币。”

“陛下，臣所需不多。这样吧，我们来玩个游戏，若臣赢了，还请陛下赐予臣一些军费，如何？”诸葛亮微微一笑。

“哦？什么游戏？朕最近对新奇的游戏颇感兴趣。”刘禅顿时来了兴致。

“我们来取铜钱。臣这里有
n 个铜钱，每个铜钱上都刻着数字，第
i 个铜钱上的数字是 a i 。我们轮流取一枚铜钱，由臣先来。无论谁取走后，剩下的所有铜钱上的数字都会乘以 −1。最后，若臣取走的铜钱数字之和 A 减去陛下取走的铜钱数字之和 B 为正，陛下就赐予臣 A−B的军费；若为负，则臣就…”诸葛亮故作神秘，留下悬念。

“有点意思，那就来吧！”刘禅的兴趣被激发。

就这样，诸葛亮和刘禅开始了这场精彩的铜钱游戏（由诸葛亮先手）。诸葛亮会尽力最大化 A−B 的值，而刘禅则会尽力最小化这个值。
那么，请你计算一下，最终 A−B 的值会是多少呢？

输入格式
第一行包含一个整数 n，表示铜钱的数量。
第二行包含 n 个整数 ，表示每个铜钱上刻的数字。

输出格式
输出一个整数，表示最终 A−B 的值。

样例输入

3
1 -2 3

样例输出

2

解题

n = int(input())
arr = list(map(int,input().split()))print(sum(arr))

3. 挑选武将【算法赛】

问题描述
却说天下大乱，曹操挟天子以令诸侯，招募了 n 员猛将，想要兴兵南下。为了联络方便，每位武将都会驻扎在一个城池中，用 a i 表示第 i 个武将驻扎的城池编号。这一日，曹操看着账下的武将名单，不禁陷入了沉思。他摸着胡子，对身边的谋士郭嘉说道：“奉孝啊，你看这名单上的武将，个个都是能征善战之辈，但你也知道，这军中之事，最忌讳的就是结党营私。你看这名单上，有些人住在一个城池里，这要是都带上了，难免会…”
郭嘉听罢，立刻明白了曹操的担忧。他微微一笑，说道：“主公英明！这挑选武将，确实要慎重啊！不如这样，我给主公精挑细选 k 员猛将，让他们尽量避免来自同一城池，以免生出不必要的麻烦。主公意下如何？”

曹操听后龙颜大悦，说道：“妙啊！那你快帮我算算，挑选的 k 员猛将，最多能有几个是单独来自一个城池的？”

输入格式
第一行输入两个整数
n,k（1≤k≤n≤10 **5），表示武将的总数量和要挑选的武将数量。
第二行输入 n 个整数 ，表示每位武将驻扎的城池编号。

输出格式
输出一个整数，表示最多能挑选的单独来自不同城池的猛将数量。

样例输入

5 4
1 1 2 2 3

样例输出

2

解题

from collections import Counter
n, m = map(int,input().split())
arr = list(map(int, input().split()))brr = list(set(arr))
crr = sorted(list(Counter(arr).values()), reverse=True)
q = len(brr)if m <= len(brr):print(m)
elif m > len(brr):k = m - len(brr)for i in range(len(crr)):if k <= 0:breakelse:k = k - (crr[i] - 1)q -= 1print(q)

4. 三顾茅庐【算法赛】

问题描述
卧龙凤雏，得一者可得天下！

在东汉末年，英雄豪杰聚集，刘备帐下的智囊徐庶家母遭曹操绑架，只得投奔曹家。在告别刘备之际，他将卧龙诸葛亮的所在告知刘备，引得刘备三顾茅庐，欲邀卧龙出山相助。

卧龙知晓刘备之雄心壮志，为考其统御之才，决定以一道难题来考验。

“我门前有一株神奇柳树，初高 x，每次操作可将其高度变为
∣当前高度−y∣，问经 k次操作后，树高为何？”

这个难题或许能考验刘备的智慧，望你能帮助他解答这一难题。

输入格式
第一行输入一个整数
t表示卧龙的询问次数。

接下来 t 行，每行三个整数 x,y,k(0≤x,y,k≤10 **9) 表示一次询问。

输出格式
输出 t 行，每行一个整数表示答案。

输入样例

3
10 1 3
10 1000 99999
10 0 0

输出样例

7
990
10

解题

暴力超时，不断优化

from math import fabsn = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]for i in range(n):result = arr[i][0]if arr[i][0] >= arr[i][1] and arr[i][1] != 0:zzz = arr[i][0] // arr[i][1]if arr[i][2] <= zzz:result = result - arr[i][1] * arr[i][2]elif arr[i][2] > zzz:if zzz % 2 == arr[i][2] % 2:result = result - arr[i][1] * zzzelif (zzz + 1) % 2 == arr[i][2] % 2:result = result - arr[i][1] * zzzresult = fabs(result - arr[i][1])elif arr[i][0] >= arr[i][1] and arr[i][1] == 0:result = arr[i][0]elif arr[i][1] > arr[i][0]:if arr[i][2] % 2 == 1:result = arr[i][1] - arr[i][0]elif arr[i][2] % 2 == 0:result = arr[i][0]print(int(result))