快手算法笔试-A卷(只通过2.2, 太难了吧....)

请会做3、4题的大佬多指教~

1. 将n分成K个正整数，使得这K个正整数之和是n，并且乘积最大，求最大乘积。

dp[i][j]表示i分成j个正整数的最大乘积，时间复杂度：。

#include 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define PI pair
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int N = 1010;
ll dp[N][15];
int main() {    
    int K, n;
    cin >> K >> n;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= K; ++k) {
            for (int j = 1; j <= i; ++j) {
                dp[i][k] = max(dp[i][k], dp[i-j][k-1] * j);
            }
        }
    }
    cout << dp[n][K] << endl;
    return 0;
}

2. 二维矩阵从左上角到右下角，求最短路径和。只能向下或者向右。

扫一遍即可。dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + A[i][j]。

3. 定义一种生成随机序列的方式：给定S, A, B, P, 初始arr[0] = S, 接下来arr[i+1] = (arr[i] * A + B) % P, 并且arr数组里的每个数字最多出现两次，当某个数字出现3次时，终止序列生成。给定两组S, A, B, P分别生成两个序列，求两个序列的最长公共子序列.。

不会。

UPD：在@六月雪Yuni 大佬的提醒下，第三题大概会了啊。。。。就是把LCS问题转化成LIS问题。。

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define PI pair<int,int>

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int N = 1000010;

int T, S[2], A[2], B[2], P[2];
vector<int> data[2];

vector<int> gen(int s, int a, int b, int p) {
    vector<int> ret({s});
    unordered_map<int, int> cnt;
    cnt[s] = 1;
    while (1) {
        int x = (1LL * ret[ret.size()-1] * a % p + b) % p;
        if (cnt.find(x) == cnt.end()) cnt[x] = 0;
        cnt[x] += 1;
        if (cnt[x] >= 3) {
            break;
        }
        ret.emplace_back(x);
    }
    return ret;
}


int LIS(vector<int> A) {
    int n = A.size();
    if (n <= 1) return 1;
    int data[n], m = 1;
    data[0] = A[0];

    for (int i = 1; i < n; ++i) {
        int pos = lower_bound(data, data + m, A[i]) - data;
        data[pos] = A[i];
        if (pos == m) m++;
    }
    return m;
}

int main() {    
    cin >> T;
    while (T--) {
        for (int i = 0; i < 2; ++i) cin >> S[i] >> A[i] >> B[i] >> P[i];
        for (int i = 0; i < 2; ++i) data[i] = gen(S[i], A[i], B[i], P[i]);

        for (auto x: data[0]) cout << x << " ";
        cout << endl;
        for (auto x: data[1]) cout << x << " ";
        cout << endl;

        // 记录第一个序列中每个数字的位置
        unordered_map<int, pair<int, int> > pos;
        for (int i = 0; i < data[0].size(); ++i) {
            int x = data[0][i];
            if (pos.find(x) == pos.end()) {
                pos[x] = mp(i, -1);
            } else {
                pos[x] = mp(pos[x].fi, i);
            }
        }

        // 得到转换后的第二个序列
        vector<int> filter;
        for (int i = 0; i < data[1].size(); ++i) {
            int x = data[1][i];
            if (pos.find(x) == pos.end()) continue;
            if (pos[x].fi != -1) {
                filter.emplace_back(pos[x].fi);
                pos[x].fi = -1;
            } else {
                filter.emplace_back(pos[x].se);
            }
        }
        cout << LIS(filter) << endl;
    }
    return 0;
}

4. 给定一个椭球：(x-a)^2/d^2 + (y-b)^2/e^2 + (z-c)^2/f^2 = 1，求中心在原点的单位球的表面，在椭球内部和在椭球外部的表面积分别是多少。

球表面积公式是。采样去近似，只拿了20%的分。。。

#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1.0);

double a, b, c, d, e, f;

bool check(double x, double y, double z) {
    double s = (x-a) * (x-a) / d + (y-b)*(y-b)/e + (z-c)*(z-c)/f;
    return s <= 1;
}

int main() {    
    cin >> a >> b >> c >> d >> e >> f;
    d *= d, e*=e, f*=f;
    double step1 = 0.0005, step2 = 0.0005;
    double total = 0, inner = 0;
    for (double i = -1; i <= 1; i += step1) {
        double left = sqrt(1 - i * i);
        for (double j = -left; j <= left; j += step2) {
            double z = sqrt(1 - i*i - j*j);
            if (z != 0) total += 2, inner += check(i, j, z) + check(i, j, -z);
            else total += 1, inner += check(i, j, z);
        }
    }
    double A1 = inner / total * 4 * pi, A2 = 4 * pi - A1;
    cout << A1 << " " << A2 << endl;
    return 0;
}