B. Triangles on a Rectangle

因为保证了每一个边上都有点，所以相当于三角形的高已经确定了。最大化底即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e15;

using ll = long long;

void solve() {
    int w, h, res = 0;
    cin >> w >> h;
    int n, l, r;
    cin >> n, l = LLONG_MAX, r = LLONG_MIN;
    for (int i = 1, x; i <= n; i++) {
        cin >> x, l = min(l, x), r = max(r, x);
    }
    res = max(res, (r - l) * h);
    cin >> n, l = LLONG_MAX, r = LLONG_MIN;
    for (int i = 1, x; i <= n; i++) {
        cin >> x, l = min(l, x), r = max(r, x);
    }
    res = max(res, (r - l) * h);
    cin >> n, l = LLONG_MAX, r = LLONG_MIN;
    for (int i = 1, x; i <= n; i++) {
        cin >> x, l = min(l, x), r = max(r, x);
    }
    res = max(res, (r - l) * w);
    cin >> n, l = LLONG_MAX, r = LLONG_MIN;
    for (int i = 1, x; i <= n; i++) {
        cin >> x, l = min(l, x), r = max(r, x);
    }
    res = max(res, (r - l) * w);
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

C. BA-String

这里的\(a\)其实不会影响到比较，只是作为分隔符。如果**则这一区间内可以放\(2k\)个\(b\)

其实可以想到，贪心的在后侧放是最优解。这样话，就可以转换成一个类似进制转换的题目。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e15;

using ll = long long;

void solve() {
    int n, k, x;
    string s, res = "\n";
    cin >> n >> k >> x >> s, x --;
    reverse(s.begin(), s.end());
    s += 'a';
    for (int cnt = 0, t; auto i: s) {
        if (i == '*') cnt++;
        else {
            t = cnt * k + 1;
            res += string(x % t, 'b') + 'a';
            x /= t, cnt = 0;
        }
    }
    res.pop_back();
    reverse( res.begin(), res.end() );
    cout << res;
    return;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

D. Exact Change

这题要想到的是\(1,2\)的数量最多为\(2\)，因为当数量大于\(2\)时，一定可以用若干个\(3\)来替代。

这样的话，我们就可以枚举\(1,2\)的数量，并根据最大值来判断\(3\)的数量。为了便于计算，可以上下浮动\(3\)的数量，再逐个判断每个数是否可以被构成即可。

注意判断数能否被构成时，不可采用贪心的策略。反例就是当硬币为\(2,2,3\)时，是可以组合出\(4\)的。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, res = LLONG_MAX, m = 0;
    cin >> n;
    vector<int> v(n);
    for (auto &i: v)
        cin >> i, m = max(m, i);
    m /= 3;
    for (int a = 0; a < 3; a++)
        for (int b = 0; b < 3; b++)
            for (int c = max(0ll, m - 5); c <= m + 5; c++) {
                if( a + b + c >= res ) continue;
                int flag = 1;
                for (auto t: v) {
                    int f = 0;
                    for (int i = 0; f == 0 and i <= a; i++)
                        for (int j = 0, p; f == 0 and j <= b; j++) {
                            p = t - i - j * 2;
                            if (p % 3 or p < 0 ) continue;
                            if (p / 3 <= c) f = 1;
                        }
                    if (f) continue;
                    flag = 0;
                    break;
                }
                if( flag ) res = min(res, a + b + c);
            }

    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

E. Replace the Numbers

记答案数组为\(x_i\)，同时维护数组\(a_i\)，当\(a_i>0\)时表示\(x_i=a_i\)，反之表示\(x_i=a_{-a_i}\)

这样的话只要能时刻的保持数组的性质，就可以实现\(O(1)\)的两种修改。

但是注意可能会出现\(a_{-a_i}<0\)的情况，此时\(x_i=a_{-a_{a_i}}\)。所以在维护的过程中，要做一个类似并查集路径压缩的优化。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5 + 5;
int b[N];
vector<int> a;

int getfa( int x ){
    if( a[x] > 0 ) return a[x] ;
    else return a[x] = getfa( -a[x] );
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int q;
    cin >> q;

    a.push_back(0);

    for (int op, x, y; q; q--) {
        cin >> op >> x;
        if (op == 1) {
            if (b[x] == 0) b[x] = a.size(), a.push_back(x);
            else a.push_back(-b[x]);
        } else {
            cin >> y;
            if( x == y ) continue;
            if (b[x] == 0) continue;
            if (b[y] == 0) b[y] = b[x], a[b[y]] = y, b[x] = 0;
            else a[b[x]] = -b[y], b[x] = 0;
        }
    }

    for( int i = 1 ; i < a.size() ; i ++ ){
        cout << getfa(i) << " ";
    }
    cout << "\n";
    return 0;
}