1.输入一些单词 再输入一个前缀 输出所有前缀开始的单词 不包括相同的单词 按字典序排序 100分
input:
asd as as,asD // 单词
a // 前缀
output:
as asD asd注：任何标点符号视为分界 即don't 视为单词 don 和 t
2.输入一个数 返回所有可能的连续自然数和 100分
input:
9 // 自然数
output:
9=9 // 自然数组合
9=4+5
9=2+3+4
Result:3 // 总组合数3.哥哥弟弟分玩具 弟弟计算玩具重量方法是不带进位的二进制加法 要求兄弟所得玩具重量在弟弟眼中相同 求哥哥最大玩具重量 200分
input:
3 // 一共三个万玩具
3 5 6 // 重量分别是 3 5 6
output：
11 // 弟弟眼中 5 + 6 -> 101 + 110 = 11 == 3 所以哥哥最多拿 5 + 6 = 11cnt = int(input())
weights = list(map(int, input().split()))
if reduce(lambda x, y: x ^ y, weights) != 0:
print(-1)
else:
print(sum(weights) - min(weights))第三题其实看到不带进位的二进制和很容易想到异或
然后我的做法是遍历 range(1 << cnt) 分配玩具
每一种状态分别对应一种玩具分配方法
例如 110011 就是第0、1、4、5个玩具给一个人 2、3给另一个人
做完优化的时候发现其实玩具重量相等可以互换实际上只需要遍历一半就OK
这时候突然想到既然必须要求所有玩具异或和为0 否则无法分配
异或性质
a = b -> a ^ c = b ^ c
0 ^ c = c
故在玩具可分配情况下 单拿出任何一个玩具 剩下玩具的异或和与此玩具相等
那只要挑个垃圾给弟弟就行了
位运算真神奇
开始的代码大概是这样的
cnt = int(input())
weights = list(map(int, input().split()))
try:
if reduce(lambda x, y: x ^ y, weights) != 0:
print(-1)
raise
ans = 0
for i in range(1, (1 << cnt) - 1):
<!-- 哥哥叫solo 弟弟叫啥忘了 -->
solo0 = solo1 = coco0 = coco1 = 0
for j in range(cnt):
if i & 1 == 1:
solo1 += weights[j]
coco1 ^= weights[j]
else:
solo0 += weights[j]
coco0 ^= weights[j]
if coco0 == coco1:
ans = max(ans, solo0, solo1)
print(ans)
od的机试还是比较简单的
现在和别人差距越来越大 加油吧
评论 (32)
