洛谷入门题 - 2

2019-10-23 Views 洛谷 编程2799字12 min read

洛谷创办于 2013 年,致力于为参加 noip、noi、acm 的选手提供清爽、快捷的编程体验。本系列文章选取大量新手村题目,为初学者讲解编程的一些相关技巧。本文使用的编程语言为 python,总共 10 道题,涵盖顺序与分支、循环和数组。
本文涉及的题目:P1909、P1089、P1423、P1424、P1980、P1008、P1427、P1428、P2141、P1567

P1909

P 老师需要去商店买 n 支铅笔作为小朋友们参加 NOIP 的礼物。她发现商店一共有 33 种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平起 见,P 老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开,因此 P 老师可能需要购买超过nn 支铅笔才够给小朋 友们发礼物。

现在 P 老师想知道,在商店每种包装的数量都足够的情况下,要买够至少nn 支铅笔最少需要花费多少钱。

因为题目已经限定好了只能买一种铅笔并且铅笔的种类只有三种,我们可以使用递归来解决这个问题,代码如下:

import math

num = int(input())
pen = []

for i in range(0,3):
    a = input().split()
    temp = [int(a[0]),int(a[1])]
    pen.append(temp)

money = math.ceil(num / pen[0][0]) * pen[0][1]

for i in range(1,3):
    c = math.ceil(num / pen[i][0])
    temp = c * pen[i][1]
    
    if money > temp:
        money = temp

print(money)

有关ceil函数的只是可以戳这里;ceil其实就是向上取整函数。

P1089

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300300 元钱,津津会预算这个月的花销,并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年末她会加上20%20% 还给津津。因此津津制定了一个储蓄计划:每个月的月初,在得到妈妈给的零花钱后,如果她预计到这个月的月末手中还会有多于100100 元或恰好100100 元,她就会把整百的钱存在妈妈那里,剩余的钱留在自己手中。

例如1111 月初津津手中还有8383 元,妈妈给了津津300300 元。津津预计1111 月的花销是180180 元,那么她就会在妈妈那里存200200 元,自己留下183183 元。到了1111 月月末,津津手中会剩下33 元钱。

津津发现这个储蓄计划的主要风险是,存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初,津津手中的钱加上这个月妈妈给的钱,不够这个月的原定预算。如果出现这种情况,津津将不得不在这个月省吃俭用,压缩预算。

现在请你根据 2004 年 1 月到 12 月每个月津津的预算,判断会不会出现这种情况。如果不会,计算到 2004 年年末,妈妈将津津平常存的钱加上 20% 还给津津之后,津津手中会有多少钱。

这道题是一道模拟,暴力枚举题。我们只需要把下个月的预算减去这个月剩下的钱,我们就可以知道下个月需要多少钱,从而可以判断津津这个月是会没钱还是可以存放一些到妈妈那里去,代码如下:

import math

money = 0
count = 0

ys = []

for i in range(0,12):
    ys.append(int(input()))

for i in range(0,11):
    if 300 - ys[i] < 0:
        count = -(i+1)
        break
    else:
        ci = (300 - ys[i]) // 100
        money = money + 100 * ci
        ys[i+1] -= (300 - ys[i]) - (100 * ci)

if 300 - ys[11] < 0:
    count = -12
else:
    ci = (300 - ys[11]) // 100
    money += 100 * ci
    sy = 300 - ys[11] - 100 * ci

if count < 0:
    print(count)
else:
    print(int(1.2 * money) + sy)

P1423

小玉开心的在游泳,可是她很快难过的发现,自己的力气不够,游泳好累哦。已知小玉第一步能游 2 米,可是随着越来越累,力气越来越小,她接下来的每一步都只能游出上一步距离的 98%。现在小玉想知道,如果要游到距离 x 米的地方,她需要游多少步呢。请你编程解决这个问题。

这道题需要利用循环解题,因为小玉每一次只能游出上次的98%,代码如下:

import math

d = float(input())
i = 1
dd = 2

while d > dd:
    dd += 2 * math.pow(0.98,i)
    i += 1

print(i)

P1424

有一只小鱼,它平日每天游泳 250 公里,周末休息(实行双休日),假设从周 x(1x7)x (1\le x \le 7) 开始算起,过了 n(n106)n (n\le 10^6) 天以后,小鱼一共累计游泳了多少公里呢?

这一道题的难点在于计算日期,比较简单的方法就是利用数组进行循环标记,到一次星期六或星期天就标记一次,最后再减去这些日子,代码如下:

a = input().split()
st = int(a[0])
t = int(a[1])
mt = 0

for i in range(0,t):
    if st == 6:
        mt += 1
    elif st == 7:
        mt += 1
        st = 0
        
    st += 1

print(250 * (t - mt))

但是因为要进行循环,所以时间复杂度会比较高,helloboyxxx提出了更好的解决办法。我们可以把时间分为三个部分:首先是目前到周六的时间,接着是游泳需要占据多少个周,最后就是游泳的时间减去占据周的时间,代码如下:

x,y = input().split()

a = int(x)
b = int(y)

if a == 7:
   n1 = 0
else:
    n1 = 6-a

n2 = (b - 8 + a) // 7 * 5

if (b - 8 + a) % 7 == 6:
    n3 = 5
else:
    n3 = (b - 8 + a) % 7

total = (n1 + n2 + n3)*250
print(total)

P1980

试计算在区间 11nn 的所有整数中,数字 x(0x9)x (0 ≤ x ≤ 9) 共出现了多少次?例如,在 111111 中,即在 1,2,3,4,5,6,7,8,9,10,111,2,3,4,5,6,7,8,9,10,11 中,数字 11 出现了 44 次。

这个问题有两种做法,因为题目限定了数据大小为1 ≤ n ≤ 1,000,00,所以我们可以提取出各位,但是会比较麻烦,因为位数较大;所以我们可以采用字符串方法——把数字看成字符串来查找,代码如下:

a = input().split()
count = 0

n = int(a[0])
which = a[1]

def dd(st,num):
    return st[:num] + st[num+1:];

for i in range(1,n+1):
    d = 0
    s = str(i)
    while d != -1: 
        d = s.find(which)
        if d >= 0:
            count += 1
            s = dd(s,d)

print(count)

P1008

1,2,,91,2, \cdots ,999 个数分成 33 组,分别组成 33 个三位数,且使这 33 个三位数构成 1:2:31:2:3 的比例,试求出所有满足条件的 33 个三位数。

这题的核心思想就是我们要明白这三个三位数各个位相加等于1+2++91 + 2 + \cdots + 9三个三位数相乘等于1×2××91 × 2 × \cdots × 9。根据这个思路我们可以提取各位之后来进行如上的比较,代码如下:

for a in range(123,334):
    b = a * 2
    c = a * 3
    if a // 100 + a // 10 % 10 + a % 10 + b // 100 + b // 10 % 10 + b % 10 + c // 100 + c // 10 % 10 + c % 10 == 45:
        if (a // 100) * (a // 10 % 10) * (a % 10) * (b // 100) * (b // 10 % 10) * (b % 10) * (c // 100) * (c // 10 % 10) * (c % 10) == 362880:
            print(str(a) + " " + str(b) + " " + str(c))

P1427

小鱼最近被要求参加一个数字游戏,要求它把看到的一串数字(长度不一定,以 0 结束,最多不超过 100 个,数字不超过 232-1),记住了然后反着念出来 (表示结束的数字 0 就不要念出来了)。这对小鱼的那点记忆力来说实在是太难了,你也不想想小鱼的整个脑袋才多大,其中一部分还是好吃的肉!所以请你帮小鱼编程解决这个问题。

这是一道简单的倒序输出数组的问题,代码如下:

a = input().split()

for k in range(len(a) - 2, -1, -1):
    print(a[k], end=" ")

P1428

人比人,气死人;鱼比鱼,难死鱼。小鱼最近参加了一个 “比可爱” 比赛,比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排,头都朝向左边,然后每只鱼会得到一个整数数值,表示这只鱼的可爱程度,很显然整数越大,表示这只鱼越可爱,而且任意两只鱼的可爱程度可能一样。由于所有的鱼头都朝向左边,所以每只鱼只能看见在它左边的鱼的可爱程度,它们心里都在计算,在自己的眼力范围内有多少只鱼不如自己可爱呢。请你帮这些可爱但是鱼脑不够用的小鱼们计算一下。

代码如下:

a = int(input())
d = input().split()

b = [0]

for i in range(1,a):
    c = 0
    for k in range(0,i):
        if d[i] > d[k]:
            c += 1
    b.append(c)

for each in b:
    print(each,end=" ")

P2141

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?

最近老师出了一些测验题,请你帮忙求出答案。

这题需要注意:在记录有多少个数恰好等于集合中另外两个数之和的时候要避免相加出相同结果的数,这种书如果算上相当于是重复计算,所以要去除;代码如下:

a = int(input())
b = input().split()
count = 0
c = []

for i in range(0,a):
    b[i] = int(b[i])

for i in range(0,len(b)):
    for k in range(i + 1,a):
        temp = b[i] + b[k]
        if temp in b:
            if temp not in c:
                count += 1
                c.append(temp)

print(count)

P1567

炎热的夏日,KC 非常的不爽。他宁可忍受北极的寒冷,也不愿忍受厦门的夏天。最近,他开始研究天气的变化。他希望用研究的结果预测未来的天气。 经历千辛万苦,他收集了连续 N(1N106)N (1 \leq N \leq 10^6) 的最高气温数据。 现在,他想知道最高气温一直上升的最长连续天数。

代码如下:

a = int(input())
b = input().split()
count = []
temp = 1

for i in range(0,a):
    b[i] = int(b[i])

t = b[0]

for i in range(1,a):
    if b[i] > t:
        t = b[i]
        temp += 1
    elif b[i] < t:
        t = b[i]
        count.append(temp)
        temp = 1

print(max(count))

注:如有更简单的代码欢迎在评论区留言哦!



logo   WRITTEN BY:Serence

一个程序员和文艺青年的博客!

本文章采用CC BY-NC-SA 4.0进行许可。转载请注明出处!

上一篇

洛谷入门题 - 3


下一篇

洛谷入门题 - 1