Q1 小美的比赛

题目描述

小美正在参加比赛,一共有n场比赛,赢得一场可以获得1分,如果上一场也赢了,可以获得额外的1分.现在给你n场比赛的结果,你需要计算小美的分数.

输入

第一行一个整数n, 表示比赛的场数.
一行n个整数,表示每场比赛的结果,1表示赢,0表示输
1 <= n <= 10^5

输出

一个整数,表示小美的分数

示例

输入:

1
2
5
1 1 1 0 1

输出:

1
6

说明:
第一场比赛获胜,获得1分
第二场比赛获胜,并且上场比赛也获胜了,获得2分
第三场比赛获胜,并且上场比赛也获胜了,获得2分
第四场比赛输了,获得0分
第五场比赛获胜,获得1分

代码:AC 100%

小美的比赛view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys

n = int(input())
nums = input().split(' ')
nums = [int(i) for i in nums]

result = 0
for n in range(len(nums)):
    if n == 0:
        result = nums[n]
    else:
        if nums[n] == 1 and nums[n-1] == 1:
            result += 2
        elif nums[n] == 1:
            result += 1
print(result)

Q2 小美打靶

题目描述

小美在训练场打靶,靶一共有10环,靶的中心位于(0,0),如果大众的位置以靶心为圆心,半径为1的园内,则得10分,之后每向外一圈分数减1,直到1分,每圈的半径都比上一圈大1.即使如果打中的位置在以靶心为圆心,半径为i的园内,则得11-i分.
如果打中的位置不在任何一圈内,则得0分.

输入

一行两个整数x,y,表示打中的位置坐标.
0 <= x, y <= 10

输出

输出一个整数,表示得分

示例

输入: 1 0
输出: 10

输入: 1 1
输出: 9

代码:AC 100%

小美打怪view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
import sys
import math

for line in sys.stdin:
    [n1, n2] = line.split(" ")
    n1 = int(n1)
    n2 = int(n2)
    distance = math.ceil(math.sqrt((n1 ** 2 + n2 ** 2)))
    
    result = 11 - distance
    result = max(0, result)
    result = min(10, result)
    print(result)

Q3 小美打怪

题目描述

小美在玩游戏,游戏中有n个怪物,怪物的血量为hi,攻击力为ai.小美的血量为H,攻击力为A,小美可以击败血量和攻击力都小于自己的怪物,并且打败后血量降为怪物的血量,攻击力降为怪物的攻击力.小妹想知道最多可以打败多少怪物.

输入

第一行三个数n,H,A,分别表示怪物的数量,小美的血量,小美的攻击力
第二行n个整数hi,表示怪物的血量
第三行n个整数ai,表示怪物的攻击力
1 <= n <= 10^3
1 <= ai, hi, H, A <= 10^9

输出

输出一个整数表示答案

示例

输入:

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

输出:

1
1

说明:
最多只能击败一个怪物

代码:AC 13.33%

小美打怪view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys

[num_monster, mei_hp, mei_atk] = [int(i) for i in input().split(" ")]
monster_hps = [int(i) for i in input().split(" ")]
monster_atks= [int(i) for i in input().split(" ")]
monster_infos = list(zip(monster_atks, monster_hps))

def max_monsters(atk, hp, monsters):
    monsters.sort(key=lambda x: x[0])
    killed = 0
    for monster in monsters:
        monster_atk, monster_hp = monster
        if atk > monster_atk and hp > monster_hp:
            atk = monster_atk
            hp = monster_hp
            killed += 1
    return killed

print(max_monsters(mei_atk, mei_hp, monster_infos))

Q4 小美的数组与

题目描述

小美有一个长度为n的数组,他想从中选出至少一个或多个数,使得这些个数的按位与的结果可以被2^m整除.例如小美有一个数组[1,2,4,12],那么他可以选出[4,12],因为4 & 12 = 4,可以被2^2整除,所以m的最大值为2.请帮小美选树,使得整数m尽可能的大.

输入

第一行一个整数n,表示数组的长度
第二行n个整数ai,表示数组的元素
1 <= n <= 10^5
1 <= ai <= 10^9

输出

输出一个整数,表示m的最大值

示例

输入:

1
2
5
1 2 3 20 28

输出:

1
2

说明:
选择20和28,20&28=20,可以被2^2整除,所以m的最大值为2.

代码:部分完成,AC 0%

小美的数组与view raw
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
import sys

def max_power_of_2(num):
    m = 0
    while num % 2 == 0:
        num //= 2
        m += 1
    return m

if __name__ == "__main__":
    n = int(input())
    nums = [int(i) for i in input().split(' ')]
    
    all_weiyu_results = []
    for i in range(2 ** n):
        comb = bin(i)[2:].zfill(n)
        
        weiyus = []
        for j in range(n):
            if comb[j] == '1':
                weiyus.append(nums[j])

        if len(weiyus) == 0:
            continue
        elif len(weiyus) == 1:
            all_weiyu_results.append(max_power_of_2(weiyus[0]))
        else:
            result = weiyus[0]
            for k in weiyus[0]:
                result = result & k
            all_weiyu_results.append(max_power_of_2(result))
    print(max(all_weiyu_results))

Q5 小美修路

题目描述

地图上有n个城市,小美准备修建一些道路,使得任意两个城市之间都能通过道路到达.现在给定一些修路计划(有一些计划是必选的),请你帮小美规划出最优的方案.

输入

第一行输入两个正整数n,m,用空格隔开.代表城市数量
接下来的m行,每行输入四个正整数u,v,w,p,代表一个计划是在城市u和城市v之间修建一条道路,花费为w.如果p为1,代表该计划必选.如果p为0,代表该计划是可选的.
1 <= n,m <= 10^5
1 <= u,v <= n
1 <= w <= 10^9
0 <= p <= 1

输出

如果无解(即无法使得任意两个城市之间都能通过道路到达),则输出-1
如果有解,则第一行输入一个正整数k,代表选择的计划数量.第二行输入k个正整数bi,代表选择的计划
你只需要保证最终所有的城市都可以通过道路连通,且总代价最小即可.请注意,p=1的计划是必选的,如果你的方案不包含某个p=1的计划,则会直接返还答案错误.

示例

输入:

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

输出:

1
2
2
1 3

说明:
选择第一个和第三个方案,总花费为4.

代码:部分完成,AC 0%

小美修路view raw
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
34
35
36
37
38
39
import sys
[n, m] = [int(i) for i in input().split(' ')]
roads = []
for line in range(m):
    [u,v,w,p] = [int(i) for i in input().split(' ')]
    roads.append((u,v,w,p))

def prim_algo(n, roads):
    network = []
    added_cities = []
    for road in roads:
        u,v,w,p = road
        if p == 1:
            network.append(road)
            added_cities.append(u)
            added_cities.append(v)
    
    start_city = 1
    added_cities = set(added_cities)
    
    while len(added_cities) < n:
        min_cost = float('inf')
        new_road = None
        for road in roads:
            u,v,w,p = road
            if u in added_cities and v not in added_cities and w < min_cost and p == 0:
                min_cost = w
                new_road = road
        if new_road:
            network.append(new_road)
            added_cities.add(new_road[1])
    return network

result = prim_algo(n, roads)
print(len(result))
result_indexes = []
for i in result:
    result_indexes.append(str(roads.index(i) + 1))
print(' '.join(result_indexes))