vue视频教程 scipy uitableview pdf session canvas encoding outlook dns routing Zeptojs Avalon vue钩子函数 vue样式 vue响应式布局 河南普通话报名 android项目开发 jq解析json 大数据驾驶舱 java反射方法 coreldraw入门学习 python调用方法 python对象 python中pop函数 python中文教程 javascanner java覆盖 java重写和重载 javaswitch语句 java生成文件 h5模板 图片放大软件 dnf刷什么图赚钱 js刷新页面 视频编辑专家下载 pycharm中文版 电脑书籍下载 小程序游戏源码 fireworks下载 vs2012中文旗舰版下载
当前位置: 首页 > 学习教程  > python

牛客网11746竞赛简单题

2021/2/6 22:22:37 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

1. 上进的凡凡 题目描述: 凡凡是一个上进的人,他的人生没有下坡路,他也讨厌带有”下坡路“的东西。所以,对于凡凡来说,只有非降序的数组才是nice的(如:1,2,2&#xff0c…

1. 上进的凡凡

题目描述:
凡凡是一个上进的人,他的人生没有下坡路,他也讨厌带有”下坡路“的东西。所以,对于凡凡来说,只有非降序的数组才是nice的(如:1,2,2,3,4,5,5);若数组元素个数为1,也满足非降序,也是nice的。现在有一个长度为n的数组,凡凡想知道它的子数组中有多少个数组是nice的。你能帮帮他吗?对于子数组的定义,如果可以通过从开头和从结束分别删除若干个(可以为零或全部,前后删除个数不必相同)元素来从数组b获得数组a,则称数组a是数组b的子数组。(子数组包含原数组,但不包含空串)

输入描述:
第一行输入一个整数n(1≤n≤10^5),表示数组的长度。
第二行包含n个空格分隔的整数a1,a2,.,an(0≤ai≤10^9),为数组的元素。

输出描述:
输出给定数组的子数组中是nice数组的个数。(注意使用long long)

示例1

输入

5
1 2 3 4 5

输出

15

链接:https://ac.nowcoder.com/acm/contest/11746/C
来源:牛客网

思路:分析题目可以知道对于当前不降序的序列后面增加一个数字假如破坏了前面不降序的序列那么后面的这个数字对于之前不降序的序列对于增加不降序的序列是没有任何贡献的,反而充当了分割线的作用将各个不降序的序列分割开来,所以我们就可以独自计算每一个不降序序列的片段,而主要是每一个不降序的片段的子数组的个数(使用一个片段),由几个数字的不降序的片段可以知道总的个数为片段长度的等差序列求和,代码如下:

if __name__ == "__main__":
    # 使用循环依次比较相邻两个数字是否相等即可
    res, count = 0, 1
    n = int(input())
    num = list(map(int, input().split()))
    for i in range(n):
        if i == n - 1 or num[i] > num[i + 1]:
            res += (1 + count) * count // 2
            count = 1
        else:
            count += 1
    print(res)

2. 数羊

问题描述:

憨憨小杨晚上睡不着觉,就开始数羊,她觉得一只一只数太慢了,突发奇想出了一种新的数羊方式,羊羊数量A(n,m)由两个整形变量n和m决定,计算方式如下:

现在给出n和m的值,请你帮小杨数数一共有多少只羊。

输入描述:
多组输入。
第一行包含一个整数T(1≤T≤1000),表示有T组测试数据。
每组测试数据包含一行,包含两个整数n(1≤n≤10^9)和m(0≤m≤2).

输出描述:
对每一组输入,在一行中输出A(n,m)的值,由于输出的结果可能会很大,答案对998244353取模

示例1
输入

3
3 0
3 1
3 2

输出

5
6
8

链接:https://ac.nowcoder.com/acm/contest/11746/H
来源:牛客网

思路分析:分析题目可以知道题目的关键是最后一个递归式子的计算,对于这种比较复杂的递归式子假如直接使用给出的递归表达式进行计算肯定是超时的,我们要做的是对其进行优化化简为更加简单的式子,最简单的方法是输出前面的1前面若干几项看能否发现什么规律(暴力打表)

m = 0时,A(n,0) = n + 2    m = 1时,A(n,1) = 2 * n,m = 2时A(n,2) = 2 ^ n

证明:当m = 0时,A(n,0) = n + 2,m = 1时A(1,1) = A(A(0,1),0) = A(1,0)=2,则A(n,1) = A(A(n -1,1),0) = A(n-1,1) + 2 = 2 * m

当m = 2时,A(n,2) = A(A(0,2),1) = A(1,1) = 2,A(n,2) = 2 ^ n

代码如下:

def quickPower(x: int, n: int):
    # 快速幂运算
    res = 1
    while n > 0:
        # 当为奇数的时候, 列出简单的例子会很好理解
        if n % 2 == 1:
            res = res * x % 998244353
        x *= x
        n //= 2
    return res % 998244353


if __name__ == "__main__":
    # 根据给出的式子进行计算, 题目的关键点在于递归式子的计算(数据规模大的时候)
    n = int(input())
    for i in range(n):
        n, m = map(int, input().split())
        res = 0
        if m == 0:
            res = n + 2
        elif m == 1:
            res = n * 2
        elif m == 2:
            res = quickPower(2, n)
        print(res)

3. 买花

题目描述 
情人节马上要到了,阳阳想送出n朵花给喜欢的妹妹,他打算提前开始买。但是,因为他有强迫症,所有的花要分k天买(k>1,即不能一天全买完),第一天他可以买任意朵花,之后每一天买花的数量为前一天的两倍,(如若第一天买4朵,第二天就要买8朵,以此类推)。
现在离情人节还有15天(k≤15),请你告诉阳阳,他能不能刚好买到n朵花。

输入描述:
多组输入。第一行一个正整数T(1<=T<=10^5),表示数据组数。
接下来T行,每行一个正整数n(1<=n<=10^9),表示预计买花的数量。
输出描述:
每组数据输出一行,共T行。
判断能否刚好买到n朵花,可以则输出"YE5",否则输出"N0"。
示例1
输入
2
21
20
输出
YE5
N0

思路分析:很明显题目存在一个一等比数列的求和,假设第一天买花的数量为x,很明显公比为2,则我们需要找到 x * (1 - 2 ^ t) == n中的x与t使得等式成立,因为是在15天之内所以我们可以判断n是否可以在15天之内找到对应的x即可,所以使用两层循环即可判断,代码如下:

import math

if __name__ == "__main__":
    # 计算x * (2 ** k - 1) == n
    n = int(input())
    for i in range(n):
        n1 = int(input())
        f = 0
        for k1 in range(2, 16):
            if n1 % (math.pow(2, k1) - 1) == 0:
                f = 1
                break
        if f:
            print("YE5")
        else:
            print("N0")

4. 这是一题简单的模拟

题目描述 
财务计划要从家里出发,去N个城市出差,然后再回到家中,但N个出差地点之间不一定都能通车,现在他要筛选出花费最少的路径,你能帮帮他吗?

输入描述:
第一行为两个正整数N和M(1≤N≤300,1≤M≤N(N+1)/2),分别表示有N个出差地点和这些地点之间的M条通路,其中出差地点用1到N编号,而财务的家所在城市用编号0表示。
随后的M行,每行给出通路连接的两个城市和这条通路上的花费,格式为:

```
城市A 城市B 花费
```
通路是双向的,且两个城市间最多有一条通路,不存在自环。保证所有花费大于0。
再下一行给出一个正整数K(K<=20000),表示现在有K条推荐路径(注意:给出的路径不一定能通过或可能不满足财务的要求)。
接下来K行每一行表示一个推荐路径,第一个整数n表示途径的城市数,后面有n(n<=2*N)个整数xi(1≤xi≤N)(表示途经的城市(不包括财务的家),如:
3 1 2 3
表示实际路径为0→1→2→3→0。
输出描述:
请你检验给出的K条推荐路径,当它满足:
1.给出的路径能实际通车,即路径中相邻城市存在通路;
2.给出的路径恰好能都到达N个出差城市一次,即不能漏掉某个城市,也不能重复到达。
则称这条路径是可行的。
对于给出的K条推荐路径,请输出其中可行路径中最少的花费,若不存在可行路径,请输出"-1"。(题目保证花费和不超过int范围)
示例1
输入

5 10
0 1 5
0 5 12
1 2 2
2 3 8
3 4 13
1 3 11
0 2 5
0 4 9
4 5 6
3 5 7
5
5 1 3 2 3 1
5 3 2 1 4 5
5 2 1 3 5 4
6 1 2 3 4 5 1
5 1 2 3 5 4
输出
37

思路分析:因为是要从推荐路径中判断是否存在这样的路径所以检查二维列表中是否存在这样的路径即可,所以使用二维列表存储边的权重模拟其中的过程即可,代码如下(只是过了70%的测试样例)

import sys

if __name__ == '__main__':
    # 分析题目可以知道是典型的dfs
    N, M = map(int, input().split())
    # 使用二维列表来存储无向图的路径以及权重
    paths = [[-1] * (N + 1) for i in range(N + 1)]
    for i in range(M):
        a, b, dis = list(map(int, input().split()))
        paths[a][b] = paths[b][a] = dis

    n = int(input())
    start = list()
    for i in range(N + 1):
        if paths[0][i] != -1: start.append(i)
    res = sys.maxsize
    for i in range(n):
        vis = [0] * (N + 1)
        recommPath = list(map(int, input().split()))
        size = recommPath[0]
        if paths[0][recommPath[1]] != -1:
            s, f = paths[0][recommPath[1]], 1
            for j in range(2, size + 1):
                if paths[recommPath[j - 1]][recommPath[j]] != -1:
                    s += paths[recommPath[j - 1]][recommPath[j]]
                else:
                    f = 0
                    break
            if f and paths[recommPath[-1]][0] != -1:
                s += paths[recommPath[-1]][0]
                res = min(res, s)
    print(-1 if res == sys.maxsize else res)

5. 黑洞密码

题目描述 
近些日子,某科学家接受到了来自外太空的神秘讯息,在经过了一段时间的研究后,科学家发现讯息是一个由字母和数字组成的字符串str,想要破译,需要通过一定的规则将字符串进行转换。规则如下:
1. 确定讯息的长度为32; 
2. 字符串中第4n+1∼4n+4的字母和第4n+1~4n+4的字母和第4n+1∼4n+4(0≤n≤3)的数字为一组,共4组;
3. 每组的第1,2,3,4个字符分别往后推每组第1,2,3,4个数字个数 例:如第一个字母为a,第一个数字为3,转换后变为d,'z'之后是'B','Z'之后是'b';
4. 将每组内部字母的顺序颠倒;
5. 将四组字符合并就是最后的讯息。

输入描述:
输入一个长度为32的字符串
输出描述:
输出转换后的密码
示例1
输入
Zzc6Ltw2OD4yR640263W7G8G30HW9C71
输出
RgCgJQwxJfYCDeQG

思路分析:分析题目可以知道我们只需要模拟整个过程即可,遍历字符串将字母与数字进行分组,然后使用四个循环将其分别转换即可,代码如下:

def change(a: str, b: str):
    # 将字符a往后转int(b)个数字
    # 看是否超过了z
    t = ord(a) + int(b)
    if t > 122:
        return chr(t - 122 + 65)
    # 看是否超过了Z
    elif t > 90 and ord(a) <= 90:
        return chr(t - 90 + 97)
    else:
        return chr(t)


if __name__ == '__main__':
    # 为一道简单的模拟题
    s = input()
    chars, digs = "", ""
    for i in range(len(s)):
        if "0" <= s[i] <= "9":
            digs += s[i]
        else:
            chars += s[i]
    # print(chars, digs)
    for i in range(3, -1, -1):
        print(change(chars[i], digs[i]), end="")
    for i in range(7, 3, -1):
        print(change(chars[i], digs[i]), end="")
    for i in range(11, 7, -1):
        print(change(chars[i], digs[i]), end="")
    for i in range(15, 11, -1):
        print(change(chars[i], digs[i]), end="")

 


本文链接: http://www.dtmao.cc/news_show_2000042.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?