京东笔试C++ 题解

第一题：求1~N的最小公倍数。把每个数字分解质因数，算他们每个质因数的贡献，然后乘起来。我的代码没写好（算质因数不用这么慢的）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 100009
int fact[maxn];
bool prime[maxn];
ll mod = 987654321;
int cal(int t, int p) {
    int cnt = 0;
    while(t % p == 0) {
        cnt++;
        t /= p;
    }
    return cnt;
}
void first() {
    memset(prime, true, sizeof(prime));
    prime[1] = false;
    for(int i = 2; i <= 100000; i++) {
        int top = sqrt(i);
        for(int j = 2; j <= top; j++) {
            if(i % j == 0) {
                prime[i] = false;
                break;
            }
        }
    }
}
void solve(int Limit) {
    first();
    for (int i = 2; i <= Limit; i++) {
        int top = sqrt(i);
        for (int j = 2; j <= top; j++) {
            if(prime[j] && i % j == 0) {
                fact[j] = max(fact[j], cal(i, j));
            }
        }
        if(prime[i])
            fact[i] = max(fact[i], 1);
    }
}
int main() {
    ll n;
    cin>>n;
    solve(n);
    ll ans = 1;
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= fact[i]; j++) {
            ans = ans * i % mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

第二题：去掉字符串构成回文。其实是经典的求回文子序列个数。但是我觉得题意是有坑的，题意描述的感觉不是这个意思。记忆化搜索dp。也可以直接dp。方程：
f[i][j] = dfs(i, j - 1) + dfs(i + 1, j) - dfs(i + 1, j - 1);
if(str[i] == str[j])
f[i][j] += dfs(i + 1, j - 1) + 1;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[59][59];
string str;
ll dfs(int i, int j) {
    if(i > j) {
        return 0;
    }
    if(i == j) {
        f[i][j] = 1;
        return f[i][j];
    }
    if(f[i][j] != 0) {
        return f[i][j];
    }
    f[i][j] = dfs(i, j - 1) + dfs(i + 1, j) - dfs(i + 1, j - 1);
    if(str[i] == str[j])
        f[i][j] += dfs(i + 1, j - 1) + 1;
    return f[i][j];
}
int main() {
    cin>>str;
    int len = str.length();
    cout<<dfs(0, len - 1)<<endl;
    return 0;
}

第三题：象棋的马走K步之后到(X,Y)的方案数。直接递推。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[10][10][3];
ll mod = 1e9 + 7;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int check(int x, int y) {
    if(x >= 0 && x <= 8 && y >= 0 && y <= 8)
        return true;
    return false;
}
void cal(int x, int y, int state) {
    dp[x][y][state] = 0;
    for(int i = 0; i < 8; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(check(tx, ty)) {
            dp[x][y][state] = (dp[x][y][state] + dp[tx][ty][state ^ 1]) % mod;
        }
    }
}
int main() {
    int K;
    cin>> K;
    int state = 0, nowstate;
    dp[0][0][0] = 1;
    while(K--) {
        state = state ^ 1;
        for(int i = 0; i <= 8; i++) {
            for(int j = 0; j <= 8; j++) {
                cal(i, j, state);
            }
        }
    }
    int x, y;
    cin>>x>>y;
    cout<<dp[x][y][state]<<endl;
    return 0;
}