[ 编程 |20分 ] 数组中两个元素和小于等于M的组合数
时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 262144K，其他语言 524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言 524288K
64bit IO Format: %lld
本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，编码后请点击“保存并调试”按钮进行代码提交。
题目描述
对于一个整型数组，里面任何2个元素相加，小于等于M的组合有多少种；
如果有符合的，输出组合对数；
没有，输出0；
输入描述:
输入有2行，第1行为int整型数组，第2行为M值，且M也为int整型数字比如：7 -1 -1
9表示数组为[7, -1, -1]，M=9
输出描述:
里面任何两个元素小于等于9的组合有3种，分别是(7,第2个元素 -1), (第2个元素 -1, 第3个元素 -1), (7, 第3个元素 -1)，不同位置相同的元素值，但可以组成不同的组合故输出为 3
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
7 -1 -1
9
输出
3
说明
输入：数组为[7, -1, -1]，M=9输出：3
参考代码
import sys
from bisect import bisect_right
readline = sys.stdin.readline
nums = list(map(int, readline().strip().split()))
M = int(readline().strip())
nums.sort()
ans = 0
for i, x in enumerate(nums):
ans += bisect_right(nums[:i], M - x)
print(ans)
[ 编程 |30分 ] 计算K位
时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 65536K，其他语言 131072K
64bit IO Format: %lld
语言限定：C++(clang++11), Java(javac 1.8), C(clang11), Python2(2.7.3), Python3(3.9), C#(mcs 5.4), PHP(7.4.7), JavaScript Node(12.18.2), Go(1.14.4), Ruby(2.7.1), Rust(1.44), Swift(5.3), Scala(2.11.12), Kotlin(1.4.10), Groovy(3.0.6), TypeScript(4.1.2)
空间限制：C/C++ 65536K，其他语言 131072K
64bit IO Format: %lld
语言限定：C++(clang++11), Java(javac 1.8), C(clang11), Python2(2.7.3), Python3(3.9), C#(mcs 5.4), PHP(7.4.7), JavaScript Node(12.18.2), Go(1.14.4), Ruby(2.7.1), Rust(1.44), Swift(5.3), Scala(2.11.12), Kotlin(1.4.10), Groovy(3.0.6), TypeScript(4.1.2)
本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，编码后请点击“保存并调试”按钮进行代码提交。
题目描述
给你两个正整数 n 和 k，其中 1 =< n <= 26，字符串 Sn 的形成规则如下：
Li表示26个字母a-z，依次是：
L1 = "a"
L2 = "b"
L3 = "c"
...
L26="z"
S1 = "a"
当 i > 1 时，Si = Si-1 +Li + reverse(invert(Si-1))
其中 + 表示字符串的连接操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（例如：`a` 翻转为 `z` ，`b` 翻转为 `y` , ... 而 `z` 翻转为 `a`）。
例如，符合上述描述的序列的前 4 个字符串依次是：
S1="a"
S2="abz"S3="abzcayz"
S4="abzcayzdabzxayz"
请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
3,1
输出
a
说明
S3为 "abzcayz"，其第 1 位为 "a" 。
示例2输入输出示例仅供调试，后台判题数据一般不包含示例
输入
4,11
输出
z
说明
S4为 "abzcayzdabzxayz"，其第 11 位为 "z" 。
参考代码
B = [0]
for i in range(1, 27):
B.append(B[-1] * 2 + 1)
class Solution:
def findKthBit(self, n: int, k: int) -> str:
mid = (B[n] + 1) // 2
if k == mid:
return chr(n + ord("a") - 1)
elif k < mid:
return self.findKthBit(n - 1, k)
return chr(
ord("z")
- ord(self.findKthBit(n - 1, B[n - 1] + 1 - (k - mid)))
+ ord("a")
)
print(Solution().findKthBit(1, 1))
[ 编程 |30分 ] 纸张分配问题
时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 262144K，其他语言 524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言 524288K
64bit IO Format: %lld
本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，编码后请点击“保存并调试”按钮进行代码提交。
题目描述
一群小朋友围成一圈准备开始画画，现在老师需要给这些孩子发纸张；
规则是如果一个小朋友的年龄比自己旁边的人大，那么这个小朋友就必须分到比身旁孩子更多的纸张；
所有孩子至少要有一个纸张，请帮助老师设计一个算法，算出最少需要多少张纸。
备注：
假设小朋友的总数量不会超过100个；
每个小朋友至少要求至少有一张纸；
当且仅当年龄大于相邻小朋友时，才会要求纸张数量更多（年龄相等的情况下，允许小于或者等于）。
输入描述:
输入是一个数组，表示孩子的年龄，以空格隔开，举例如下：4 4 5代表3个小朋友，年龄分别是4岁，4岁，5岁
输出描述:
输出是最少需要的纸张的数量，以上述的输入为例，则最少需要1+1+2=4共4张纸，输出结果如下即可4
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
1 1 1
输出
3
说明
3个小朋友，年龄相同，每个小朋友只需发一张纸即可
示例2输入输出示例仅供调试，后台判题数据一般不包含示例
输入
1 2 3
输出
6
说明
3个小朋友，年龄分别需要 1+2+3共6张纸
示例3输入输出示例仅供调试，后台判题数据一般不包含示例
输入
5
输出
1
说明
1个小朋友，只需要1张纸即可
参考代码
import sys from collections import deque
readline = sys.stdin.readline
a = list(map(int, readline().strip().split()))
n = len(a)
adj = [[] for _ in range(n)]
indeg = [0] * n
for i in range(n):
l = (i - 1 + n) % n
r = (i + 1) % n
if a[i] > a[l]:
adj[l].append(i)
indeg[i] += 1
q = deque()
for i in range(n):
if indeg[i] == 0:
q.append(i)
b = [1] * n
while q:
u = q.popleft()
for v in adj[u]:
b[v] = max(b[v], b[u] + 1)
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
print(sum(b))
[ 编程 |20分 ] 航海探险
时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 32768K，其他语言 65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言 65536K
64bit IO Format: %lld
本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，编码后请点击“保存并调试”按钮进行代码提交。
题目描述
给你一个由 `0`（水）、`1`（陆地）和`2`（障碍物）组成的的二维网格，
再给你一个两栖交通工具，走陆地费用为1，走水路费用为2，
障碍物无法通行，请你计算从网格的起始位置行驶到最终位置的最小费用。
注意：
仅可以水平方向 和 竖直方向行驶。
如果无法到达目的地，则返回-1
另外，起始第1个位置不算，根据到达位置的属性来决定费用。
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
输出
7
说明
路径：[0,0]起，经过[0,1],[0,2],[0,3],[1,3],[2,3],[2,4],[3,4]，到达终点。
参考代码
import heapq
from typing import List
class Solution:
def minSailCost(self, g: List[List[int]]) -> int:
n = len(g)
m = len(g[0])
dist = [[float("inf") for _ in range(m)] for _ in range(n)]
dist[0][0] = 0
q = []
heapq.heappush(q, (0, 0))
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
while q:
d, u = heapq.heappop(q)
i, j = divmod(u, m)
for k in range(4):
r, c = i + dx[k], j + dy[k]
if 0 <= r < n and 0 <= c < m and g[r][c] != 2:
if d + 2 - g[r][c] < dist[r][c]:
dist[r][c] = d + 2 - g[r][c]
heapq.heappush(q, (dist[r][c], r * m + c))
if dist[-1][-1] == float("inf"):
return -1
return dist[-1][-1]
全部评论
(0) 回帖