京东秋招 2023.09.16 编程题目与题解

发表于 2023-09-17 分类于笔试阅读次数：本文字数： 2.4k 阅读时长 ≈ 2 分钟

1、小红比身高

小红和朋友们比身高，一共有\(n\)个朋友，每个朋友的身高是\(h_i\)，小红的身高为\(H\)，一共有\(m\)阶楼梯，第\(i\)阶楼梯的高度是\(s_i\)，第\(i\)个朋友会站在第\(p_i\)阶楼梯上，小红想知道，如果小红可以目由选择站在第几阶楼梯上，她最多可以比多少朋友高。

输入

一行三个整数\(n,m,H\)，表示朋友的个数，楼梯的个数，小红的身高。

一行\(n\)个整数\(h_i\)，表示每个朋友的身高。

一行\(n\)个整数\(p_i\)，表示每个朋友站在第几阶楼梯上。

一行\(m\)个整数\(s_i\)，表示每个楼梯的高度。

\(1\le n,m \le 10^5\)
\(1\le H,h_i, s_i \le 10^6\)
\(1\le p_i\le m\)

输出

输出一个整数，表示小红可以比多少朋友高。

样例

输入：
3 4 4
3 5 7
1 2 2
1 2 3 3

输出：
1

提示：
小红站在最高的楼梯上，高度为4+3=7。
第一个朋友高度为3+1=4，第二个朋友高度为 5+2=7，第三个朋友高度为7+2=9。
小红只能比第一个朋友高。

解答

为了比尽量多的朋友高，那么小红应该站在最高的阶梯上，即其高度为\(\displaystyle{V=H+\max_{i=1}^m\{s_i\}}\)，而第\(i\)个朋友的高度为\(v_i=h_i+a_{p_i}\)。因此只需要统计有多少个\(i\)满足\(V>v_i\)即可。

代码

# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=100004;
int h[N],p[N],a[N],v[N],n,m,H;
int main(){
    scanf("%d %d %d",&n,&m,&H);
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        v[i]=h[i]+p[a[i]];
    int V=*max_element(a+1,a+m+1)+H;
    int ans=0;
    for(int i=1;i<=n;i++)
        if(V>v[i]) ++ans;
    printf("%d\n",ans);
}

2、小红的树上游戏

小红有一棵\(n\)个结点的树，编号为\(1\)到\(n\)。小红和朋友想要在树上玩一个游戏，游戏规则如下：

每次删除一个叶子结点，然后将与其相连的边删除
删除了编号为\(x\)的结点的人获胜。

小红想知道，如果她先手，她是否能获胜。

输入

第一行输入一个整数\(t\)，表示数据组数。

每组数据第一行两个整数\(n\)和\(x\)，表示树的结点数和小红想要删除的结点编号。

接下来\(n-1\)行，每行两个整数\(u,v\)，表示树上存在一条连接\(u\)和\(v\)的边。

\(1\le t\le 30\)
\(1\le n \le 10^4\)
\(1\le u,v,x\le n\)

输出

输出\(t\)行，每行一个字符串，如果小红能获胜，输出win，否则输出lose。

样例

输入：
2
5 3
1 2
1 3
2 4
2 5
5 2
1 2
1 3
2 4
2 5

输出：
win
lose

提示：
第一组，3是叶子结点，可以直接删除。

解答

当节点\(x\)是叶节点时，先手必胜，因为游戏开始时就可以拿起它。

否则，\(x\)是内部节点。对于两个同样聪明的人而言，他们肯定不希望自己当前的行动导致下一轮行动就会将\(x\)节点暴露到叶节点中，从而让对方取到并获胜。实在没有办法了，那么其中一方才会使\(x\)节点暴露到叶节点中，从而让另一方获胜。\(x\)什么时候会被暴露呢？拖到如下这种情况下，无论进行哪一步操作，\(x\)节点就会被迫暴露出来了：

graph TD
  X((x));Y((y));Z((z));
  X---Y;X---Z;

因此，下一个拿到\(x\)的是赢家，此时\(x\)是第\(n-1\)个回合所取得的节点。也就是说，我们只需要判断\(n-1\)是否为奇数即可。

代码

# include <bits/stdc++.h>

using namespace std;

const int N=10004;
int d[N];
int solve(){
    int n,x,u,v;
    memset(d,0,sizeof(d));
    scanf("%d %d",&n,&x);
    for(int i=1;i<n;i++){
        scanf("%d %d",&u,&v);
        ++d[u];++d[v];
    }
    if(n==1||d[x]==1) return 1;
    return (n-1)&1;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        puts(solve()?"win":"lose");
    }
}

3、小红的二进制位加减

给定一个正整\(x\)，小红每次操作可以选择\(x\)的一个二进制位中的'1'，并加上这个二进制位或者减去这个二进制位对应的十进制的值。小红希望在有限的操作次数内变成了\(y\)。你能帮帮她吗？

输入

两个正整数\(x,y\)，用空格隔开\(1 \le x,y \le 10^{18}\)。

输出

如果无解，请直接输出\(-1\)。

否则第一行输入一个整数\(t\)，代表操作次数心。

接下来的\(t\)行，每行输入一个字符\(op\)（\(+\)或者\(-\)）、空格、一个正整数\(i\)，代表每次操作。

请务必保证操作次数不超过\(1000\)，且操作选择的数必须是当前的\(x\)中存在的二进制的'1'(输出时请输出那个'1'对应的十进制的值）

有多解时输出任意即可。

样例

输入：
3 8

输出：
2
+ 1
+ 4

提示：
输出以下也是可以的：
- 1
+ 2
+ 4

输入：
4 5

输出：
-1

提示：
4的二进制为"100"，显然无法再加上1得到5。

解答

我们可以从二进制的角度来看待这两种操作：

对于第一种操作，相当于是将所选中的\(1\)比特和高位连续的所有\(1\)比特置成\(0\)比特，并将原本最高位的那个\(1\)比特后一位的\(0\)比特置成\(1\)比特。
对于第二种操作，相当于是将\(x\)的某个\(1\)比特置成\(0\)比特。

也就是说，无论怎么进行两种操作，这个数的\(1\)比特数量只会下降，不会上升。

因此如果\(x\)的\(1\)比特数量小于\(y\)的\(1\)比特数，那么\(x\)肯定不能转化成\(y\)。

为了方便，我们需要对第一种操作施加一个约束条件：选定的\(1\)比特只有其相邻高位的那一位是\(0\)，第一种操作才能使用。在这种情况下执行第一种操作，就相当于将这个\(1\)比特向高位移动了一位。

因此，令\(X\)是一个集合，\(b\in X\)当且仅当第\(x\)的第\(b\)位是\(1\)比特，我们可以用类似的方式定义集合\(Y\)。因此，第一种操作就相当于在保持\(X\)集合所有元素仍然是单一的情况下，对其个元素进行\(+1\)，而第二种操作则相当于是从\(X\)中删去某个元素。然后询问集合\(X\)是否能变成集合\(Y\)。

如果\(|X|<|Y|\)，那么不能完成。如果\(|X|>|Y|\)，那么由于第二种操作都会使\(X\)的元素趋于变大，因此我们执行\(|X|-|Y|\)次操作去掉\(X\)中的最大元素以得到\(X'\)，来保证\(|X'|=|Y|\)。假设\(X_i\)为集合\(X\)的第\(i\)大元素，将\(i\)从\(1\)遍历到\(n\)，如果在一开始，\(X_i>Y_i\)，那么原来的转化同样也不可行，否则可以使用\(Y_i-X_i\)次操作将\(X_i\)转化成\(Y_i\)。

由于\(10^{18}<2^{60}\)，因此这种方法在极限情况下（\(x=2^{60}-1,y=2^{60}-2^{30}\)）只会有\(30\times (30+1)=930\)次操作，符合题意。

代码

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

int flag=0;
vector<int>solve(vector<int>&a,vector<int>&b){
    vector<int>sol;
    if(a.size()<b.size()){
        return {};
    }
    while(a.size()>b.size()){
        int x=a.back();a.pop_back();
        sol.push_back(-x);
    }
    int m=a.size();
    for(int i=m-1;i>=0;i--){
        if(a[i]>b[i]) return {};
        for(int j=a[i];j<b[i];j++){
            sol.push_back(j);
        }
    }
    flag=1;
    return sol;
}
int main(){
    ll x,y;
    scanf("%lld %lld",&x,&y);
    vector<int>a,b;
    for(int i=0;i<62;i++){
        if(x>>i&1) a.push_back(i);
        if(y>>i&1) b.push_back(i);
    }
    vector<int>c=solve(a,b);
    if(flag){
        printf("%d\n",c.size());
        for(int x:c){
            int f=1;
            if(x<0) x=-x,f=-1;
            printf("%c %d\n",f==1?'+':'-',1ll<<x);
        }
    }
    else puts("-1");

}