爱奇艺2018校招题解与思路
空中旅行
分析
模拟一下。
参考代码
#include <bits/stdc++.h>
using namespace std;
int n, s;
int f[55];
int main() {
cin >> n >> s;
for(int i = 0; i < n; i++) cin >> f[i];
int cnt = 0;
int add = f[0];
for(int i = 0; i < n; i++) {
if(add <= s) {
cnt++;
}
add = add + f[i + 1];
}
cout << cnt << endl;
return 0;
}
拼凑三角形
分析
暴力枚举,然后维护出答案就好了。
参考代码
#include <bits/stdc++.h>
using namespace std;
int a, b, c;
int main() {
cin >> a >> b >> c;
int mx = 0;
for(int i = 1; i <= a; i++) {
for(int j = 1; j <= b; j++) {
for(int k = 1; k <= c; k++) {
if(i + j > k && i + k > j && j + k > i) {
mx = max(mx, i + j + k);
}
}
}
}
cout << mx << endl;
return 0;
}
循环数比较
分析
根据题意模拟比较。当然这个题,不同语言难度不一样。。
参考代码
#include <bits/stdc++.h>
using namespace std;
int x1, x2, k1, k2;
int main() {
cin >> x1 >> k1 >> x2 >> k2;
stringstream ss1;
ss1 << x1;
string a;
ss1 >> a;
stringstream ss2;
ss2 << x2;
string b;
ss2 >> b;
string aa = "", bb = "";
for(int i = 0; i < k1; i++) aa += a;
for(int i = 0; i < k2; i++) bb += b;
if(aa.size() > bb.size() || (aa.size() == bb.size() && aa > bb)) {
cout << "Greater" << endl;
} else if(aa.size() < bb.size() || (aa.size() == bb.size() && aa < bb)) {
cout << "Less" << endl;
} else {
cout << "Equal" << endl;
}
return 0;
}
红和绿
分析
枚举分界点,然后分别统计需要的次数,记录最小值就是答案。
参考代码
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
cin >> s;
int len = s.size();
int ans = len;
for(int i = 0; i <= len; i++) {
int need = 0;
for(int j = 0; j < i; j++) {
if(s[j] != 'R') need++;
}
for(int j = i; j < len; j++) {
if(s[j] != 'G') need++;
}
ans = min(ans, need);
}
cout << ans << endl;
return 0;
}
括号匹配深度
分析
记录当前'('出现的次数cnt,出现')'就完成一次匹配,维护整个过程中cnt的最大值就是答案。
参考代码
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
cin >> s;
int ans = 0, cnt = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] == '(') {
cnt++;
ans = max(ans, cnt);
} else if(s[i] == ')') {
cnt--;
}
}
cout << ans << endl;
return 0;
}
平方根问题
分析
(sqrt(a) + sqrt(b)) (sqrt(a) + sqrt(b))
= sqrt(a) sqrt(a) + 2 sqrt(a) sqrt(b) + sqrt(b) sqrt(b)
= sqrt(a a) + 2 sqrt(a b) + sqrt(bb)
= a + 2 sqrt(a * b) + b
于是原问题就是看a*b是否能是完全平方数,详细做法见代码注释。
参考代码
#include <bits/stdc++.h>
using namespace std;
int solve(int N, int M) {
int res = 0;
for (int a = 1; a <= N; a++) {
int s = 1;
//找到最大的s,让a是s*s的倍数
// O(sqrt(N))
for (int x = 2; x <= a / x; x++) {
if (a % (x * x) == 0) {
s = x * x;
}
}
int r = a / s;
//a * r 是一个完全平方数
//如果b = r * c, 我们要让a * b是一个平方数,需要c也是一个完全平方数
// O(sqrt(M))
for (int y = 1; y * y * r <= M; y++) {
//(a, r * r * y)是一个合法的解
res++;
}
}
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
printf("%d\n", solve(n, m));
return 0;
}
奶牛编号
分析
贪心。排序一下,然后答案就是所有x[i] - i的乘积。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int x[55];
int n;
int main() {
cin >> n;
for(int i = 0; i < n; i++) cin >> x[i];
long long res = 1;
sort(x, x + n);
for(int i = 0; i < n; i++) {
res *= x[i] - i;
res %= mod;
}
cout << res << endl;
return 0;
}
奇异数
分析
分析一下这种数字的特征,我们会发现这种数字出现的规律。
我们先把上下界处理到整100的地方,剩下的就可以快速计算了。
参考代码
#include <bits/stdc++.h>
using namespace std;
long long L, R;
int main() {
cin >> L >> R;
long long ans = 0;
while(L <= R && (L % 100)) ans += ((L % 10) == ((L / 10) % 10)), L++;
while(L <= R && (R % 100)) ans += ((R % 10) == ((R / 10) % 10)), R--;
if(L > R) {
cout << ans << endl;
} else {
cout << ans + ((R - L) / 100) * 10 + 1;
}
return 0;
}
平方串
分析
枚举间断点把字符串分成两部分,然后计算两个部分的LCS,维护最大值就是最后所求答案的一半。
参考代码
#include <bits/stdc++.h>
using namespace std;
int LCS(string X, string Y) {
if (Y.length() > X.length())
swap(X, Y);
int m = X.length(), n = Y.length();
vector< vector<int> > c(2, vector<int>(n + 1, 0));
int i, j;
for(i = 1;i <= m;i++) {
for(j = 1;j <= n;j++) {
if (X[i - 1] == Y[j - 1])
c[1][j] = c[0][j - 1] + 1;
else
c[1][j] = max(c[1][j - 1], c[0][j]);
}
for(j = 1;j <= n;j++)
c[0][j] = c[1][j];
}
return (c[1][n]);
}
string s;
int main() {
cin >> s;
string st = s;
int ans = 0;
for(int cp = 1; cp < st.size(); cp++) {
string st1, st2;
for(int i = 0; i < st.size(); i++) {
if(i < cp) st1 += st[i];
else st2 += st[i];
}
ans = max(ans, LCS(st1, st2));
}
cout << ans * 2 << endl;
return 0;
}
