2024西北师范大学天梯赛选拔赛 题解

author : 星幻流空

A题：思路：

按照题意直接输出即可。

void solve()
{
    int n;
    cin >> n;
    if (n < 400) cout << "这活干不了一点了！";
    else if (n > 600) cout << "我要加倍干！";
    else cout << "这活我干的不亏";
}

B题：思路：

本次 B 题的测试用例存在错误，因此不予讲解。

C题：思路：

判断字符串的序列的 dfs 的数量，使用 标记，达到数量 + 1 即可

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int f = 1;
    int ans = 0;
    for (int i = 0; i < n; i ++ ){
        if (f == 1 && s[i] == 'd'){
            f = 2;
        }
        if (f == 2 && s[i] == 'f'){
            f = 3;
        }
        if (f == 3 && s[i] == 's'){
            f = 1;
            ans ++ ;
        }
    }
     
    cout << ans << endl;
}

D题：思路：

前缀和，计算一段区间的值，使用前缀和预处理即可。

void solve()
{
    int n, m;
    cin >> n >> m;
     
    int a[n + 1] = {0};
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
        a[i] += a[i - 1];
    }
     
    while (m -- ){
        int x, y;
        cin >> x >> y;
        cout << a[y] - a[x - 1] << endl;
    }
}

E题：思路：

字符串的缝合，使用substr函数操作直接实现即可。

void solve()
{
    string s;
    cin >> s;
     
    int n;
    cin >> n;
     
    while (n -- ){
        int a, b;
        string x, y;
        cin >> a >> b >> x >> y;
         
        string t = s.substr(a, b - a + 1); // 剪切字符串
        int idx = s.find(x + y); // 寻找插入位置
         
        if (idx == -1){ // 不存在插入末尾
            s += t;
            continue;
        }
        else { // 存在插入到指定位置
            idx += x.size();
            s = s.substr(0, idx) + t + s.substr(idx, s.size() - 1);
        }
    }
    
    cout << s << endl;  
}

F题：思路：

并查集，和中病毒感染者一个集合的都中病毒。

const int N = 1e3 + 10;
 
int p[N];
int n, m;

// 初始化
void init(){
    for (int i = 0; i <= n - 1; i ++ ){
        p[i] = i;
    }
}
 
// 查找
int find(int x){
    if (x != p[x]){
        p[x] = find(p[x]);
    }
    return p[x];
}

// 合并集合
bool merge(int x, int y){
    x = find(x), y = find(y);
    if (x == y){
        return 1;
    }
    p[x] = y;
    return 0;
}
 
void solve()
{
    init();
    while (m -- ){
        int k, idx;
        cin >> k;
        for (int i = 0; i < k; i ++ ){
            int t;
            cin >> t;
            if (i == 0) {
                idx = t;
                continue;   
            }
            merge(t, idx); // 默认都合并到第一个节点
        }
    }
    
    int ans = 0;
    for (int i = 1; i < n; i ++ ){
        if (find(i) == find(0)){ // 和 0 在一个集合，则中病毒
            ans ++ ;
        }
    }
     
    cout << ans + 1 << endl; // 也包括 0 因此 + 1
}

G题：思路：

map存储 相应的时间花钱，最后重新放在vector中进行排序即可。

void solve()
{
    int n, m;
    cin >> n >> m;
     
    map<string, int> ma;
    int ans = 0, sum = 0;
     
    for (int i = 0; i < n; i ++ ){
        string s;
        int x;
         
        cin >> s >> x;
         
        if (x >= m){
            ma[s] += 50;
            sum += 50;
        }
        else if (x < 60){
            ans ++ ;
        }
        else {
            ma[s] += 20;
            sum += 20;
        }
    }
    cout << sum << endl;
    if (ans >= 5) {
        cout << "(＞﹏＜)" << endl;
        return ;
    }
     
    vector<pair<string, int> > v;
     
    for (auto i : ma){ // map 存储到 vector 中
        v.push_back({i.first, i.second});
    }
     
    sort(v.begin(), v.end(), [&](PII x, PII y){
        if (x.second != y.second){ // 优先金钱排序
            return x.second > y.second;
        }
        else { // 其次时间排序
            return x.first < y.first;
        }
    });
     
    for (auto i : v){
        cout << i.first << " " << i.second << endl;
    }
     
}

H题：思路：

dijkstra 最简单的模板。

void solve()
{
    int n, m, s;
    cin >> n >> m >> s;
     
    vector<vector<PII> > g(n + 1);
    for (int i = 0; i < m; i ++ ){
        int u, v, w;
        cin >> u >> v >> w;
         
        g[u].push_back({w, v});
    }
     
    int d[n + 1];
    memset(d, 0x3f, sizeof(d));
    bool st[n + 1] = {false};
     
    priority_queue<PII, vector<PII>, greater<PII> > q;
     
    d[s] = 0;
    q.push({0, s});
     
    while (!q.empty()){
        auto t = q.top();
        int dist = t.first, x = t.second;
        q.pop();
         
        if (st[x]) continue;
        st[x] = true;
         
        for (int i = 0; i < g[x].size(); i ++ ){
            int j = g[x][i].second, p = g[x][i].first;
            d[j] = min (d[j], d[x] + p);
            q.push({d[j], j});
        }
         
    } 
     
    for (int i = 1; i <= n; i ++ ){
        cout << d[i] << " ";
    }
}