8.8网易笔试题+AC代码

1. 第一题： 给个英文字母字符串，长度10^3以内，在后面加随便英文字母，找出最短回文字符串
2. 第二题：给一堆（最多15）有价值的东西，均分给2个人，均分不了的，扔掉，求最小扔掉多少
3. 第三题：n（不超过2000）个人排队买票，第i个人要么单独买票，要么和后面一个人一起买（反过来，就是可以和前面一个人买），单独买花费时间a[i]，一起买是b[i]，求最短时间，售票员可以回家。开始时间是早上08:00:00 am，输出结束时间。（12点都算am，这点弄错了，只能过65%，神奇的小试一下，ac了）

#include <bits/stdc++.h>
using namespace std;
inline bool check(string &s, int start, int end)
{
    int i = start, j = end;
    while (i < j && s[i] == s[j])
    {
        ++i, --j;
    }
    return i >= j;
}
int main(int argc, char const *argv[])
{
    string s;
    cin >> s;
    int length = s.size();
    int i;
    for (i = 0; i < length; ++i)
    {
        if (check(s, i, length - 1))
        {
            break;
        }
    }
    string prefix = s.substr(0, i);
    reverse(prefix.begin(), prefix.end());
    cout << s + prefix << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int a[20];
int suffixSum[20];
int n;
int minLoss;
void dfs(int first, int second, int cost, int index)
{
    if (index >= n)
    {
        if (first == second)
            minLoss = min(minLoss, cost);
        return;
    }
    if (first == second)
        minLoss = min(minLoss, suffixSum[index] + cost);
    if (abs(first - second) > suffixSum[index])
        return;
    // 给first，给second，扔掉
    dfs(first + a[index], second, cost, index + 1);
    dfs(first, second + a[index], cost, index + 1);
    dfs(first, second, cost + a[index], index + 1);
}
int main(int argc, char const *argv[])
{
    int t;
    cin >> t;
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        memset(suffixSum, 0, sizeof(suffixSum));
        for (int i = n - 1; i >= 0; --i)
            suffixSum[i] = suffixSum[i + 1] + a[i];
        minLoss = INT32_MAX;
        dfs(0, 0, 0, 0);
        cout << minLoss << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int a[2020];
int b[2020];
int dp[2020][3];
int main(int argc, char const *argv[])
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n - 1; ++i)
            scanf("%d", &b[i]);
        b[0] = a[1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        dp[0][1] = a[0];
        dp[0][2] = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (j >= 1)
            {
                // j 单独买
                dp[j][0] = min(dp[j - 1][2], dp[j - 1][0]) + a[j];
                // j 和 j+1 一起买
                dp[j][1] = min(dp[j - 1][0], dp[j - 1][2]) + b[j];
            }
            else
            {
                // j 单独买
                dp[j][0] = a[j];
                // j 和 j+1 一起买
                dp[j][1] = b[j];
            }
            // j 和 j-1 一起买
            if (j >= 2)
                dp[j][2] = min(dp[j - 2][0], dp[j - 2][2]) + b[j - 1];
            else
                dp[j][2] = b[j - 1];
        }
        int seconds = min(dp[n][0], dp[n][2]);
        int hour = seconds / 3600 + 8;
        int minutes = seconds % 3600 / 60;
        seconds = seconds % 3600 % 60;
        printf("%02d:%02d:%02d", hour, minutes, seconds);
        // 12点是 am，少了等号，只能过65%的测试用例
        if (hour <= 12)
            printf(" am\n");
        else
            printf(" pm\n");
    }
    return 0;
}