2024年天梯赛个人部分题解

写在前头

天梯赛的赛时是可以选择不同的语言提交的，对于 L1 的简单题，使用 Python 做起来效率一般更高，尤其是字符串处理，写起来轻松。所以这里的 L1 题解就不给 C++ 实现了。

L1

L1-1 编程解决一切

题目链接

签到题，直接打印 Problem? The Solution: Programming. 即可。

python 实现

print("Problem? The Solution: Programming.")

L1-2 再进去几个人

题目链接

题目中数学家的意思就是，再进去一个人房子就为空（00）了，所以直接求 b−ab - a 即可。

a, b = list(map(int, input().strip().split()))
print(b - a)

L1-3 帮助色盲

题目链接

题目关键信息提取：当前交通灯为红灯或绿灯时，检测其前方两米内是否有同向行走的人 —— 如果有，则患者自己可以判断，程序就不做提示；如果没有，则根据灯的颜色给出不同的提示音。黄灯也不需要给出提示。

可以看得出一个简单的 if-elif-else 就可以解决。

python 实现

a, b = list(map(int, input().strip().split()))
if a == 0: #red
    print("{}\nstop".format('-' if b == 1 else "biii"))
elif a == 1: #green
    print("{}\nmove".format('-' if b == 1 else "dudu"))
else: # yellow
    print("-\nstop")

L1-4 四项全能

题目链接

通过题意我们容易想到，结果应该是 sumkmod  nsum_k \mod n ，但是交上去后 wa 了两个点，考虑特殊情况，当 sumkmod  n=0sum_k \mod n = 0 时，应该是正好分完，也就是有 nn 个人 mm 项都会。对于 n×(m−1)>sumkn \times {(m - 1)} > sum_k 时，数据不满足 nn 个人 m−1m - 1 项都会的情况，那么更不可能满足有人 mm 项都会，直接输出 00 。

python 实现

n, m = list(map(int, input().strip().split()))
s = sum(list(map(int, input().strip().split())))
ans = s % n
if ans == 0:
    print(n)
elif n * (m - 1) > s:
    print(0)
else:
    print(ans)

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

题目链接

这题说的就是给你 nn 个需要替换成 <censored> 的字符串，然后给你一个最大替换次数 kk 和需要替换的字符串 ss ，问你替换之后的结果。

对于这题，主要是一个坑：对于替换成 <censored> 后的结果，可能会产生新的违禁词，导致不应该的替换，所以需要替换成一个题目中不可能出现的字符串或者字符。但是题目的字符范围覆盖 ASCII 码范围，处理起来不方便，这里我们就可以用我们天天用的，高贵的 Unicode 码字符——中文字符，这样就避免了这个问题。此外，记得输出的时候把字符转回 <censored> 。

其他方面就是语言特性，C++ 的查找替换是针对单个元素的，需要跑循环来完成操作，而 Python 的替换是针对全部的。

python 实现

lst = [input() for _ in range(0, int(input()))]
k = int(input())
s = input()
cnt = 0
for l in lst:
    cnt += s.count(l)
    s = s.replace(l, "中")
if cnt < k:
    print(s.replace("中", "<censored>"))
else:
    print(cnt)
    print("He Xie Ni Quan Jia!")

L1-6 兰州牛肉面

题目链接

这题的写码难度比上题简单，用一个列表存一下价格，然后暴力模拟算就好了.

n = int(input())
lst = list(map(float, input().strip().split()))
cnt = [0 for _ in range(0, n)]
ans = 0.0
a, b = list(map(int, input().strip().split()))
while a != 0:
    ans += lst[a - 1] * b
    cnt[a - 1] += b
    a, b = list(map(int, input().strip().split()))
for i in cnt:
    print(i)
print("{:.2f}".format(ans))

L1-7 整数的持续性

题目链接

这题，容易想到用 dfs 搜索结果，加快运算。将每次递归的结果用字典（哈希表）存起来，下次搜到就直接返回，这样就可以减少计算的次数。当然暴力枚举好像也能过。

python 实现

dic = {}
def dfs(v):
    if v < 10:
        return 0
    if dic.get(v, 0) != 0:
        return dic[v]
    x = 1
    for i in [int(i) for i in str(v)]:
        x *= i
    dic[v] = 1 + dfs(x)
    return dic[v]

a, b = list(map(int, input().strip().split()))
maxn = 0
ans = []
for i in range(a, b + 1):
    v = dfs(i)
    if v > maxn:
        maxn = v
        ans = [i]
    elif v == maxn:
        ans.append(i)
print(maxn)
for i in ans[:-1]:
    print(i, end = ' ')
print(ans[-1])

L1-8 九宫格

题目链接

这题也是一道简单的模拟题，考虑枚举每一列，每一行和九个 3×33 \times 3 的矩形是否成立即可。

mat = []
def row(x):
    vis = [False for _ in range(10)]
    for i in range(9):
        v = mat[x][i]
        if v >= 10 or v <= 0 or vis[v]:
            return False
        vis[v] = True
    return True

def col(y):
    vis = [False for _ in range(10)]
    for i in range(9):
        v = mat[i][y]
        if v >= 10 or v <= 0 or vis[v]:
            return False
        vis[v] = True
    return True

def mat33(x, y):
    vis = [False for _ in range(10)]
    for i in range(3):
        for j in range(3):
            px, py = x + i, y + j
            v = mat[px][py]
            if v >= 10 or v <= 0 or vis[v]:
                return False
            vis[v] = True
    return True

for _ in range(int(input())):
    mat = [list(map(int, input().strip().split())) for _ in range(9)]
    ans = True
    for i in range(9):
        ans = ans and row(i)
    for i in range(9):
        ans = ans and col(i)
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            ans = ans and mat33(i, j)
    print(1 if ans else 0)

L2

L2-1 鱼与熊掌

题目链接

题目翻译一下就是，给定 nn 个长度不同的数组，数组可能含有 [1,k][1, k] 的任意数字，对于 qq 次查询，每次给出数字 ll 和 rr ，问你有多少个集合同时包含这两数字。

这两思路理论上都是能过的，但是咋玩都被题目卡，开set就MLE，不开就TLE，陈越怕不是在恶心python选手

思路一

一开始容易想到并查集来维护，但是并查集的空间占用为 n×mn \times m ，对于题目给定的范围，会MLE，所以考虑使用集合来维护我们的这个“数组”。因为集合的有序性，在查询时的复杂度仅为 O(log⁡n)O(\log{n}) ，插入预处理元素的时间复杂度也为 O(log⁡n)O(\log{n}) 。总体时间复杂度为 O(nlog⁡n)O(n\log{n}) 。

python 实现

大体思路没问题，换C++能过，但是py卡一个点tle，如果换set就三个点mle，真是神奇

from bisect import bisect_left
n, m = list(map(int, input().strip().split()))
sets = [sorted(list(map(int, input().strip().split()))[1:]) for _ in range(n)]
q = int(input())
while q != 0:
    l, r = list(map(int, input().strip().split()))
    ans = 0
    for s in sets:
        pl, pr = bisect_left(s, l), bisect_left(s, r)
        if pl != len(s) and pr != len(s) and l == s[pl] and r == s[pr]:
            ans += 1
    q -= 1
    print(ans)

C++实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const char &ln = '\n';

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n, m;
    cin >> n >> m;
    vector<set<i64> > sets(n);
    for(auto &&set : sets) {
        i64 k;
        cin >> k;
        for(i64 i = 0, x; i < k; ++i) {
            cin >> x;
            set.emplace(x);
        }
    }
    i64 q, l, r;
    cin >> q;
    while(q--) {
        cin >> l >> r;
        i64 ans = 0;
        for(auto &&set : sets) 
            ans += set.count(l) and set.count(r);
        cout << ans << ln;
    }
}

思路二

和思路一差不多，只不过思路一的集合元素和数组的下标互换了，查询的时候取交集即可。看不懂可以看代码，但是这个思路的py代码仍然TLE最后一个点，感觉出题人真的是恶心py选手到爆

python实现

n, m = list(map(int, input().strip().split()))
sets = [[] for _ in range(m + 1)]
for cnt in range(n):
    for j in list(map(int, input().strip().split()))[1:]:
        sets[j].append(cnt)
for _ in range(int(input())):
    l, r = list(map(int, input().strip().split()))
    print(len(set(sets[l]) & set(sets[r])))

C++实现

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const char &ln = '\n';

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n, m;
    cin >> n >> m;
    vector<set<i64> > sets(m + 1);
    for (i64 i = 0; i < n; ++i) {
        i64 k;
        cin >> k;
        for (i64 _ = 0, x; _ < k; ++_) {
            cin >> x;
            sets[x].emplace(i);
        }
    }
    i64 q, l, r;
    cin >> q;
    while (q--) {
        cin >> l >> r;
        set<i64> ans;
        // 求交集
        set_intersection(sets[l].begin(), sets[l].end(),
                         sets[r].begin(), sets[r].end(),
                         inserter(ans, ans.begin()));
        cout << ans.size() << ln;
    }
}

L2-2 懂蛇语

题目链接

这题的题目翻译一下就是

给你一个包含 nn 个明文的字典，保证铭文由小写英文字母和空格组成。给你 mm 个密文，问你查询的结果。如果有多个结果，每个结果中间用 | 分隔，查不到就原样打出密文。

查询的方法就是字符串中空格后的单词的首字符组成的字符串。比如说，hello, i am winterl, nice to meet you in my blog. 对应的密钥就是 hiawntmyimb ，构造字典和查询字典的时候都用这个方法求密钥，再通过密钥查找即可

这题有几个坑就是：

  • 明文或者密文可能会有前导空格，处理的时候就给你埋雷.
  • 明文可能会有一模一样的，就是说，会有重复的明文，用set存就过不了了，最好就是用多重集，不用排序

这题说简单点就是一道模拟题，不过全是坑。

陈越出的字符串题，心系yue人每一题

Python 实现

from sys import stdin
from collections import defaultdict
def to_head(s):
    return "".join([x[0] for x in s.split()])
dic = defaultdict(list)
for _ in range(int(stdin.readline())):
    s = stdin.readline()[:-1]
    dic[to_head(s)].append(s)
for key in dic:
    dic[key].sort()
for _ in range(int(stdin.readline())):
    s = stdin.readline()[:-1]
    ans = dic.get(to_head(s), "无")
    print(s if ans == "无" else "|".join(ans))

C++ 实现

#include <bits/stdc++.h>  
using namespace std;  
using i64 = long long;  
const char &ln = '\n';  

signed main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    i64 n;  
    cin >> n;  
    cin.ignore();  
    auto &&to_head = [](const string &s) {  
        vector<char> res;  
        if (s[0] != ' ')  
            res.emplace_back(s[0]);  
        auto &&len = s.length();  
        for (auto p = s.find(' '); p != string::npos; p = s.find(' ', p + 1)) {  
            auto tmp = p + 1;  
            if (tmp < len and s[tmp] != ' ')  
                res.emplace_back(s[tmp]);  
        }  
        return res;  
    };  
    map<vector<char>, multiset<string> > dict;  
    string s;  
    while(n--) {  
        getline(cin, s);  
        dict[to_head(s)].emplace(s);  
    }  
    i64 q;  
    cin >> q;  
    cin.ignore();  
    while(q--) {  
        getline(cin, s);  
        auto &&ans = dict[to_head(s)];  
        // static_cast 静态强制类型转换，主要是用来消警告，不写不影响结果
        i64 cnt = static_cast<i64>(ans.size() - 1);  
        if(cnt == -1) {  
            cout << s << ln;  
            continue;  
        }  
        for(auto &&i : ans) {  
            cout << i;  
            if(cnt--)  
                cout.put('|');  
        }  
        cout.put(ln);  
    }  
}

L2-3 满树的遍历

题目链接

题目简要意思就是，给你一颗树。输出这颗树的度，是不是满 kk 叉树（ kk 未知，需要自己处理），该树的前序遍历。

题目给出的树本身是 父亲表示法 ，为了方便，我们建树的时候应该考虑将其转变成 父亲孩子表示法。然后枚举判断 kk 的同时求出树的度即可。最后打印出前序遍历的结果

题解
#天梯赛
2024年天梯赛个人部分题解
https://winterl-blog.netlify.app/2024/05/01/2024年天梯赛题解/
作者
winterl
发布于
2024年5月1日
许可协议