2023.07.21 SMU Summer 2023 Contest Round 5

A. Points in Segments

给n个，1～m的子集，求1～n中所有没在这些子集中出现过的数字

把子集区间合并为集合s，输出1～n中没有在s中出现过的数

#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;

int n, m;
vector<PII> segs;
vector<bool> mark(110);

void merge() {
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

void solve() {
    merge();

    for(auto [i, j] : segs) {
//        cout << i << ' ' << j << endl;
        for(int pos = i; pos <= j; pos ++) {
            mark[pos] = true;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= m; i++) {
        if(!mark[i]) cnt ++;
    }
    cout << cnt << endl;
    if(cnt == 0) {
        return;
    }
    for(int i = 1; i <= m; i++) {
        if(!mark[i]) cout << i << " ";
    }

}

signed main() {

    cin >> n >> m;

    while(n--) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    solve();
}

~B. Obtaining the String

给定两个长度相等的字符串，通过每次交换相邻两个字符的操作，把第一个字符串调整为第二个字符串，问最少的操作数和每次操作所交换元素的第一个元素的下标

第一次读错题以为字符串中没有相同的字母，所以这么做了：把第二个字符串的字母，映射成它的下标，则第一个字符串就可以转换为一个数字串，冒泡排序即可

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

vector<int> arr(100);
vector<int> ans;
int cnt;

void bubbleSort(vector<int> &arr, int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素位置
                cnt++;
                ans.push_back(j + 1);

                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swapped = true;
            }
        }
        if (!swapped) {
            return;
        }
    }
}

signed main(){
    int n;
    string s1, s2;
    cin >> n;
    cin >> s1 >> s2;

    map<char, int> mp;
    for(int i = 0; i < n; i++) mp[s2[i]] = i;

    for(int i = 0; i < n; i++) {
        if (mp.find(s1[i]) == mp.end()) {
            // 如果 s1[i] 不在 s2 中出现
            cout << -1;
            return 0;
        }
        arr[i] = (mp[s1[i]]);
    }

    bubbleSort(arr, n);

    cout << cnt << endl;
    for(int i : ans) cout << i << ' ';
    cout << endl;
}

如果有相同的字符则不能这么映射了，因为后一个字符会把前一个相同的字符的映射给覆盖掉，所以把mp.first的类型改成queue来维护相同字母的序号即可

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

vector<int> arr(100);
vector<int> ans;
int cnt;

void bubbleSort(vector<int> &arr, int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素位置
                cnt++;
                ans.push_back(j + 1);

                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swapped = true;
            }
        }
        if (!swapped) {
            return;
        }
    }
}

signed main(){
    int n;
    string s1, s2;
    cin >> n;
    cin >> s1 >> s2;

    //判断是否可以排序成一样的，只要判断两个字符串中每个字母的个数是否分别相等即可
    int ok[30] = {0};
    for(int i = 0;i < n;i++) {
        ok[s1[i] - 96]++;
        ok[s2[i] - 96]--;
    }
    for(int i = 1;i <= 26;i++) {
        if(ok[i] != 0) {
            cout<<-1;
            return 0;
        }
    }


    map<char, queue<int>> mp;
    for(int i = 0; i < n; i++) mp[s2[i]].push(i);

    for(int i = 0; i < n; i++) {
//        if (mp.find(s1[i]) == mp.end()) {
//            // 如果 s1[i] 不在 s2 中出现
//            cout << -1;
//            return 0;
//        }//由于可能存在多个相同的字母，例如，s2中有两个a，而s1中只有一个，这么写检测不出来
        arr[i] = mp[s1[i]].front();
        mp[s1[i]].pop();
    }

    bubbleSort(arr, n);

    cout << cnt << endl;
    for(int i : ans) cout << i << ' ';
    cout << endl;
}

*C. Songs Compression

Ivan有n首歌,第i首歌原始大小为ai,压缩后为bi。他有一个容量为m的U盘。
他想把所有歌复制到U盘中,可以选择任意歌曲压缩,使得总大小不超过m。
求最少需要压缩的歌曲数,如果无法完成则输出-1。

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

#define int long long
// 定义长长整型便于处理大数

int n, m, t1, t2;
// n:歌曲数 m:U盘容量
// t1:所有歌曲压缩后大小总和 t2:所有歌曲原始大小总和

vector<pair<int, int>> t;
// t数组存储每首歌的(原始大小,压缩后大小)

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first - a.second > b.first - b.second;
}
// cmp函数用于排序,按压缩效果从大到小排序

signed main() {

    cin >> n >> m;

    t.resize(n);

    for(int i = 0; i < n; i++){
        cin >> t[i].first >> t[i].second;
        t1 += t[i].second;
        t2 += t[i].first;
    }
    // 读入输入,计算t1和t2

    if(t1 > m){
        cout << -1;
        return 0;
    }
    // 判断压缩后是否能装下,不能则输出-1

    sort(t.begin(), t.end(), cmp);
    // 排序

    for(int i = 0; i < n; i++){
        if(t2 <= m) {
            cout << i;
            return 0;
        }
        t2 -= t[i].first - t[i].second;
    }
    // 贪心算法,从效果最大的开始压缩,直到容量满足

    cout << n;

    return 0;
}