“战疫杯”大学生程序设计在线邀请赛（5）题解

“战疫杯”大学生程序设计在线邀请赛（5）题解

题目wa穿了，罚时好多，但今天好多人估计卡第一题了

另外发现一个bug，我都ac了，再提交错误答案，还是会加罚时，无法理解

1. 感染源在哪里

由于读错题，快速写完wa了一发才开始冷静下来

注意题目几个关键性信息：

• 得分是加 1 / 出现次数
• 当出现有人多次去同一地点时，只计算一次
• 得分从高到低，如果有多个地点得分相同，地点名字典序小的优先

那么我们就可以把这个题目转换为一道需要模拟的排序题

排序条件是地点 出现的感染指数，降序，字典序升序

n = int(input())
dic = []
st = set()
# 去重
for i in range(n):
    s = input()
    s1,s2 = s.split()
    st.add(s1)
    if [s1,s2] not in dic:
        dic.append([s1,s2])
cnt = {}
# 统计每个地点的感染指数
for name in st:
    t = 0
    for i in range(len(dic)):
        if dic[i][0] == name:
            t += 1
    for i in range(len(dic)):
        if dic[i][0] == name:
            if dic[i][1] in cnt:
                cnt[dic[i][1]] += (1 / t)
            else:
                cnt[dic[i][1]] = (1 / t)
# 第一场排序，根据感染指数排序              
cnt = sorted(cnt.items(),key=lambda x:x[1],reverse=True)
# 由于不会自定义排序，自己又套了一层
# 给一个二维数组，将每个感染指数的加入到一个数组
# 每次输出时排序即可
res = [[] * n for _ in range(n)]
mins = cnt[0][1]
t = 0
for k in cnt:
    if k[1] == mins:
        res[t].append(k[0])
    else:
        t += 1
        res[t].append(k[0])
        mins = k[1]
for i in range(len(res)):
    if res[i] != []:
        res[i].sort()
        for j in range(len(res[i])):
            print(res[i][j])

2. 病毒序列

根据题意滑动下标模拟即可，但是5000 * 5000 的数据，py又又tle了，无奈改写c++才过

思路应该是相同的，贴一份py暴力n^ 2 的做法，但是tle了

s1 = input()
s2 = input()
res = 0
for t in range(len(s1)):
    dt = 0
    if t >= len(s2):
        break
    for i in range(len(s1)):
        if i + t >= len(s2):
            break
        if (s1[i] == "A" and s2[i + t] == "U") or (s1[i] == "U" and s2[i + t] == "A"):
            dt += 3
        elif (s1[i] == "C" and s2[i + t] == "G") or (s1[i] == "G" and s2[i + t] == "C"):
            dt += 2
    res = max(res,dt)
for t in range(len(s2)):
    dt = 0
    if t >= len(s1):
        break
    for i in range(len(s2)):
        if i + t >= len(s1):
            break
        if (s1[i + t] == "A" and s2[i] == "U") or (s1[i+t] == "U" and s2[i] == "A"):
            dt += 3
        elif (s1[i+t] == "C" and s2[i] == "G") or (s1[i+t] == "G" and s2[i] == "C"):
            dt += 2
    res = max(res,dt)
    # print(res)
print(res)
            

贴一份C++的ac代码，思路是一样的

#include 
#include 
#include 

using namespace std;
typedef long long LL;

int main() {
	string s1,s2;
	cin >> s1 >> s2;
	LL res = 0;
	int mxt = max(s1.size(),s2.size());
	int mit = min(s1.size(),s2.size());
	for(int t = 0; t < mxt; t ++) {
		LL dt = 0;
		if (t >= s2.size()) break;
		for (int i = 0; i < mit; i ++ ) {
			if ((i + t) >= s2.size())break;
			if(( s1[i] == 'A' && s2[i + t] == 'U') || (s1[i] == 'U' && s2[i + t] == 'A')) {
				dt += 3;
			} else if(( s1[i] == 'C' && s2[i + t] == 'G') || (s1[i] == 'G' && s2[i + t] == 'C')) {
				dt += 2;
			}
			// cout << s1[i] << " " << s2[i+t] << endl;
		}
		res = max(res,dt);
		// cout << dt <= s1.size()) break;
		for(int i = 0; i < mit ; i++) {
			if((i + t) >= s1.size()) break;
			if(( s1[i+t] == 'A' && s2[i] == 'U') || (s1[i+t] == 'U' && s2[i] == 'A')) {
				dt += 3;
			} else if(( s1[i+t] == 'C' && s2[i] == 'G') || (s1[i+t] == 'G' && s2[i] == 'C')) {
				dt += 2;
			}
			// cout << s1[i+t] << " " << s2[i] << endl;
		}
		res = max(res,dt);

		// cout << dt << endl;
	}
	cout << res << endl;
	return 0;
}

3. 奇奇怪怪的形状

模拟题，观察三视图的面积，加起来的和 * 2 即可，

俯视图： 如果四个点不是0 ，就+1

正视图： 取a,c 最大 + 取 b,d最大

左视图： 取a,b 最大 + 取 c,d最大

a,b = map(int,input().split())
c,d = map(int,input().split())
up,left,before = 0,0,0
nums = [a,b,c,d]
for i in range(len(nums)):
    if nums[i] != 0:
        up += 1
before += max(a,c)
before +=  max(b,d)
left += max(a,b)
left += max(c,d)
print((left + before + up)* 2)