8.8网易笔试题+AC代码
C++ 开发岗位笔试
做到现在的各公司笔试题，第一次做出来3道题，纪念一下！以后可能就没机会了。。。
- 第一题： 给个英文字母字符串，长度10^3以内，在后面加随便英文字母，找出最短回文字符串
- 第二题：给一堆（最多15）有价值的东西，均分给2个人，均分不了的，扔掉，求最小扔掉多少
- 第三题：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;
} 
