京东笔试 20230826

计算机基础单选+三种语言任选一种的语言特性题单选+3道编程。

单选都不太难，有个考数据库的，问给定条件下页表目录多大的题 没答上来。

编程：第一题，输入一个数组 $a_i$ 满足长度小于1e5，值小于1e6。输出数组 $b_i$ 使得对于任意的i，$(a_i + b_i) % i = 0$，且 $b_i$ 各不相同。

感觉就是瞎搞。如果有重复值了就加上几个i直到没碰撞为止。AC

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
const int INF = 1e9;

long long a[N];
int cnt = 0;
set<int> st;
set<int> ss;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        a[i] = i - val + val / i * i;
    }

    for (int i = n; i >= 1; --i)
    {
        while(st.count(a[i]))
            a[i] += 1LL * i * (++cnt);
        if(a[i] > INF)
            a[i] -= INF / i * i;
        while(st.count(a[i]))
            a[i] += 1LL * i * (++cnt);
        st.insert(a[i]);
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << a[i] << ' ';
        if(a[i] >= 1e9 || ss.count(a[i]))
            while(true);
        ss.insert(a[i]);
    }
    cout << endl;
    return 0;
}

第二题，兽棋。有n颗棋子，碰面了m次，问最后哪些活着。棋子身份为人或兽，各有战斗值$a_i$。每次战斗前可以选择说出自己的身份或不说。兽知道了对方是人，则一定战斗。人知道对方是兽且自己战力更高时，才会发起战斗。身份相同则无事发生。每次战斗战力低的死亡，相等则同时死亡。如果有一方已经死了则不会发起战斗。

模拟。没少写特判条件，但是就过了95%。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;

int n, m;
int type[N], val[N], die[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s >> val[i];
        type[i] = s[0] == 'h';
    }
    for (int i = 1; i <= m; ++i) {
        int x, y;
        string a, b;
        cin >> x >> y >> a >> b;
        if (die[x] || die[y] || (a[0] == 'N' && b[0] == 'N') || type[x] == type[y])
            continue;
        if (a[0] == 'Y' && b[0] == 'Y') {
            if (val[x] > val[y])
                die[y] = 1;
            else if (val[x] < val[y])
                die[x] = 1;
            else
                die[x] = die[y] = 1;
        } else if (a[0] == 'Y') {
            if (type[y]) {
                if (val[y] > val[x])
                    die[x] = 1;
            } else {
                if (val[x] > val[y])
                    die[y] = 1;
                else if (val[x] < val[y])
                    die[x] = 1;
                else
                    die[x] = die[y] = 1;
            }
        } else {
            if (type[x]) {
                if (val[x] > val[y])
                    die[y] = 1;
            } else {
                if (val[x] > val[y])
                    die[y] = 1;
                else if (val[x] < val[y])
                    die[x] = 1;
                else
                    die[x] = die[y] = 1;
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << (die[i] ? 'N' : 'Y');
    cout << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

第三题，n道题，m秒。每题可以选择花 at_i 秒得 ap_i 分或 bt_i 秒得 bp_i分或不做，问最后最多能得多少分。

01背包，存做了前 i 题，花 j 秒能获得的最高分，同时存当前状态下每题是得了ap还是bp还是放弃了。AC

#include <bits/stdc++.h>
using namespace std;
const int N = 2020;

int n, m;
int pt[N], pp[N], at[N], ap[N];
vector< vector<int> > res(2, vector<int>(N));
int fi[N];
bitset<N> bt1[2][N], bt2[2][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> at[i] >> ap[i] >> pt[i] >> pp[i];
    }
    for (int i = 1; i <= n; ++i) {
        string ss = to_string(i);
        for (int j = 0; j <= m - at[i]; ++j) {
            if (res[1][j + at[i]] < res[0][j] + ap[i]) {
                res[1][j + at[i]] = res[0][j] + ap[i];
                bt1[1][j + at[i]] = bt1[0][j];
                bt2[1][j + at[i]] = bt2[0][j];
                bt1[1][j + at[i]][i].flip();
            }
        }
        for (int j = 0; j <= m - pt[i]; ++j) {
            if (res[1][j + pt[i]] < res[0][j] + pp[i]) {
                res[1][j + pt[i]] = res[0][j] + pp[i];
                bt1[1][j + pt[i]] = bt1[0][j];
                bt2[1][j + pt[i]] = bt2[0][j];
                bt2[1][j + pt[i]][i].flip();
            }
        }
        for (int i = 1; i <= m; ++i)
            bt1[0][i] = bt1[1][i], bt2[0][i] = bt2[1][i], res[0][i] = res[1][i];
    }
    for(int i=1;i<=n;++i)
        cout << (bt1[1][m][i] ? 'A' : (bt2[1][m][i] ? 'B' : 'F'));

    cout << endl;
    return 0;
}