西南民族大学2023天梯选拔赛

题目列表 - 编程题 - 西南民族大学2023天梯选拔赛 (pintia.cn)

L1-1 谢谢卡尔！

签到题

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
#define ll long long
const int N = 2e5 + 7;
const int mod = 10007;
int a[N];
int b[N];
int v[N];
int f[105][N];
void solve(){
    cout << "谢谢卡尔！\\(>_<)/";
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L1-2 现在是，幻想时间！

模拟题

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>

using namespace std;
#define ll long long
const int N = 2e5 + 7;
const int mod = 10007;
int a[N];
int b[N];
int v[N];
int f[105][N];
void solve(){
    double n,t;cin >> n >> t;
    cout << fixed << setprecision(3) << n / t << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L1-3 你是来陪可莉炸鱼的吗?

模拟

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
using namespace std;
#define ll long long
const int N = 1e3 + 7;
const int mod = 10007;
int a[N];
int b[N];
int v[N];
int f[N];
void solve(){
    int n;cin >> n;
    ll res = 0;
    for (int i = 1; i <= n; ++i){
        ll x;cin >> x;
        if (x < 100)res += 1;
        else if(x >= 100 && x < 200)res += 2;
        else if(x < 300 && x >=200)res += 5;
        else if(x >= 300 && x < 400)res += 10;
        else res += 15;
    }
    cout << res;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L1-4 扫雷游戏

暴力模拟，范围很小

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
using namespace std;
#define ll long long
const int N = 1e3 + 7;
const int mod = 10007;
int b[N];
char a[20][20];
char res[20][20];
int n,m;
int dx[] = {-1,-1,-1,0,0,0,1,1,1};
int dy[] = {-1,0,1,-1,0,1,-1,0,1};
int check(int x,int y){
    int bc = 0;
    for (int i = 0;i < 9;i++){
        int u = x + dx[i],v = y + dy[i];
        if (u < 1 || u > n || v < 1 || v > m)continue;
        if (a[u][v] == '*')bc++;
    }
    return bc;
}
void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j){
            if (a[i][j] == '*'){
                res[i][j] = '*';
                continue;
            }
            int d = check(i,j);
            if (d == 0)res[i][j] = '.';
            else res[i][j] = d + '0';
        }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            cout << res[i][j];
        cout << endl;
    }

}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L1-5 史莱姆

模拟合并即可

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
using namespace std;
#define ll long long
const int N = 2e3 + 7;
const int mod = 10007;
int b[N];
char a[N];
int n,m;
void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    string res;
    char last = a[1];
    for (int i = 2; i <= n; ++i){
           if (last == a[i])continue;
           else
               res.push_back(last),last = a[i];
    }
    res.push_back(last);
    cout << res.size() << endl;
    cout << res;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L1-6 加密通信

哈希表映射后模拟即可

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
#include <unordered_map>
using namespace std;
#define ll long long
const int N = 2e3 + 7;
const int mod = 10007;
int b[N];
char a[N];
int n,m,k;
void solve(){
    cin >> n >> k;
    unordered_map<char,int> f;
    string s;cin >> s;
    k %= n;
    char j = 'a';
    for (int i = 1; i <= 26; ++i,j++){
        int x;cin >> x;
        f[j] = x;
    }
    string res;
    for (int i = n - 1 - k + 1; i < n ; ++i)
        res.push_back(s[i]);
    for (int i = 0; i < n - k + 1 - 1; ++i)
        res.push_back(s[i]);
    vector<int> r;
    for (auto x : res){
        r.push_back(f[x]);
    }
    for (auto x : r)
        cout << x;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L1-7 字符操作

这题就很妙了，你不需要去考虑调换的事情，你只需考虑前一半和后一半，在考虑是相同区域的调换还是不同区域的调换，再考虑对调的次数奇偶性就可以了

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
#include <unordered_map>
using namespace std;
#define ll long long
const int N = 5e5 + 7;
const int mod = 10007;
char a[N];
int n,m,k;
void solve(){
    cin >> n;n *= 2;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    string b ;
    cin >> k;
    int cg = 0;
    for (int i = 1; i <= k; ++i){
           int t,x,y;cin >> t >> x >> y;
           if (t == 1){
                if (cg % 2 == 0)
                    swap(a[x],a[y]);
                else{
                    if (x > y)swap(x,y);
                    if (y > n / 2 && x <= n / 2){
                        swap(a[y % (n / 2)],a[x + n / 2]);
                    }else if(x > n / 2 && y > n / 2){
                        swap(a[x - n / 2],a[y - n / 2]);
                    }else {
                        swap(a[x + n / 2],a[y + n / 2]);
                    }
                }
           }else{
               cg++;
           }
    }
    if (cg % 2) {
        for (int i = n / 2 + 1; i <= n; ++i)
            b.push_back(a[i]);
        for (int i = 1; i <= n / 2; ++i)
            b.push_back(a[i]);
    }else {
        for (int i = 1; i <= n; ++i)
            b.push_back(a[i]);
    }
    cout << b;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L1-8 vivo50！

结构体排序模拟

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define ll long long
const int N = 2e4 + 7;
const int mod = 10007;
int n,m,k;
struct stu{
    string name;
    double gpa;
    double deyu,ziyu;
    int ye;
}a[N];
struct sch{
    string name;
    double poi;
}b[N];
bool cmp(sch x,sch y){
    if (x.poi == y.poi)return x.name < y.name;
    return x.poi > y.poi;
}
void solve(){
    cin >> n >> k;
    int cnt = 0;
    for (int i = 1; i <= n; ++i){
        stu x;
        cin >> x.name >> x.gpa >> x.deyu >> x.ziyu >> x.ye;
        if (x.ye == 0)continue;
        a[++cnt].name = x.name,a[cnt].gpa = x.gpa,a[cnt].deyu = x.deyu,a[cnt].ziyu = x.ziyu,a[cnt].ye = x.ye;
        b[cnt].name = x.name,b[cnt].poi = (x.gpa * 10 + 50 + x.ziyu) * 0.7 + min(100.0,x.deyu + 70) * 0.3;
    }
    sort(b + 1,b + cnt + 1,cmp);
    int fi = 0;
    double last = 0;
    int len = 1;
    for (int i = 1;i <= cnt && fi <= k ;i++){
        if (abs(b[i].poi - last) > 1e-4)fi += len ,last = b[i].poi,len = 1;
        else len++;
        if (fi > k)break;
        cout << fi << " " << b[i].name << " " << fixed <<setprecision(1) <<b[i].poi << endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L2-1 游戏圈

并查集

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define ll long long
const int N = 1e6 + 7;
const int mod = 10007;
int f[N];
int n,m,q;
int find(int a){return f[a] == a ? a : f[a] = find(f[a]);}
int meger(int x,int y){
    int a = find(x),b = find(y);
    if (a != b)
        f[a] = b;
}
void solve(){
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    for (int i = 1; i <= m; ++i){
        int x,y;cin >> x >> y;
        meger(x,y);
    }
    for (int i = 1; i <= n; ++i)
        f[i] = find(f[i]);
    for (int i = 1; i <= q; ++i){
        int x,y;cin >> x >> y;
        if (f[x] == f[y])cout << "yes\n";
        else
            cout << "no\n";
    }
    set<int> h;
    for (int i = 1; i <= n; ++i)
        h.insert(f[i]);
    cout << h.size();
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L2-2 组套题

模拟！

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 1e2 + 7;
const ll mod = 1e9;
struct Node{
    int id,num;
    Node(int _id,int _num){id = _id,num = _num;}
};
bool cmp(Node a,Node b){
    if (a.id == b.id)return a.num < b.num;
    return a.id < b.id;
}
int n;
int cnt[17];
void solve(){
    cin >> n;
    int count = 0;
    vector<Node> res[N];
    queue<Node> rest[N];
    for (int i = 1; i <= 10; ++i) cin >> cnt[i],count += cnt[i];
    for (int i = 1; i <= n; ++i){
        int nums;cin >> nums;
        for (int j = 1; j <= nums; ++j){
            char c;int x,y;
            cin >> c;
            scanf("%d-%d",&x,&y);
            if (cnt[x])cnt[x]--,res[x].emplace_back(i,y);
            else rest[x].emplace(i,y);
        }
    }
    for (int i = 1; i <= 10; ++i){
        if (!cnt[i])continue;
        for (int j = i + 1; j <= 10 && cnt[i]; ++j){
            while (!rest[j].empty() && cnt[i]) {
                cnt[i]--;
                res[j].push_back(rest[j].front());
                rest[j].pop();
            }
        }
        for (int j = i - 1; j >= 1 && cnt[i]; --j){
            while (!rest[j].empty() && cnt[i]) {
                cnt[i]--;
                res[j].push_back(rest[j].front());
                rest[j].pop();
            }
        }
    }
    for (int i = 1; i <= 10; ++i) {
        if(res[i].empty())continue;
        sort(res[i].begin(),res[i].end(),cmp);
        for (int j = 0; j < res[i].size(); ++j){
                count--;
                if (count == 0){
                    cout << res[i][j].id << '-' << res[i][j].num;
                }else
                    cout << res[i][j].id << '-' << res[i][j].num << " ";
        }
    }
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    int _ = 1;//cin >>_;
    while (_--){
        solve();
    }
}

L2-3 简单的数数

dp，赛时不知道为什么调不出来，赛后秒过，晕了

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define ll long long
const int N = 1e5 + 7;
const ll mod = 998244353;
int a[N];
int n,m,q;
ll f[N][20];
void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    f[1][a[1]]++;
    for (int i = 2; i <= n; ++i){
        for (int j = 0; j <= 9; ++j){
            if (!f[i - 1][j])continue;
            f[i][(j * a[i]) % 10] += f[i - 1][j];
            f[i][(j * a[i]) % 10] %= mod;
            f[i][(j + a[i]) % 10] += f[i - 1][j];
            f[i][(j + a[i]) % 10] %= mod;
        }
    }
    for (int i = 0; i < 10; ++i)
        cout << f[n][i] % mod << endl;

}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr),cin.tie(nullptr);
    int _ = 1; //cin >> _;
    while (_--){
        solve();
    }
}

L2-4 回家日

最短路问题，跑dijkstra，考虑把解封日期当作距离

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 7;
const ll mod = 1e9;
int n,m,k;
int dist[N];
int a[N];
struct Node{
    int y,v;
    Node(int _y,int _v){y = _y,v = _v;}
};
vector<Node> edge[N];
void Dijkstra(){
    memset(dist,127,sizeof(dist));
    dist[k] = a[k];
    set<pair<int,int>> q;
    for (int i = 1; i <= n; ++i)
        q.emplace(dist[i],i);
    while (!q.empty()){
        int x = q.begin() -> second;
        q.erase(q.begin());
        for (auto i:edge[x]){
            if (dist[i.y] > max(a[i.y],dist[x])){
                q.erase({dist[i.y],i.y});
                dist[i.y] = max(a[i.y],dist[x]);
                q.emplace(dist[i.y],i.y);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (i == n)
            cout << dist[i];
        else
            cout << dist[i] << " ";
    
    }
}
void solve(){
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i){
        int x;cin >> x;
        a[x] = i;
    }
    for (int i = 1; i <= m; ++i){
        int u,v;cin >> u >> v;
        edge[u].emplace_back(v,max(a[v],a[u]));
        edge[v].emplace_back(u,max(a[v],a[u]));
    }
    Dijkstra();
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    int _ = 1;//cin >>_;
    while (_--){
        solve();
    }
}