SMU 2024 spring 天梯赛3

7-1 重要的话说三遍 - SMU 2024 spring 天梯赛3 (pintia.cn)

I'm gonna WIN!
I'm gonna WIN!
I'm gonna WIN!

7-2 两小时学完C语言 - SMU 2024 spring 天梯赛3 (pintia.cn)

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,k,m;
    cin >> n >> k >> m;
    cout << max(n - k * m,0) << '\n';

    return 0;
}

7-3 拯救外星人 - SMU 2024 spring 天梯赛3 (pintia.cn)

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a,b,ans = 1;
    cin >> a >> b;
    for(int i = 1;i <= a + b;i ++)
        ans *= i;
    cout << ans << '\n';

    return 0;
}

7-4 谁能进图书馆 - SMU 2024 spring 天梯赛3 (pintia.cn)

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if (d >= b && c < a) {
        printf("%d-Y %d-Y\nqing 2 zhao gu hao 1", c, d);
    } else if (c >= b && d < a) {
        printf("%d-Y %d-Y\nqing 1 zhao gu hao 2", c, d);
    }else if(c >= a && d >= a){
        printf("%d-Y %d-Y\nhuan ying ru guan", c, d);
    }else if(c < a && d < a){
        printf("%d-N %d-N\nzhang da zai lai ba", c, d);
    }else if(c >= a){
        printf("%d-Y %d-N\n1: huan ying ru guan", c, d);
    }else{
        printf("%d-N %d-Y\n2: huan ying ru guan", c, d);
    }

    return 0;
}

7-5 试试手气 - SMU 2024 spring 天梯赛3 (pintia.cn)

每个骰子从6往下枚举n个,遇见有过的跳过即可;

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    vector<int> a(6);
    for (auto &i : a)cin >> i;
    cin >> n;
    
    for(int i = 0;i < 6;i ++){
        for(int j = 6,m = n;j >= 1 && m;j --){
            if(j == a[i]) continue;
            m--;
            if(!m) cout << j << " \n"[i == 5];
        }
    }

    return 0;
}

7-6 查验身份证 - SMU 2024 spring 天梯赛3 (pintia.cn)

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    const int w[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
    const char M[] = {'1','0','X','9','8','7','6','5','4','3','2'};

    vector<string> ans;
    while(n --){
        string s;
        cin >> s;
        int num = 0,f = 0;
        for(int i = 0;i < 17;i ++){
            if(s[i] < '0' || s[i] > '9'){
                ans.push_back(s);
                f = 1;
                break;
            }
            num += (s[i] - '0') * w[i];
        }
        if(f) continue;
        num %= 11;
        if(M[num] != s.back())
            ans.push_back(s);
    }

    if(!ans.size()) cout << "All passed\n";
    else{
        for(auto i : ans)
            cout << i << '\n';
    }
    return 0;
}

7-8 连续因子 - SMU 2024 spring 天梯赛3(补题) (pintia.cn)

按照滑动窗口的思想每次连乘,大于n时除掉前面的数;

维护连续乘的个数,大于ans时更新答案;

数据范围弱,可以直接枚举到n,因其有一个数据点最大因子超过\(\sqrt n\),也可以枚举到\(2 \times \sqrt n\),不过要注意特判素数;

素数判断时也超时,可以改下\(i \times i \leq n\)换成$ i \leq \sqrt n$,可能有奇效;

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	i64 n;
	cin >> n;

	auto ss = [](int x) {
		if (x < 2) return false;
		if (x == 2) return true;
		for (int i = 2; i <= sqrt(x); i ++)
			if (x % i == 0) return false;
		return true;
	};

	if (ss(n)) {
		cout << 1 << '\n' << n << '\n';
		return 0;
	}

	vector<i64> ans;
	i64 num = 0, res = 1, head = 2;
	for (int i = 2; i <= sqrt(n) * 2; i ++) {
		res *= i;
		num ++;
		if(!ans.size() && n % i == 0){
			ans.push_back(i);
		}
		while (res > n) {
			res /= head;
			head ++;
			num --;
		}
		if (n % res == 0) {
			if (num > ans.size()) {
				vector<i64>().swap(ans);
				for (int j = head; j <= i; j ++)
					ans.push_back(j);
			}
		}
	}

	cout << ans.size() << '\n';
	for (auto i : ans)
		cout << i << "*\n"[i == ans.back()];

	return 0;
}

7-8 出租 - SMU 2024 spring 天梯赛3 (pintia.cn)

模拟

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    vector<int> arr,vis(10),index(12);

    for(int i = 0;i < 11;i ++){
        int num = s[i] - '0';
        if(vis[num]) continue;
        arr.push_back(num);
        vis[num] = 1;
    }

    sort(arr.begin(),arr.end(),greater<>());
    for(int i = 0;i < arr.size();i ++){
        index[arr[i]] = i;
    }

    cout << "int[] arr = new int[]{";
    for(int i = 0;i < arr.size();i ++){
        cout << arr[i] ;
        if(i != arr.size() - 1) cout << ',';
    }
    cout << "};\n";
    cout << "int[] index = new int[]{";
    for(int i = 0;i < 11;i ++){
        cout << index[s[i] - '0'] ;
        if(i != 10) cout << ',';
    }
    cout << "};";

    return 0;
}

7-9 哈利·波特的考试 - SMU 2024 spring 天梯赛3 (pintia.cn)

Floyd处理出两两最短长度;

枚举每只动物能变成其余动物最长魔咒长度,取最小值;

若没有一只动物能变成其余各种动物,输出0;

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    typedef pair<i64, i64> PII;
    vector dis(n + 1, vector<i64>(n + 1, INT_MAX));
    for (int i = 0; i < m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = w;
        dis[v][u] = w;
    }

    for (int k = 1; k <= n; k ++) {
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (i == j) dis[i][j] = 0;
                if (dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }

    i64 ans = INT_MAX, f = 0, index = 0;
    for (int i = 1; i <= n; i ++) {
        i64 res = INT_MIN;
        for (int j = 1; j <= n; j ++) {
            if (dis[i][j] == INT_MAX) {
                res = INT_MIN;
                break;
            }
            res = max(res, dis[i][j]);
        }
        if (res < ans && res != INT_MIN) {
            ans = res, index = i;
        }
    }

    if (index) {
        cout << index << ' ' << ans << '\n';
    } else
        cout << 0 << '\n';

    return 0;
}

7-10 列车厢调度 - SMU 2024 spring 天梯赛3 (pintia.cn)

按题意模拟;

注意点是,1号车厢没有枚举完时若此时3号车厢满足条件,应该从3号转到2号;

具体例子:

ABCD
CBAD

output:

1->3
1->3
1->2
3->2
3->2
1->2

code:

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;

    stack<char> box;
    vector<string> ans;
    int index = s1.size() - 1;
    reverse(s1.begin(), s1.end());
    for (int i = 0; i < s2.size(); i ++) {
        if (!box.size() || box.top() != s2[i]) {
            while (index >= 0 && s1[index] != s2[i]) {
                box.push(s1[index]);
                ans.push_back("1->3");
                index --;
            }
        }

        if (index >= 0 && s1[index] == s2[i]) {
            ans.push_back("1->2");
            index --;
            continue;
        }
        if (box.size() && box.top() == s2[i]) {
            ans.push_back("3->2");
            box.pop();
        } else {
            cout << "Are you kidding me?\n";
            return 0;
        }
    }

    for (auto i : ans)
        cout << i << '\n';

    return 0;
}

7-11 文件传输 - SMU 2024 spring 天梯赛3 (pintia.cn)

并查集;

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

struct UFS {
    vector<int> fa;
    int n;
    UFS(int n): n(n) {
        fa.resize(n + 1);
        for (int i = 0 ; i <= n; i ++)
            fa[i] = i;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void unin(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) fa[x] = y;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    UFS ufs(n);
    char c;
    int c1, c2;
    while (cin >> c) {
        if (c == 'S') break;
        cin >> c1 >> c2;
        if (c != 'C') {
            ufs.unin(c1, c2);
        } else {
            c1 = ufs.find(c1);
            c2 = ufs.find(c2);
            if (c1 != c2) {
                cout << "no\n";
            } else
                cout << "yes\n";
        }
    }

    int num = 0;
    for (int i = 1; i <= n; i ++)
        if (ufs.find(i) == i) num ++;
    if(num == 1) cout << "The network is connected.\n";
    else cout << "There are " << num << " components.\n";

    return 0;
}

7-12 病毒溯源 - SMU 2024 spring 天梯赛3 (pintia.cn)

根节点不一定从0开始,但一定唯一,所以可以先找出根节点;

跑一遍dfs计算出最大深度;

然后对每个点的相连的点做一个排序;

再跑一遍dfs统计答案,当第一次跑到最大深度时即是最小序列;

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector g(n + 1, vector<int>());
    vector<int> fa(n);
    iota(fa.begin(),fa.end(),0);
    for (int i = 0; i < n; i ++) {
        int k;
        cin >> k;
        if (k) {
            for (int j = 0; j < k; j ++) {
                int x;
                cin >> x;
                g[i].push_back(x);
                fa[x] = i;
            }
        }
    }

    int root = 0;
    for(int i = 0;i< n;i ++){
        if(fa[i] == i) {
            root = i;
            break;
        }
    }

    for (int i = 0; i < n; i ++) {
        sort(g[i].begin(), g[i].end());
    }

    int mx = 0;
    auto dfs = [&](auto dfs, int u, int now) -> void{
        mx = max(now, mx);
        for (auto i : g[u]) {
            dfs(dfs, i, now + 1);
        }
    };

    dfs(dfs, root, 1);
    vector<int> ans;
    auto dfs1 = [&](auto dfs, int u, int now) -> void{
        if (now == mx) {
            cout << mx << '\n';
            for (auto i : ans)
                cout << i << " \n"[i == ans.back()];
            exit(0);
        }
        for (auto i : g[u]) {
            ans.push_back(i);
            dfs(dfs, i, now + 1);
            ans.pop_back();
        }
    };

    ans.push_back(root);
    dfs1(dfs1, root, 1);

    return 0;
}

7-14 天梯地图 - SMU 2024 spring 天梯赛3(补题) (pintia.cn)

dijkstra进阶做法,包含路径记录,以及按权重统计路径条件等;

不过最开始我一直将优先队列开的最大堆,但是一直过不了自己的例子,后来改成最小堆并且路径值改成负数存进去就对了,再后来我发现改成最大堆也可以,不过要把点值改成负数,最后才焕然大悟,这题路径取最短的同时,节点值也应该尽量的小(

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

struct DIJ {
    using i64 = long long;
    using PII = pair<i64, i64>;
    vector<i64> dis, path, node;
    vector<vector<array<int, 3>>> G;
    int n;

    DIJ() {}
    DIJ(int n): n(n) {
        node.resize(n + 1, 1);
        dis.assign(n + 1, 1e18);
        G.resize(n + 1);
        path.resize(n + 1, -1);
    }

    void add(int u, int v, int w, int val) {
        G[u].push_back({v, w, val});
    }

    void dijkstra(int s) {
        priority_queue<PII,vector<PII>,greater<PII>> que;
        dis[s] = 0;
        que.push({0, -s});
        while (!que.empty()) {
            auto p = que.top();
            que.pop();
            int u = -p.second;
            if (dis[u] < p.first) continue;
            for (auto [v, w, val] : G[u]) {
                if (dis[v] > dis[u] + w) {
                    node[v] = node[u] + val;
                    dis[v] = dis[u] + w;
                    que.push({ dis[v], -v});
                    path[v] = u;
                } else if (dis[v] == dis[u] + w) {
                    if (node[v] > node[u] + val) {
                        node[v] = node[u] + val;
                        path[v] = u;
                    }
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    DIJ time(n), way(n);
    while (m --) {
        int u, v, c, t, w;
        cin >> u >> v >> c >> w >> t;
        time.add(u, v, t, w);
        way.add(u, v, w, 1);
        if (!c) {
            time.add(v, u, t, w);
            way.add(v, u, w, 1);
        }
    }

    int st, ed, ok;
    cin >> st >> ed;
    time.dijkstra(st);
    way.dijkstra(st);

    ok = ed;
    vector<int> ans, ans1;
    while (ok != -1) {
        ans.push_back(ok);
        ok = time.path[ok];
    }
    ok = ed;
    while (ok != -1) {
        ans1.push_back(ok);
        ok = way.path[ok];
    }

    if (ans1 == ans) {
        cout << "Time = " << time.dis[ed] << "; ";
        cout << "Distance = " << way.dis[ed] << ": ";
        for (int i = ans1.size() - 1; i >= 0; i --) {
            cout << ans1[i] ;
            if (i) cout << " => ";
            else cout << '\n';
        }
    } else {
        cout << "Time = " << time.dis[ed] << ": ";
        for (int i = ans.size() - 1; i >= 0; i --) {
            cout << ans[i] ;
            if (i) cout << " => ";
            else cout << '\n';
        }
        cout << "Distance = " << way.dis[ed] << ": ";
        for (int i = ans1.size() - 1; i >= 0; i --) {
            cout << ans1[i] ;
            if (i) cout << " => ";
            else cout << '\n';
        }
    }

    return 0;
}