万万没想到之聪明的编辑
需求: 1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello 2. 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello 3. 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC
1 | 输入例子： |
直接读入,用栈对最新读入做check就行了 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20import sys
inputs = sys.stdin.readlines()[1:]
def fix(string):
fixed_string = []
fixed_string.append(string[0])
fixed_string.append(string[1])
for char in string[2:]:
if char == fixed_string[-1] == fixed_string[-2]:
pass
else:
fixed_string.append(char)
if fixed_string[-1] == fixed_string[-2]:
if len(fixed_string) > 3 and fixed_string[-3] == fixed_string[-4]:
fixed_string.pop()
return ''.join(fixed_string)
for sentence in inputs:
print(fix(sentence.strip()))
万万没想到之抓捕孔连顺
- 我们在字节跳动大街的 N 个建筑中选定 3 个埋伏地点。
- 为了相互照应，我们决定相距最远的两名特工间的距离不超过 D
给定 N（可选作为埋伏点的建筑物数）、 D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。 注意： 1. 两个特工不能埋伏在同一地点 2. 三个特工是等价的：即同样的位置组合( A , B , C ) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
1 | 输入例子： |
本质是个查找,从前往后遍历,固定被选择的建筑i,找出距离建筑i距离不超过D的尽可能远的建筑,做Cn2即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31import sys
inputs = sys.stdin.readlines()
N, D = map(int, inputs[0].split(" "))
if N <= 2:
print(0)
location = [int(i) for i in inputs[1].split(" ")]
def binsearch(target, l, r, arr):
mid = l + (r - l) // 2
while l <= r:
if arr[mid] == target:
return mid
elif arr[mid] < target:
l = mid + 1
else:
r = mid - 1
mid = l + (r - l) // 2
return mid
def Cn2(n):
return n * (n - 1) // 2
res = 0
for i in range(N-2):
r = binsearch(location[i] + D, i, N-1, location)
if r - i >= 2:
res += Cn2(r-i)
# 按牛客需求: 一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模
print(res % 99997867)
雀魂启动！
小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。 于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：
- 总共有36张牌，每张牌是1~9。每个数字4张牌。
- 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
- 14张牌中有2张相同数字的牌，称为雀头。
- 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）
1 | 输入例子： |
可以按取面子+雀头看剩下什么牌来做听牌check,可以分3面子+1雀头+1搭子或者4面子+单张,但需要做额外判断(搭子是否听牌以及听什么牌). 所以这里选择另一种方式,直接1-9遍历,必定凑出4面子+1雀头才是听牌. 听牌判断就是迭代加回溯
1 | import sys |
特征提取
小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。
输入描述 1
2
3
4
5
6
7
8
9第一行包含一个正整数N，代表测试用例的个数。
每个测试用例的第一行包含一个正整数M，代表视频的帧数。
接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2>
所有用例的输入特征总数和<100000
N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。
特征取值均为非负整数。
示例 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15输入例子：
1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1
输出例子：
3
例子说明：
特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3
用defaultdict,检测连续特征计数+1,否则pop特征并做max判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41import sys
from collections import defaultdict
instance_count = int(sys.stdin.readline())
result_lst = []
for instance in range(instance_count):
max_length = 0
animation_dict = defaultdict(int)
frame_count = int(sys.stdin.readline())
for frame_index in range(frame_count):
frame_input = sys.stdin.readline().strip().split(' ')
feature_pool = []
feature_num = int(frame_input[0])
features = frame_input[1:]
for feature_index in range(feature_num):
feature = ''
feature_length = len(features)//feature_num
for feature_pos in range(feature_length):
feature += features[feature_index*feature_length + feature_pos]
feature += ' '
feature_pool.append(feature)
keys = list(animation_dict.keys())
for feature in keys:
if feature in feature_pool:
animation_dict[feature] += 1
else:
value = animation_dict.pop(feature)
if value > max_length:
max_length = value
for feature in feature_pool:
if not animation_dict[feature]:
animation_dict[feature] += 1
max_length_in_dict = sorted(animation_dict.values())[-1]
max_length = max_length_in_dict if max_length_in_dict > max_length else max_length
result_lst.append(max_length)
for length in result_lst:
print(length)
毕业旅行问题
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
1 | 输入例子： |
这题卡了,找chatgpt学了下思路,dp+bitmask的思路,贴下chatgpt的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27def min_cost(cost):
n = len(cost)
# dp[mask][i]表示已经访问过的城市集合为mask，并且最后一次访问的城市是i时的最小花费
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 起点到达自己的花费为0
for mask in range(1, 1 << n):
for i in range(n):
if mask & (1 << i): # 如果第i个城市已经访问过了
for j in range(n):
if i != j and mask & (1 << j): # 如果第j个城市也已经访问过了
dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + cost[j][i])
# 找到从任意城市到达起点的最小花费
return min(dp[(1 << n) - 1][j] + cost[j][0] for j in range(n))
# 示例测试
if __name__ == "__main__":
cities = ["北京", "上海", "广州", "成都"]
# 以二维列表的形式给出每对城市之间的车费，如果不可达则用inf表示
ticket_cost = [
[0, 500, 800, 1000],
[500, 0, 600, 700],
[800, 600, 0, 900],
[1000, 700, 900, 0]
]
print("最小车费花销为:", min_cost(ticket_cost))
n个城市有2^n个状态,用二进制可以进行表示,最终状态位全1,dp列表一维表示到访过的城市掩码,二维表示最后到达的城市,其值表示能满足此条件的最低路径长度.
最终需要从城市回起点,在返回时再加一层判断即可.
代码没问题,不过python提交之后会TLE,想起之前密码学也有题python超时换c过了,于是用c重写了一下,成功通过.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int min(int a, int b){
return a < b ? a : b;
}
int cost(int *cost, int cities){
int dp[1<<cities][cities];
for(int i = 0; i < (1<<cities); i++){
for(int j = 0; j < cities; j++){
dp[i][j] = MAX;
}
}
dp[1][0] = 0;
for(int mask = 1; mask < (1<<cities); mask++){
for(int i = 0; i < cities; i++){
// i is choosen
if(mask & (1 << i)){
for(int j = 0; j < cities; j++){
if(i != j && mask & (1 << j)){
dp[mask][i] = min(dp[mask ^ (1 << i)][j] + cost[j * cities + i], dp[mask][i]);
}
}
}
}
}
int min_cost = MAX;
for(int k = 0; k < cities; k++){
min_cost = min(min_cost, dp[(1 << cities) - 1][k] + cost[k * cities]);
}
return min_cost;
}
int main() {
int cities;
scanf("%d", &cities);
int costs[cities][cities];
for(int i=0; i < cities; i++){
for(int j=0; j < cities; j++){
scanf("%d", &costs[i][j]);
}
}
printf("%d", cost(*costs, cities));
return 0;
}
找零
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为
N(0 < N<=1024 )的商品，请问最少他会收到多少硬币？ 1
2
3
4
5
6输入例子：
200
输出例子：
17
例子说明：
花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import sys
paied = int(sys.stdin.readline().strip())
def solution(money):
dp = [1024] * 1024
dp[0] = 0
for i in range(1, 1024):
if i in [1, 4, 16, 64]:
dp[i] = 1
elif i < 4:
dp[i] = dp[i-1] + 1
elif i < 16:
dp[i] = min(dp[i-1] + 1, dp[i-4] + 1)
elif i < 64:
dp[i] = min(dp[i-1] + 1, dp[i-4] + 1, dp[i-16] + 1)
else:
dp[i] = min(dp[i-1] + 1, dp[i-4] + 1, dp[i-16] + 1, dp[i-64] + 1)
return dp[money]
print(solution(1024-paied))
机器人跳跃问题
机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。
起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。
游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17输入例子：
5
3 4 3 2 4
输出例子：
4
----------------
输入例子：
3
4 4 4
输出例子：
4
----------------
输入例子：
3
1 6 4
输出例子：
3
描述非常诡异,不过其实是个数学问题 1
2
3
4
5
6
7
8
9
101: X>0
2: X+(X-H1) > 0
3: X+(X-H1)+(2X-H1-H2) > 0
4: X+(X-H1)+(2X-H1-H2)+(4X-2H1-H2-H3) > 0
化简之后
1: X>0
2: 2X>H1
3: 4X>2H1+H2
4: 8X>4H1+2H2+H3
1 | import sys |