A:贝壳找房

题解：打表，预处理1e5的表，然后根据表进行查询。
题目说了有序，不知道会不会有降序，总之写了也过了

#include <iostream>
#include <algorithm>
#include <array>
#include <limits>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;
using ll = long long;
using db = double;
map<ll, ll> house;

int main() {
    ios::sync_with_stdio(false);
    house[1] = 1;
    ll prev = 1;
    for (int i = 2; i <= 1e5 + 3; ++i) {
        ll cur = prev + i + 1;
        house[cur] = i;
        prev = cur;
    }
    int n;
    cin >> n;
    while (n--) {
        int num;
        cin >> num;
        prev = -1;
        bool dir = false;
        bool ok = true;
        ll dis = 0;
        if (num == 1) {
            int cur;
            cin >> cur;
            ll pos = house[cur];
            if (!pos) {
                cout << "no" << endl;
            } else {
                cout << "yes" << endl;
            }
        } else {
            while (num--) {
                int cur;
                cin >> cur;
                if (prev == -1) {
                    ll pos = house[cur];
                    if (!pos) {
                        ok = false;
                        prev = 0;
                        continue;
                    } else {
                        ok = true;
                    }
                    prev = pos;
                    continue;
                } else {
                    if (!ok)continue;
                    auto pos = house[cur];
                    if(!pos)
                    {
                        ok = false;
                        continue;
                    }
                    if(!dir)
                    {
                        dir = true;
                        dis = prev - pos;
                        if(abs(dis)>1)
                        {
                            ok = false;
                            continue;
                        }
                        prev = pos;
                        continue;
                    }
                    if(prev - pos == dis)
                    {
                        prev = pos;
                        continue;
                    }
                    else {
                        ok = false;
                    }
                }

      }
        if (ok) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
}
}

B 贝壳找房移山（简单）

题解:回溯。由于题目范围很小可以容忍复杂度相当高的算法。因此随便搞一个回溯就能过

#include <iostream>
#include <algorithm>
#include <array>
#include <limits>
#include <cmath>
#include <map>
#include <iomanip>
#include <queue>
#include <functional>

using namespace std;
using ll = long long;
using db = double;

struct Mountain {
    int start, end, height;

    Mountain() {}

    Mountain(int s, int e, int h) : start(s), end(e), height(h) {}

    bool operator<(const Mountain v) const {
        if (height != v.height)
            return height > v.height;
        else
            return end - start < v.end - v.start;
    }
};
array<int, 10> road{};
int n, k;
int cnt = 0x3f3f3f3f;

void dfs(int _cnt)
{
    vector<Mountain> q;
    int status = 0;
    int spos = 0;
    for (int i = 1; i <= n + 1; ++i) {
        if (status == 1) {
            if (road[i] < road[i - 1]) {
                status = 0;
                q.push_back(Mountain(spos, i - 1, min(road[spos] - road[spos - 1], road[i - 1] - road[i])));
            } else if (road[i] > road[i - 1]) {
                spos = i;
            }
        } else {
            if (road[i] > road[i - 1]) {
                status = 1;
                spos = i;
            }
        }
    }
    if (q.size() > k) {
        for(auto el:q)
        {
            auto top = el;
            int s = top.start;
            int e = top.end;
            for (int i = s; i <= e; ++i) {
                --road[i];
            }
            dfs(_cnt+1);
            for (int i = s; i <= e; ++i) {
                ++road[i];
            }
        }

    } else {
        cnt = min(_cnt,cnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) {
            cin >> road[i];
        }
        road[n + 1] = road[0] = 0;
        cnt = 0x3f3f3f3f;
        dfs(0);
        cout << cnt << endl;
    }
}

C 贝壳找房移山（中等）

题解:枚举所有的山峰山谷，一起消去就行

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
ll n, k, t;
ll a;
vector<ll> high;

int main() {
    cin >> t;
    for (ll q = 1; q <= t; q++) {
        cin >> n >> k;
        ll last = 0, ans = 0;
        high.clear();
        bool which = true;
        high.push_back(0);
        for (ll i = 1; i <= n; i++) {
            cin >> a;
            if (which) {
                if (a < last) {
                    high.push_back(last);
                    which = false;
                }
            } else {
                if (a > last) {
                    high.push_back(last);
                    which = true;
                }
            }
            last = a;
        }
        if (which) {
            high.push_back(last);
            high.push_back(0);
        } else
            high.push_back(0);
        auto numofsf = static_cast<ll>(high.size() / 2);
        for (ll i = 1; i <= numofsf - k; i++) {
            ll willdel = 1;
            for (ll j = 1; j <= high.size() / 2; j++) {
                if (high[j * 2 - 1] - (max(high[j * 2 - 2], high[j * 2])) <
                    high[willdel] - max(high[willdel - 1], high[willdel + 1]))
                    willdel = j * 2 - 1;
            }
            if (high[willdel + 1] > high[willdel - 1]) {
                ans += high[willdel] - high[willdel + 1];
                high.erase(high.begin() + willdel);
                high.erase(high.begin() + willdel);
            } else {
                ans += high[willdel] - high[willdel - 1];
                high.erase(high.begin() + willdel - 1);
                high.erase(high.begin() + willdel - 1);
            }
        }
        cout << ans << endl;
    }
}