BT笔试

学习大佬

第一题

头条1.png

最暴力的方法，挨个遍历，对结果用set存储，避免重复，但是无法通过所有测试用例

排序后使用双指针法，也就是滑动窗口

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = INT_MAX;
int a[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i) scanf("%d",&a[i]);
    sort(a, a+n);
    n = unique(a, a+n) -a;
    int r = 0, ans=0;
    for(int l=0; l<n;++l)
    {
        while(r<n&&a[r]-a[l]<k) ++r;
        if(r==n) break;
        if(a[r]-a[l] == k) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}

第二题

头条2.png
头条2-2.png

利用动态规划来做简单一些
dp[i][j]表示s的长度为i，m的长度为j时所需要的最少步数，状态转移示意图如下

状态转移示意图.jpg

#include <bits/stdc++.h>

using namespace std;

#define MAX_SIZE 10000

int dp[MAX_SIZE][MAX_SIZE >> 1];

int main()
{
    for (int i = 2; i < MAX_SIZE; i++) {
        for (int j = 1; j < MAX_SIZE / 2; j++)
            dp[i][j] = 0x3f3f3f;
        for (int j = 1; j <= i / 2; j++)
            dp[i][j] = min(dp[i][j], dp[i - j][j] + 1);
        if (i % 2)        // 注意偶数情况才能继续
            continue;
        for (int j = 1; j <= i / 4; j++)
            dp[i][i / 2] = min(dp[i][i / 2], dp[i / 2][j] + 1);
    }
    vector<int> ans(MAX_SIZE);
    for (int i = 1; i < MAX_SIZE; i++)        //在dp[i][j]中预处理出s的长度为i时所需要的最小步数，即：
        ans[i] = *min_element(dp[i] + 1, dp[i] + MAX_SIZE / 2);

    for (int n; cin >> n; cout << ans[n] << endl) {}
    return 0;
}

第四题

头条4.png

分析：

1. 从平均值大的集合中取小于该集合平均值且大于令一个集合中的平均值的这些元素放到另一个集合中
2. 取数只能取出现次数等于1的数，放数只能放没出现过的数
3. 什么样取的顺序能使magic进行的次数尽可能多，肯定是从小的开始取，使均值小的集合均值上升慢，均值大的集合均值上升快

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()
{
    for (int n, m; cin >> n >> m; ) {
        set<LL> A, B;
        double aveA = 0, aveB = 0;
        for (int i = 0, x; i < n; A.insert((cin >> x, x)), aveA += x, ++i) {}
        for (int i = 0, x; i < m; B.insert((cin >> x, x)), aveB += x, ++i) {}

        // aveA / n > aveB / m;
        if (aveA / n < aveB / m) {
            A.swap(B);
            swap(aveA, aveB);
            swap(n, m);
        }

        int ans = 0;
        for (auto it = A.begin(); it != A.end() && *it * 1.0 < aveA / n; ++it) {
            if (B.find(*it) != B.end())
                continue;
            if (*it > aveB / m) {
                aveA -= *it, aveB += *it;
                --n, ++m;
                ++ans;
            }
        }

        cout << ans << endl;
    }
    return 0;
}

第五题

头条-5.png

BFS，当前状态只能借助与跳板高度绝对值小于等于k的跳板

#include <bits/stdc++.h>

using namespace std;

int main()
{
    for (int n, k, h; cin >> n >> k >> h; ) {
        vector<int> height;
        for (int i = 0, x; i < n; height.push_back((cin >> x, x)), ++i) {}

        int TOP = *max_element(height.begin(), height.end()) + h + 1;
        vector<bool> used(TOP, false);
        queue<pair<int, int> > que;
        used[0] = true;
        que.emplace(0, 0);
        int ans = 0;
        for (; !que.empty(); ) {
            auto now = que.front();
            que.pop();

            ans = max(now.first, ans);

            for (auto it = height.begin(); it != height.end(); ++it) {
                if (abs(now.first - *it) <= h &&
                        (2 * *it - now.first > 0 || 2 * *it - now.first < TOP) &&
                        !used[2 * *it - now.first] && now.second < k) {
                    used[2 * *it - now.first] = true;
                    que.emplace(2 * *it - now.first, now.second + 1);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}