京东秋招 2023.08.26 机试题目与题解

发表于 2023-08-27 更新于 2023-10-14 分类于笔试阅读次数：本文字数： 2.7k 阅读时长 ≈ 2 分钟

1、讨厌鬼的数组构造

给定一个长度为\(n\)的序列\(a\)，请你构造一个序列\(b\)，序列\(b\)满足以下条件：

序列\(b\)的长度为\(n\)
对于任意\(i\in [1,n]\)，满足\((a_i+b_i) \bmod i=0\)
对于任意\(i\in [1,n]\)，满足\(1\le b_i\le 10^9\)
对于任意\(1\le i\le j\le n\)，满足\(b_i\neq b_j\)

输入

第一行输入一个整数\(n(1\le n\le 10^5)\)

第二行输入\(n\)个整数，第\(i\)个为\(a_i(1\le a_i\le 10^6)\)

输出

输出\(n\)个整数，表示答案。若有多个不同的答案，输出任意一个即可。

样例

解答

一种暴力的做法是，从小到大枚举每个\(i\)，然后尝试往\(b_i\)中填数。从小到大枚举所有满足\(x\equiv -a_i\pmod{i}\)中的正整数，如果\(x\)未曾出现过，那么将\(x\)填入\(b_i\)中即可。

代码

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

const int N=100004;
unordered_set<int>st;
int a[N],b[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int x=(-a[i]%i+i)%i;
        if(x==0) x=i;
        while(st.count(x)) x+=i;
        b[i]=x;
        printf("%d%c",b[i], " \n"[i==n]);
        st.insert(x);
    }
}

2、小红的兽

小红正在玩一个《兽》的游戏。

在这个游戏中，有\(n\)个单位，每个单位的身份是“人”或者“兽”。每个人只知道自己的身份，不知道别人的身份。每个人的战斗力为\(a_i\)。

当两个单位相遇的时候，首先第一环节是确认身份（每个人可能会告诉对方自己身份，也可能隐藏）。

如果一个兽得知了对方是人，那么兽会直接攻击人，两方发生战斗；

如果一个人得知了对方是兽，那么他会权衡双方的战斗力：只有自己的战斗力大于对方时他才会发起攻击。如果两个单位的阵营相同，则无事发生。

当两个单位攻击时，如果他们的战斗力相等，则最终同归于尽。如果某一方战斗力高，则战斗力高的将把对方杀死。

现在小红进行了\(m\)轮遭遇（每次选两个单位遭遇），请你输出最终的存活情况。

请注意，如果选择遭遇的两方存在某一方已经死亡，显然也不会发生战斗。

输入

第一行输入两个正整数\(n,m\)，代表单位数量、回合数。

接下来的\(n\)行，每行输入一个字符串\(s_i\)、一个正整数\(a_i\)，分别代表第\(i\)个单位的身份、战斗力。

接下来的\(m\)行，每行输入两个正整数\(u,v\)以及两个字符\(c_1,c_2\)，代表第\(u\)个单位和第\(v\)个单位遭遇。\(c_1\)是'Y'字符代表\(u\)向\(v\)公布自己的身份，'N'代表隐藏身份；\(c_2\)是'Y'字符代表\(v\)向\(u\)公布自己的身份，'N'代表隐藏身份。

\(1\le n\le 10^5\)
\(1\le a_i\le 10^9\)
\(1\le u,v\le n\)
\(s_i\)为"human"和"monster"中的一个，"human"代表人，"monster"代表兽。

输出

输出一个长度为\(n\)的字符串，仅由'Y'和'N'组成，'Y'代表第\(i\)个单位存活，'N'代表死亡。

样例

输入：
4 3
human 2
monster 3
monster 10
monster 1
1 2 N Y
1 4 Y N
2 3 Y Y

输出：
YYYN

提示：
第一轮，第一个单位（人）和第二个（兽）遭遇，兽公布了自己的身份，由于人的战斗力低于兽，他不会选择战斗。
第二轮，第一个单位（人）和第四个（兽）遭遇，人公布了自己的身份，兽直接选择战斗，但人获胜。
第三轮，两个单位都公布了身份，由于身份相同，因此不会战斗。
最终只有第四个单位死亡。

解答

本题需要仔细地模拟整个过程。并且最主要的是，将一些对称情况进行合并，从而减少代码量。

首先，如果两方属于同一阵营，那么无论是否公布身份，都不会发生战斗。并且跳过双方已经阵亡的战斗。

其次，接下来两方不属于同一个阵营，不失一般性，假设\(u\)为人，\(v\)为兽（否则可以将输入的两方信息进行交换）。如果\(v\)公布了身份，那么\(u\)需要根据自身的攻击力判断是否触发战斗。如果\(u\)公布了身份，那么直接触发战斗。

接下来只需要按照题意计算出这场战斗的结果即可。

代码

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

const int N=100004;
const int H=1,M=2;
int n,q,my[N],a[N];
char s[14],t[14];
int now[N];
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        now[i]=1;
        scanf("%s %d",s,&a[i]);
        my[i]=(s[0]=='h'?H:M);
    }
    int x,y;
    for(int qq=1;qq<=q;qq++){
        scanf("%d %d %s %s",&x,&y,s,t);
        if(now[x]==0||now[y]==0||my[x]==my[y]) continue;
        if(my[x]==M){
            swap(x,y);swap(s[0],t[0]);
        }
        int done=(s[0]=='Y'||t[0]=='Y'&&a[x]>a[y]);
        if(done){
            if(a[x]>a[y]) now[y]=0;
            else if(a[x]<a[y]) now[x]=0;
            else now[x]=now[y]=0;
        }
    }
    for(int i=1;i<=n;i++)
        putchar(now[i]?'Y':'N');
}

3、小红笔试

小红正在参加笔试，已知笔试一共有\(n\)个编程题，每个编程题有若干个测试用例，小红获得的分数和通过的测试用例数量成正比。

对于一个题而言，小红可以写一个暴力算法获得部分分，这样相对的比较节省时间，另外她还可以直接尝试正解，这样可以获得满分，但需要花费更多的时间。

现在给定了总时间，以及每个题目暴力算法的用时和得分、正确算法的用时和得分。

请你帮小红规划一个做题方案，可以在有限的时间内获得更多分数。

输入

第一行输入两个正整数\(n,t\)，代表题目数量，以及笔试的总时长。

接下来\(n\)行，每行输入四个正整数\(t_{i1},s_{i1},t_{i2},s_{i2}\)，分别代表小红写出正解的用时，正确算法的得分，小红写暴力算法的用时，暴力算法的得分。

\(1 \le n,t \le 2000\)
\(1 \le t_{i2} \le t_{i1} \le 2000\)
\(1 \le s_{i2} \le s_{i1} \le 10^5\)

输出

输出一个长度为\(n\)的字符串，第\(i\)个字符代表第道题的策略：

如果这道题写暴力算法，则用字符'B'表示，如果写正确算法，则用字符'A'表示，如果放弃此题（不耗时间，但这道题\(0\)分），则用'F'表示。

请务必保证总耗时不超过\(t\)，且总得分尽可能大。如果有多种做题方案都能拿到最高分数，输出任意一种即可。

样例

输入：
3 10
4 10 2 5
4 20 2 5
6 20 1 15

输出：
AAB

提示：
前两题写正解，第三题写暴力算法，这样总耗时为9，总得分为10+20+15=45。可以证明，这样安排是最优的。

解答

本题是一道比较明显的动态规划题目。令\(f(i,j)(0\le i\le n,0\le j\le t)\)表示完成花费\(j\)时间完成前\(i\)个题目的最多得分是多少。那么可以写出如下状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &0 & & \text{if}\quad i=0\land j=0 \\ &-\infty & & \text{if}\quad i=0\land j>0 \\ &f(i-1,j) & & \text{if}\quad i=0\land j<t_{i2} \\ &\max\{f(i-1,j),f(i-1,j-t_{i2})+s_{i2}\} & & \text{if}\quad i=0\land t_{i2}\le j<t_{i1} \\ &\max\{f(i-1,j),f(i-1,j-t_{i1})+s_{i1},f(i-1,j-t_{i2})+s_{i2}\} & & \text{if}\quad i=0\land j\ge t_{i1} \\ \end{aligned}\right.\)

对于状态\(f(i,j)\)下的一道题，我们有三种不同的决策：不做，暴力，正解。如果不做，那么得分为\(0\)，从\(f(i-1,j)\)转移而来；如果暴力，那么得分为\(s_{i2}\)，从\(f(i-1,j-t_{i2})\)转移而来。

在转移的过程中，我们还需要一个数组pre来记录每个状态的最优决策是什么，最终在输出解答方案时，按照这个数组返回求出一个解答方案即可。

代码

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

const int N=2004;
int f[N][N],pre[N][N];
int sa[N],sb[N],ta[N],tb[N];
char s[N];
int main(){
    int n,t;
    scanf("%d %d",&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d %d",&ta[i],&sa[i],&tb[i],&sb[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=t;j++){
            f[i][j]=f[i-1][j];
            pre[i][j]=0;
            if(j>=ta[i]){
                int w=f[i-1][j-ta[i]]+sa[i];
                if(w>f[i][j]){
                    f[i][j]=w;
                    pre[i][j]=1;
                }
            }
            if(j>=tb[i]){
                int w=f[i-1][j-tb[i]]+sb[i];
                if(w>f[i][j]){
                    f[i][j]=w;
                    pre[i][j]=2;
                }
            }
        }
    }
    int p=max_element(f[n],f[n]+t+1)-f[n];
    for(int i=n;i>=1;i--){
        if(pre[i][p]==0) s[i]='F';
        else if(pre[i][p]==1){
            s[i]='A';
            p-=ta[i];
        }
        else{
            s[i]='B';
            p-=tb[i];
        }
    }
    puts(s+1);

}