Problem A Points in Segments

题意

给你若干个区间，以及区间大小n,问你在区间$$[1,n]$$内没有被覆盖的点有哪些。

题解

乱搞，范围不大

#include <iostream>
#include <algorithm>
#include <cstring>
#include <array>
#include <vector>
using namespace std;
using ll = long long;
int arr[110];
vector<int>ans;
int main() {
    int num, tot;
    cin >> num >> tot;

    for (int i = 0; i < num; ++i) {
        int s, e;
        cin >> s >> e;
        for (int j = s; j <= e; ++j) {
            arr[j] = 1;
        }
    }
    int len = 0;
    for(int i = 1;i<=tot;++i) {
        if(!arr[i]) {
            ans.push_back(i);
        }
    }
    cout << (len = ans.size()) << "\n";
    for(int i = 0;i<len;++i) {
        if(i)cout << " ";
        cout << ans[i];
    }
    cout << "\n";
}

Problem B – Obtaining the String

题意

给你两个字符串$$s,t$$，你可以对s串进行操作，但不能对t串进行操作。
设$$s$$串中每一个字符为$$s_i$$,每一次可以交换$$s_i$$和$$s_j$$的位置。
问能否在$$10^4$$次操作内完成交换使得$$s == t$$
$$1 \leq|s| = |t| \leq 50$$
给出任意一组解
无解输出-1

题解

乍看好像没有什么头绪，其实可以贪心来解决。
从左往右扫，如果$$t[i] != s[i]$$,就找一个$$s[j] == t[i]$$,$$|j-i|=min$$ 交换。
考虑到不满足条件的可能只有两个字符串的各个字符集的容量不等
（如abc与abb）,所以只要在字符集相同的情况一定有解
乱搞一下

#include <iostream>
#include <algorithm>
#include <cstring>
#include <array>
#include <vector>
using namespace std;
using ll = long long;
int arr[110];
vector<int>ans;
int main() {
    string s,t;
    int len;
    cin >> len;
    cin >> s >> t;
    string cs,ct;
    cs = s,ct = t;
    sort(cs.begin(),cs.end());
    sort(ct.begin(),ct.end());
    if(cs != ct) {
        cout << -1 << "\n";
    }
    else {
        for (int i = 0; i < len; ++i) {
            if (s[i] == t[i]) {
                continue;
            } else {
                for (int j = i + 1; j < len; ++j) {
                    if (t[i] == s[j]) {
                        for (int k = j - 1; k >= i; --k) {
                            ans.push_back(k + 1);
                            swap(s[k], s[k + 1]);
                        }
                    }
                }
            }
        }
        cout << ans.size() << "\n";
        int sz = ans.size();
        for (int i = 0; i < sz; ++i) {
            if (i) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }
}

Problem C – Songs Compression

题意

手机容量为$$storage$$,每首歌的大小为$$s_i$$,压缩后为$$c_i$$
问最少压缩几首歌可以装下所有歌曲，若无解输出-1

题解

贪心，根据$$s_i – c_i$$降序排序取到符合条件即可
唯一的无解条件是$$\displaystyle\sum_i t_i > storage$$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <array>
#include <vector>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const int maxn = 1e5 + 6;
array<pll, maxn> song;

bool cmp(pll a, pll b) {
    return a.first - a.second > b.first - b.second;
}

int main() {
    int tot, storage;
    cin >> tot >> storage;
    ll sum1 = 0, sum2 = 0;
    for (int i = 0; i < tot; ++i) {
        ll a, b;
        cin >> a >> b;
        sum1 += a;
        sum2 += b;
        song[i].first = a;
        song[i].second = b;
    }
    if (sum2 > storage) {
        cout << -1 << '\n';
    } else {
        sort(song.begin(), song.begin() + tot, cmp);
        int ans = 0;
        for (int i = 0; i < tot && sum1 > storage; ++i) {
            sum1 -= song[i].first - song[i].second;
            ++ans;
        }
        cout << ans << "\n";
    }
}

Problem D – Walking Between Houses

题意

有$$n$$座房子，你的位置是1,房子的区间为$$[1,n]$$,房子之间距离为$$|i – j|$$,每次进行一次移动，需满足$$|i-j|>0$$
问能否在$$K$$次移动使$$\displaystyle\sum move = distance$$
无解输出NO
有解输出YES和具体方案，

题解

比较恶心的模拟
无解的情况是从$$1\to n$$走$$K$$次都无法大于等于$$distance$$
以及$$distance < K$$
每次模拟移动，移动的步数是$$jump = distance / K$$,若$$distance / K > 0$$，则$$jump = distance / K + 1 $$
然后$$distance -= jump$$,$$K-=1$$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n, k, s;
    while(~scanf("%lld%lld%lld", &n, &k, &s)){
        if(k > s || k*(n-1) < s){
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        ll cur = 1;
        while(k){
            ll t = s/k;
            if(s%k)
                t++;
            s -= t;
            if(cur > n/2){
                cur -= t;
            }
            else{
                cur += t;
            }
            printf("%lld ", cur);
            k--;
        }
        printf("\n");
    }
    return 0;
}

Problem E1 – Stars Drawing (Easy Edition)

题意

有这么一个星星长这个样 以次类推

..*..
.***.
..*..

问给定的图中由几个类似的星星组成，输出任意一组解即可，无解输出-1

题解

模拟 贪心取
注意做好标记就行

#include <iostream>
#include <algorithm>
#include <vector>
#include <regex>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const int maxn = 1e2 + 1e1;
array<array<int, maxn>, maxn> t;
array<array<char, maxn>, maxn> s;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, a, l;
    for (auto &i:s) {
        i.fill(0);
    }
    for (auto &i:t) {
        i.fill(0);
    }
    vector<pair<pii, int>> v;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> s[i][j];
            if (s[i][j] == '*') {
                t[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == '*') {
                a = 0;

                for (int x = i - 1; x >= 0; --x) {
                    if (s[x][j] == '*') { ++a; }
                    else { break; }
                }
                l = a;
                a = 0;
                for (int x = i + 1; x < n; ++x) {
                    if (s[x][j] == '*') { ++a; }
                    else { break; }
                }
                l = min(l, a);
                a = 0;
                for (int y = j - 1; y >= 0; --y) {
                    if (s[i][y] == '*') { ++a; }
                    else { break; }
                }
                l = min(l, a);
                a = 0;
                for (int y = j + 1; y < m; ++y) {
                    if (s[i][y] == '*') { ++a; }
                    else { break; }
                }
                l = min(l, a);

                if (l) {
                    v.push_back({{i + 1, j + 1}, l});
                    t[i][j] = 2;

                    for (int x = i - 1, u = l; u; --x, --u) {
                        t[x][j] = 2;
                    }

                    for (int x = i + 1, u = l; u; ++x, --u) {
                        t[x][j] = 2;
                    }

                    for (int y = j - 1, u = l; u; --u, --y) {
                        t[i][y] = 2;
                    }

                    for (int y = j + 1, u = l; u; ++y, --u) {
                        t[i][y] = 2;
                    }
                }
            }
        }
    }

    bool invalid = false;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (t[i][j] == 1) {
                invalid = true;
                break;
            }
        }
    }

    if (invalid) {
        cout << -1 << "\n";
    } else {
        cout << v.size() << "\n";
        for (auto i:v) {
            cout << i.first.first << " " << i.first.second << " " << i.second << "\n";
        }
    }
}