携程4.28笔试题解

A 游游的数组相邻去重

简单模拟题。

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

const int N = 3 + 1e5;

int n, a[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        int j = i;
        while (j + 1 <= n && a[i] == a[j + 1])
            ++j;
        cout << a[i];
        if (j > i) {
            cout << "(" << j - i + 1 << ")";
        }
        cout << " ";
        i  = j;
    }
    return 0;
}

B 游游的水果大礼包

看数据范围可以O(n)，直接枚举第一个礼包的数量算最多还能搞几个二号礼包就行了。

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

LL n, m, a, b;

int main() {
    cin >> n >> m >> a >> b;
    LL ans = 0;
    for (int i = 0; i * 2 <= n && i <= m; ++i) {
        int j = min(n - 2 * i, (m - i) / 2);
        ans = max(ans, i * a + j * b);
    }
    cout << ans << endl;
    return 0;
}

C 游游的字母串

枚举最终变成什么字母，然后单个字母的操作次数是可以O(1)算出来的。

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

string s;

int solve(int c) {
    int ans = 0;
    for (auto& i : s) {
        ans += min((c - (i - 'a') + 26) % 26, (i - 'a' - c + 26) % 26);
    }
    return ans;
}

int main() {
    int ans = 1e9;
    cin >> s;
    for (int i = 0; i < 26; ++i) {
        ans = min(ans, solve(i));
    }
    cout << ans << endl;
    return 0;
}

D 游游的不相邻取数

看数据范围就知道可以O(n^2)，设dp[i][j]代表前i个数，取的数中5的因子数量不超过j的情况下，2的因子的最大值，这样就可以完成转移了。

这个题有个类似的题：https://www.nowcoder.com/practice/a2be806a0e5747a088670f5dc62cfa1e

但做法还是有区别的，这道题得开二维，不能硬搬2333

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

const int N = 1003;

int n, a[N], b[N], c[N];
int dp[N][N * 5];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        while (a[i] % 5 == 0) {
            ++b[i];
            a[i] /= 5;
        }
        while (a[i] % 2 == 0) {
            ++c[i];
            a[i] /= 2;
        }
    }
    int ans = 0;
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;
    dp[1][0] = 0;
    dp[1][b[1]] = c[1];
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j <= 5000; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= b[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 2][j - b[i]] + c[i]);
            }
            ans = max(ans, min(j, dp[i][j]));
        }
    }
    cout << ans << endl;
    return 0;
}