爱奇艺2018春季校招笔试编程题参考代码
牛牛与玩偶
分析
根据题意，只会有两种重量的玩偶，对于每一种重量，维护该重量的玩偶总数和最后一个该重量玩偶的序号，最后找到数量为1的那种玩偶对应的序号就可以了。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
int w[1000005];
int main() {
int n;
int w1, w2, num1 = 0, num2 = 0, ans1, ans2;
scanf("%d", &n);
scanf("%d", &w[1]);
w1 = w[1];
num1 = 1;
ans1 = 1;
for(int i = 2; i <= n; i++) {
scanf("%d", &w[i]);
if(w[i] == w1) {
num1++;
ans1 = i;
} else {
w2 = w[i];
num2++;
ans2 = i;
}
}
if(num1 == 1)
printf("%d\n", ans1);
else
printf("%d\n", ans2);
return 0;
}
彩色队伍
分析
挨着扫一遍, 统计当前字符跟前一个字符不同的个数。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
cin >> s;
int cnt = 0;
for(int i = 1; i < s.size(); i++) {
if(s[i - 1] == s[i]) {
cnt++;
i++;
}
}
cout << cnt << endl;
return 0;
}
牛牛学洗牌
分析
按照题目所说的，每一次把前Xi张牌和剩下的牌分开，再一张一张从两叠牌轮流放回去即可。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[15];
int temp[2][15];
int len[2];
int main() {
int n;
bool f;
for(int i = 1; i <= 13; i++) scanf("%d", &a[i]);
scanf("%d", &n);
while(n--) {
scanf("%d", &len[0]);
len[1] = 13 - len[0];
for(int i = 1; i <= len[0]; i++) temp[0][i] = a[i];
for(int i = 1; i <= len[1]; i++) temp[1][i] = a[i + len[0]];
f = 0;
for(int i = 13; i >= 1; i--) {
if(len[f] == 0) f=!f;
a[i] = temp[f][len[f]];
len[f]--;
f = !f;
}
}
for(int i = 1; i <= 13; i++) {
printf("%d", a[i]);
if(i == 13)
printf("\n");
else
printf(" ");
}
return 0;
}
三个整数
分析
设X为最后三个数都变为的数。
所以总共需要的操作次数为(3X - (A + B + C)) / 2。注意到X肯定大于等于A, B, C三个数的最大值, 我们现在要最小化X, 并且两个操作都不改变A + B + C的奇偶性。
设A, B, C的最大值为Ma = max(A, max(B, C))
所以3 Ma与 A + B + C相同奇偶性的话, X = Ma, 否则X = Ma + 1。
然后输出(3Ma - (A + B + C)) / 2即可。
时间复杂度
O(1)
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[3];
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
if ((a[2] - a[1] + a[2] - a[0]) % 2 == 0)
cout << (a[2] - a[1] + a[2] - a[0]) / 2;
else
cout << (a[2] - a[1] + a[2] - a[0] + 3) / 2;
return 0;
}
字典序最大子序列
分析
贪心。每次取当前剩余字典序最大的字符。
时间复杂度
O(n)
参考代码
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
cin >> s;
ostringstream ss;
while(!s.empty()) {
string::iterator it = max_element(s.begin(), s.end());
ss << *it;
s.erase(s.begin(), it + 1);
}
cout << ss.str() << endl;
return 0;
}
牛牛配点心
分析
合法的点心盒一共有三种：一甜一苦一酸/两甜一苦(酸)/三甜。
为了最大化点心盒的数量，我们肯定是优先组成第一种点心盒，再考虑第二种点心盒，最后剩下的甜点心每三个组成一个点心盒。
于是问题转化为，最多能同时组成多少对一苦一酸的点心，并且每对点心都不冲突。
我们可以借助二分图匹配的模型，考虑在任意一对个不冲突且一苦一酸的点心之间连一条边，然后求最大匹配。
最后根据最大匹配的数量、多余的苦(酸)点心的数量、和甜点心的数量算出答案。
时间复杂度
O(n^3)
参考代码
#include <bits/stdc++.h>
using namespace std;
char s[505][5];
bool ok[505][505];
int root[505];
vector <int> vec[505];
bool life[505];
bool solve(int x) {
life[x] = 1;
for(int i = 0; i < vec[x].size(); i++) {
if(life[vec[x][i]])
continue;
else
life[vec[x][i]] = 1;
if(!root[vec[x][i]] || solve(root[vec[x][i]])) {
root[vec[x][i]] = x;
return 1;
}
}
return 0;
}
int main() {
int n, m, u, v;
int numdl = 0, numdc = 0, numds = 0, ans = 0;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%s", s[i]);
for(int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
ok[u][v] = 1;
ok[v][u] = 1;
}
for(int i = 1; i <= n; i++) {
if(s[i][0] == 'K') {
numdc++;
for(int j = 1; j <= n; j++) {
if(s[j][0] == 'S' && !ok[i][j])
vec[i].push_back(j);
}
} else {
if(s[i][0] == 'T') numdl++;
else numds++;
}
}
for(int i = 1; i <= n; i++) {
memset(life, 0, sizeof(life));
if(s[i][1] == 'C' && solve(i)) ans++;
}
if(ans >= numdl)
printf("%d\n", numdl);
else
{
if((numdl - ans) / 2 >= (numdc + numds - ans * 2))
printf("%d\n", numdc + numds - ans + (numdl - ans - (numdc + numds - ans * 2) * 2) / 3);
else
printf("%d\n", ans + (numdl - ans) / 2);
}
return 0;
}
牛牛配糖果
分析
可以通过母函数求解或者直接用背包dp就好了。
参考代码
#include <bits/stdc++.h>
using namespace std;
long long f[2][105];
int main() {
int n, m;
scanf("%d%d", &n, &m);
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
memset(f[i & 1], 0, sizeof(f[i & 1]));
int l, r;
scanf("%d%d", &l, &r);
for (int k = l; k <= r; k++)
for (int j = m; j >= k; j--)
f[i & 1][j] += f[i + 1 & 1][j - k];
}
printf("%lld\n", f[n & 1][m]);
return 0;
}#校招#
