2024 CCCC 天梯赛 230分题解详解

大三了也许是最后一次天梯赛，个人国二。

这次题目L1比L2难，确实牛。去年看了出题人说那个剪贴板题做的很糟糕，所以知道这次会出字符串处理的题目，复习了一..，然后你最喜欢的栈队列堆就不来是吧？？？。

接着奉劝所有天梯赛的同胞，都得学一下C++。首先用Python写可行性代码，超时改C++。不然真没法得奖，因为Java右时间宽限，Python和C++一样不知道why。

L1-3 帮助色盲

题目链接PTA | 程序设计类实验辅助教学平台

思路：… …if else

color, person = map(int, input().split())
move = ['stop', 'move']
tips = ['biii', 'dudu']
if color in [0, 1]:
    if person == 1:
        print('-')
        print(move[color])
    else:
        print(tips[color])
        print(move[color])
else:
    print('-')
    print('stop')

L1-4 四项全能

题目链接PTA | 程序设计类实验辅助教学平台

思路：每个人都会 m-1个技能点，如果这点数超过总点数那么不合法是0，否则总点数-每个人都会m-1个技能点

n, m = map(int, input().split())

nums = list(map(int, input().split()))

# 假设每个人都会m-1个技能的总点数
s_m = n * (m-1)

# 超出不合法
if s_m > sum(nums):
    print(0)
else:
    print(sum(nums)-s_m)

L1-5 别再来这么多猫娘了！

题目链接PTA | 程序设计类实验辅助教学平台

题意：按照从左到右，违禁词输入顺序，查找每个违禁词出现次数（违禁词不能在字符串内有共同重叠部分，也就是原串的一个子串只能是一个违禁词）

思路：… … ？？？？按照输入的顺序先count次数，然后replace把所有这个违禁词替换为_____（因为有的违禁词就是<censored>， 直接替换会导致count错误），最后统计总count，最后把_____替换为<censored>。

n = int(input())

dic = {}
for i in range(n):
    temp = input().strip()
    dic[temp] = 0

k = int(input())
s = input().strip()

# 统计次数，并且直接替换掉，不造成共用重叠
for key in dic.keys():
    dic[key] = s.count(key)
    s = s.replace(key, "_____")

mx = sum(dic.values())
if mx >= k:
    print(mx)
    print("He Xie Ni Quan Jia!")
else:
    print(s.replace('_____', '<censored>'))

L1-6兰州牛肉面

题目链接PTA | 程序设计类实验辅助教学平台

思路：纯模拟… … 难度是for

n = int(input())

# 直接下标取价格
money = [0.0] + list(map(float, input().split()))

# 记录每种的次数
count = [0] * (n+1)
res = 0
while True:
    a, b = map(int, input().split())
    if a==0 and b==0:
        break

    count[a] += b
    res += money[a] * b

for i in range(1, n+1):
    print(count[i])
print("%.2f"%res)

L1-7整数的持续性

题目链接PTA | 程序设计类实验辅助教学平台

思路：考察递归… … 可能需要记忆化，但是数据范围太小了，对于每个整数一直递归到<10然后返回长度。

from functools import lru_cache
a, b = map(int, input().split())

# 记录每个最终步数，出现的正整数
dic = {}


@lru_cache(maxsize=None) # 记忆化
def dfs(u):
    if u < 10:
        return 0
    return dfs(eval('*'.join(str(u)))) + 1


for i in range(a, b+1):
    dis = dfs(i)
    if dis not in dic:
        dic[dis] = []
    dic[dis].append(i)

# 最大步数
mx = max(dic.keys())

print(mx)
print(*dic[mx])

L1-8 九宫格

题目链接PTA | 程序设计类实验辅助教学平台

坑点：注意非法检查，存在非1-9的数字

思路：好烦下标处理，最烦了，这次来了三题下标处理的题目，烦死了。用set(1-9)直接对比即可。

# 数据范围小，直接和集合进行对比，方便判断
kk = set(range(1, 10))
for _ in range(int(input())):
    flag = 1
    maps = []
    for i in range(9):
        maps.append(list(map(int, input().split())))
        for x in maps[-1]:
            # 非法检测
            if not 1 <= x <= 9:
                flag = 0

    # 九宫格检查
    for i in range(9):
        xx, yy = 3 * (i // 3), 3 * (i % 3)
        vis = set()
        for ii in range(3):
            for jj in range(3):
                vis.add(maps[xx + ii][yy + jj])
        if vis != kk:
            flag = 0
            break

    # 行检查
    for i in range(9):
        if set(maps[i]) != kk:
            flag = 0
            break

    # 列检查
    for j in range(9):
        if set(maps[i][j] for i in range(9)) != kk:
            flag = 0
            break

    print(flag)

L2-1 鱼与熊掌

题目链接PTA | 程序设计类实验辅助教学平台

题意：每个人都拥有一些物品，给出一些询问，每组两个物品，有多少人两个物品都有。

思路：每个人用一个set维护拥有物品，每个询问直接查找每个人是否兼有。

坑点：Python超内存… … ，改成C++就全过了

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

const int N = 100010;
int n, m;

// 每个人一个set维护拥有的物品
set<int> vis[N];

int main() {
    cin>>n>>m;
    // 读入每个人拥有的物品
    for(int i = 1; i <= n; i++){
        int k, temp;cin>>k;
        while (k--){
            cin>>temp;
            vis[i].insert(temp);
        }
    }
    
    int q, a, b;cin>>q;
    // 处理询问
    while (q--){
        cin>>a>>b;
        int res = 0;
        // 每个询问都检查每个人是否都拥有
        for(int i = 1; i <= n; i++)
            if(vis[i].count(a) && vis[i].count(b))
                res++;
        cout<<res<<'\n';
    }
    return 0;
}

L2-2 懂蛇语

题目链接PTA | 程序设计类实验辅助教学平台

题意：给出一个词典句子集合，每次询问读入一句话， 然后从词典句子集合中找出和询问句子每个单词的首字母都对应相同的句子。

坑点：尾部可能有空格，不能清除！！！！！

思路：使用一个<字符串， 列表>的字典（map），读入一个词典句子，以每个单词首字母构造新字符串作为key键，在对应的列表中存入原句。询问的时候，以同样的方法构造字符串，去map查找输出即可。

n = int(input())

dic = {}
for i in range(n):
    # 读入原字符串
    temp = input().strip('\n')

    # 以首字母构造新字符串
    beg_str = ''.join(i[0] for i in temp.split())

    # 存入map中
    if beg_str not in dic:
        dic[beg_str] = []
    dic[beg_str].append(temp)

m = int(input())
for i in range(m):

    temp = input().strip('\n')
    
    # 以同样的方法构造字符串查找
    beg_str = ''.join(i[0] for i in temp.split())
    if beg_str not in dic:
        print(temp)
    else:
        print('|'.join(sorted(dic[beg_str])))

L2-3 满树的遍历

题目链接PTA | 程序设计类实验辅助教学平台

题意：非叶子节点，必须所有节点的孩子数量都相同则为k阶，否则k为最大的孩子数量。

思路：读入父节点的时候，用size记录每个节点的孩子数量，同时寻找root节点。然后判断szie数组是否所有非0的元素都是相同的，则是yes否则no。最后dfs按照字典序先序遍历即可。

n = int(input())

# 存每个节点的孩子
edge = [[] for _ in range(n +1)]

# 存孩子个数
size = [0 ] *(n +1)
root = 0


def dfs(u):
    if u != root:
        print(end=' ')
    print(u, end='')
    for i in sorted(edge[u]):
        dfs(i)


for i in range(1, n+ 1):
    fa = int(input())
    edge[fa].append(i)
    size[fa] += 1
    if fa == 0:
        root = i

# 判断非叶子节点，是否孩子数都相同
mx_size, flag = max(size[1:]), 'yes'
for i in range(1, n + 1):
    if size[i] != 0 and size[i] != mx_size:
        flag = 'no'

print(mx_size, flag)
dfs(root)

L2-4 吉利矩阵

题目链接PTA | 程序设计类实验辅助教学平台

题意：每行每列的和要等于给定的和。

思路：dfs回溯，考虑到需要多次计算每行每列的和，索性不进行二维数组填表，直接两个数组一个row、col记录每行列的和，然后到达下和右边界的时候检查和。

可行性剪纸：下边界(该列已完成)或右边界（该行已完成）是否等于s。

可行性剪纸：当前和大于s。

然后Python最大范围的9 4需要50秒，直接改C++满分。

#include<bits/stdc++.h>

using namespace std;
int s, k;
// 记录每行每列的和
int row[5], col[5], cnt;

void dfs(int u){
    // 已经完成全部格子
    if(u==k*k){
        cnt++;
        return;
    }
    // 线性下标转二维下标
    int xx = u/k, yy=u%k;
    for(int i=0; i<=s; i++){
        // 到达下边界，检查该列
        if(xx==k-1 && col[yy] + i != s )
            continue;
        // 到达右边界，检查该行
        if(yy==k-1 && row[xx] + i != s)
            continue;
        // 当前和大于s，往后的i也会大于s
        if(col[yy] + i > s || row[xx] + i>s)
            break;

        // 对这个格子对应的行和列加上
        row[xx] += i;
        col[yy] += i;
        dfs(u+1);
        // 回溯，恢复现场
        row[xx] -= i;
        col[yy] -= i;
    }


}
int main() {
    cin>>s>>k;
    dfs(0);
    cout<<cnt;
    return 0;
}

L3-1 夺宝大赛

题目链接PTA | 程序设计类实验辅助教学平台

题意：一个有障碍物的二维网格，有很多个队伍去终点，同时达到的队伍直接失败，找非同时达到的队伍中最早到达的队伍。

思路：每个队伍都要去同一个终点且是最短路，所以直接从终点开始一次BFS得到每个格点到终点的最短距离。读入队伍查表该位置的最短距离，按照队伍编号存入ans数组，统计每个队伍的最短距离，如果出现相同的最短距离，则这些队伍全都失败ans记录距离为0失败。再查找非0的最小距离队伍编号。

这题是真的ex，最烦这种下标的题目了，前面出了两个就算了。你这个为什么下标反着给我？？？

前面两题n是行m是列，这里你给我m行n列。然后下标先给列再给行。没有比你更牛的。

def main():
    from sys import stdin
    input = lambda: stdin.readline().strip()
    m, n = map(int, input().split())

    # m行, n列
    maps = [[]]
    root_x, root_y = 0, 0
    for i in range(1, m + 1):
        row = [0] + list(map(int, input().split()))
        maps.append(row)
        if root_x != 0:
            continue
        for j, x in enumerate(row):
            # 寻找终点
            if x == 2:
                root_x, root_y = i, j

    # 终点开始一次BFS，得到每个网格去终点的最短距离
    def bfs(a, b):
        from collections import deque
        step = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        diss = [[0] * (n + 1) for _ in range(m + 1)]
        que = deque()
        que.append((a, b, 0))
        while que:
            x, y, cur_dis = que.popleft()
            diss[x][y] = cur_dis
            for dx, dy in step:
                xx, yy = x + dx, y + dy
                if 1 <= xx <= m and 1 <= yy <= n and maps[xx][yy] != 0:
                    maps[xx][yy] = 0
                    que.append((xx, yy, cur_dis + 1))
        return diss

    dis = bfs(root_x, root_y)

    k = int(input())
    ans = [0] * (k + 1)

    # 对于每个队伍，直接查表得到最短距离
    for i in range(1, k + 1):
        a, b = map(int, input().split())  # 列 行
        ans[i] = dis[b][a]

    # 统计每个队伍的最短距离出现次数
    dis_count = dict()
    for i in range(1, k + 1):
        x_dis = ans[i]
        dis_count[x_dis] = dis_count.get(x_dis, 0) + 1
    # 把最短距离出现1次以上的队伍全都pass掉
    for i in range(1, k + 1):
        x_dis = ans[i]
        if dis_count[x_dis] > 1:
            ans[i] = 0
    
    # 找pass掉之后的，非0最短距离的队伍编号
    if max(ans) == 0:
        print("No winner.")
    else:
        mi_dis = min(x for x in ans if x != 0)
        print(ans.index(mi_dis), mi_dis)

if __name__ == '__main__':
    main()