排位赛#14题解

双面人

2024-11-11 13:54:46

发布于：广东

57阅读

0回复

0点赞

T1.混淆字符串
函数 is_confusable 来判断两个字符串是否互为「混淆字符串」。这个函数首先定义了一个字典 confusable_pairs 来存储混淆字符对，然后遍历两个字符串的每个字符，检查它们是否相同或者是否互为混淆字符对。如果所有对应的字符都满足条件，则返回 "Yes"，否则返回 "No"。
上代码

def is_confusable(s, t):
    # 定义混淆字符对
    confusable_pairs = {
        '1': 'l', 'l': '1',
        '0': 'O', 'O': '0',
        '5': 'S', 'S': '5'
    }
    # 检查每个字符是否相同或者互为混淆字符对
    for i in range(len(s)):
        if s[i] != t[i] and (s[i] not in confusable_pairs or confusable_pairs[s[i]] != t[i]):
            return "No"
    return "Yes"

# 读取输入
N = int(input())  # 读取字符串长度，但实际上我们不需要这个信息，因为问题描述中字符串长度是固定的
S = input()
T = input()

# 判断并输出结果
result = is_confusable(S, T)
print(result)

T2.循环小数
find_repeating_cycle 来找出有理数 p/q
的循环小数序列。这个函数使用了长除法的方法，通过一个字典 remainders 来记录每个余数出现的位置，以此来检测循环的开始。如果余数为0，则没有循环小数。如果余数之前出现过，那么从那个位置开始的序列就是循环序列。
上代码

def find_repeating_cycle(p, q):
    # 用来存储余数，以便检测循环
    remainders = {}
    rem = p
    result = []

    # 执行长除法直到余数为0或者检测到循环
    while rem != 0 and rem not in remainders:
        remainders[rem] = len(result)
        rem = rem * 10
        result.append(rem // q)
        rem %= q

    # 如果余数为0，则没有循环小数
    if rem == 0:
        return ''.join(map(str, result))

    # 找到循环开始的位置
    start_index = remainders[rem]
    # 提取循环序列
    repeating_cycle = result[start_index:]

    return ''.join(map(str, result[:start_index] + repeating_cycle))

# 读取输入
p, q = map(int, input().split())

# 输出循环序列
print(find_repeating_cycle(p, q))

T3.特殊的染料
这道题目是一个典型的贪心算法问题，我们需要通过最少的金币消耗来将染料桶中的染料量从左到右递增排序。关键在于理解如何通过交换操作来实现排序，并且如何计算每次交换所需的金币消耗。
我们需要理解题目中的“倒换”操作。每次交换操作涉及到三个桶：i、i+1 和 j。我们需要将 i 或 i+1 中的染料倒入 j 中，然后再将 j 中的染料倒入 i 或 i+1 中，完成倒换。这个过程需要消耗金币，金币的消耗取决于 j 桶中染料的颜色。
上代码

#include <bits/stdc++.h>
using namespace std;

int a[114], b[114];
int main() {
    int n, ans = 0, minn;
    cin >> n;
    for (int i = 0; i < n; i ++)
    	cin >> a[i];
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (a[j] == i + 1)
				cin >> b[j];
    for (int ii = 1; ii < n; ii ++)
        for (int i = 0; i < n - 1; i ++)
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                swap(b[i], b[i + 1]);
                minn = 114514;
                for (int j = 0; j < n; j ++) {
					if (j == i || j == i + 1)
                        continue;
                    if (a[i] + a[j] <= n || a[i + 1] + a[j] <= n)
                        minn = min(minn, b[j]);
                }
                ans += minn;
            }
   	cout << ans;
   	
    return 0;
}