爱奇艺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;
}