笔试-快手-180910
优质
小牛编辑
129浏览
2023-12-01
- 单选 20;编程 3
字符串归一化
![](https://imgs.xnip.cn/cj/docimg/751/42a90764-d566-4949-94ba-d94a70952493.png)
Python(AC)
from collections import Counter
s = input()
c = Counter(s)
res = ""
for key in sorted(c.keys()):
res += key
res += str(c[key])
print(res)
魔法深渊
![](https://imgs.xnip.cn/cj/docimg/751/5c7cd585-fc77-49bc-ace8-eb04b42e2ba6.png)
![](https://imgs.xnip.cn/cj/docimg/751/fbb8d733-6e1a-4f9b-9f4f-dafb38f9fd28.png)
Python(AC)
def foo(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
j = 1
while j <= n:
if i < j:
break
dp[i] = dp[i] + dp[i - j]
j = j * 2
return dp[n] % 1000000003
N = int(input())
for i in range(N):
n = int(input())
print(foo(n))
善变的同伴
![](https://imgs.xnip.cn/cj/docimg/751/811aa30f-02bb-42aa-b6a6-ee19bc595515.png)
![](https://imgs.xnip.cn/cj/docimg/751/2bd67ed5-e495-49f6-8a6f-9d6afcb91663.png)
![](https://imgs.xnip.cn/cj/docimg/751/3b20ae58-5b4f-4bd6-91a1-789b262c1436.png)
思路
作者:n不正
链接:https://www.nowcoder.com/discuss/106768
来源:牛客网
1、先把整个数组改成正负交错的数组,去掉首尾的负数(相邻的正数合并成一个正数,负数合并成一个负数)
2、如果正数个数<=M,输出所有的正数之和
3、如果正数个数>M,将数组中[正负正]合并,该负数为数组中负数的最大值并且三者之和>三者最大值
4、直到3不满足或者正数个数<=M,输出最大的M个正数之和
Python(未测试)
- 按照上述思路实现的代码
# N, M = list(map(int, input().split())) # ns = list(map(int, input().split())) N, M = 7, 3 ns = [1, 2, 3, -2, 3, -10, 3]
new_ns = [ns[0]]
for i in ns[1:]: if i == 0: continue if (new_ns[-1] > 0) == (i > 0): new_ns[-1] += i else: new_ns.append(i)
if len(new_ns) >= 1 and new_ns[0] < 0: new_ns.pop(0)
if len(new_ns) >= 1 and new_ns[-1] < 0: new_ns.pop(-1)
ns_pos = new_ns[0::2] ns_neg = new_ns[1::2] cnt_pos = len(ns_pos)
updated = True while updated and M < cnt_pos: """""" updated = False
mx_i = 0
# mx = max(ns_pos[mx_i] + ns_pos[mx_i+1] + ns_neg[mx_i], ns_pos[mx_i], ns_pos[mx_i])
mx = float("-inf")
for i in range(len(ns_neg)):
tmp = ns_pos[i] + ns_pos[i+1] + ns_neg[i]
if tmp < max(ns_pos[i], ns_pos[i+1]): # 如果合并后减小则不合并
continue
if tmp > mx:
updated = True
mx = tmp
mx_i = i
if updated:
# 更新合并后的数组
ns_neg.pop(mx_i)
ns_pos[mx_i] = mx
ns_pos.pop(mx_i+1)
cnt_pos -= 1
# print(ns_pos)
# print(ns_neg)
ns_pos.sort(reverse=True) print(sum(ns_pos[:M]))