阿里淘天秋招 2023.09.09 编程题目与题解

发表于 2023-09-10 分类于笔试阅读次数：本文字数： 1.5k 阅读时长 ≈ 1 分钟

1、小红的棋盘

小红有一个大小为\(8\times 8\)的国际象棋棋盘，棋盘的\((x_1,y_1)\)位置上是骑士，可以向八个方向移动，棋盘的\((x_2,y_2)\)位置上是主教，可以向四个方向移动，但是不能越过其他棋子。小红想知道，有多少个地方可以放一个新棋子，不会被骑士和主教吃掉。新棋子只能放置在空的格子上。

骑士位置在\((x_1,y_1)\)，那么会吃掉\((x_1+dx,y_1+dy)\)的棋子，\(|dx|+|dy|=3,dx\neq 0,dy\neq 0\)。

主教位置在\((x_2,y_2)\)，那么会吃掉\((x_2+dx,y_2+dy)\)的棋子，\(|dx|=|dy|>0\)。

输入

一行四个整数\(x_1,y_1,x_2,y_2\)，表示骑士和主教的位置。

\(1\le x_1,y_1,x_2,y_2 \le 8\)
\((x_1,y_1)\neq (x_2,y_2)\)

输出

输出一个整数，表示可以放置新棋子的位置数。

样例

输入：
1 2 4 5

输出：
45

解答

直接进行对两颗棋子的攻击范围进行遍历即可，需要注意的是，模拟的过程中主教的攻击范围遇到骑士时，应当停止。

代码

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

const int N=8;
int dx[N+4]={-1,1,-1,1,-2,2,-2,2};
int dy[N+4]={2,2,-2,-2,1,1,-1,-1};

int da[4]={-1,1,0,0};
int db[4]={0,0,-1,1};

int g[N+4][N+4];
int f[N+4][N+4];
int main(){
    int xa,ya,xb,yb;
    scanf("%d %d %d %d",&xa,&ya,&xb,&yb);
    f[xa][ya]=f[xb][yb]=g[xa][ya]=g[xb][yb]=2;
    for(int i=0;i<N;i++){
        int x=xa+dx[i],y=ya+dy[i];
        if(1<=x&&x<=N&&1<=y&&y<=N){
            g[x][y]=1;
        }
    }

    for(int i=0;i<4;i++){
        for(int k=1;k<=N;k++){
            int x=xb+da[i]*k,y=yb+db[i]*k;
            if(x<1||y<1||x>N||y>N||f[x][y]) break;
            g[x][y]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            ans+=!g[i][j];
    printf("%d\n",ans);
}

2、小红的城堡

一天小红来到了一个古老的王国，这个王国由\(n\)个城堡组成，这其中有一个城堡是国王的皇宫，编号为\(1\)，城堡之间用\(n-1\)条道路相连，形成一张连通的图。

然而，不幸的是，有\(m\)个城堡的供水系统出现了问题，导致这些城堡的居民没有水源供应。

小红决定自愿修复这些城堡的供水系统，以保障居民的生活质量。每次修复，小红可以选择一个城堡，然后修复这个城堡到皇宫的所有城堡的供水系统（包括选择的城堡和皇宫）。

小红想知道，为了保证整个王国的供水正常，她最少需要修复多少个城堡的供水系统。

输入

一行两个整数\(n,m\)，表示城堡的数量和出现问题的城堡的数量。

接下来\(n-1\)行，每行两个整数\(u,v\)，表示城堡\(u\)和城堡\(v\)之间有一条道路相连。

接下来一行，\(m\)个整数\(a_1,a_2,\dots,a_m\)，表示出现问题的城堡的编号。

\(1\le m\le n\le 10^5\)
\(1\le u,v\le n\)
\(1\le a_i\le n\)

输出

输出一个整数，表示最少需要修复的城堡的数量。

样例

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

输出：
2

提示：
修复3，4号城堡的供水系统即可。

解答

代码

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

const int N=100004;
vector<int>g[N];
int a[N],n,m;
int vis[N];
int ans=0;
int dfs(int u,int fa){
    int f=0;
    for(int v:g[u]){
        if(v==fa) continue;
        f|=dfs(v,u);
    }
    if(f==0&&vis[u]) ++ans;
    return f|vis[u];
}
int main(){
    int x,y;
    scanf("%d %d",&n,&m);
    for(int i=2;i<=n;i++){
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&x);
        vis[x]=1;
    }
    dfs(1,0);
    printf("%d\n",ans);
}

3、小红的移动点

小红有\(n\)个点，每个点的坐标为\((x_i,y_i)\)，小红可以从一个点出发，平行于坐标轴移动，直到到达另一个点。比如从\((1,1)\)出发，可以到达\((1,3),(5,1)\)，但无法直接到达\((4,4)\)，如果需要到达\((4,4)\)，需要增加一个点\((4,1)\)或者\((1,4)\)。小红想知道，最少需要增加几个点，才能使得任意两个点之间可以互相到达。

输入

第一行一个整数\(n\)，表示点的个数。

接下来\(n\)行，每行两个整数\(x_i,y_i\)，表示第\(i\)个点的坐标。

\(1\le n\le 10^5\)
\(-10^9\le x_i,y_i\le 10^9\)

输出

输出一个整数，表示最少需要增加的点的个数。

样例

输入：
2
1 1 
2 2

输出：
1

提示：
至少需要增加一个点(1,2)或者(2,1)。

解答

我们可以这样进行考虑：将坐标系中的每一条水平线和每一条垂直线视为图中的每一个节点。如果存在一个坐标点\((x_i,y_i)\)，那么说明从\(x=x_i\)中的点和\(y=y_i\)中的点相互可达。因此，我们可以为节点\(x=x_i\)和\(y=y_i\)之间连一条边。

最终如果这个图的所有边分散在\(k\)个连通块，那么说明只需要添加\(k-1\)个条边（也就是\(k-1\)个坐标点），就能够将这些连通块都进行连通。

由于这里是维护连通块，因此只需要使用并查集即可完成。

代码

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

const int N=100004;
unordered_map<ll,ll>mp;
ll find(ll x){
    return mp[x]==x?x:mp[x]=find(mp[x]);
}
void merge(ll x,ll y){
    mp[find(x)]=find(y);
}
ll x[N],y[N],offset=1e11;
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&x[i],&y[i]);
        y[i]+=offset;
        mp[x[i]]=x[i];
        mp[y[i]]=y[i];
    }
    for(int i=1;i<=n;i++)
        merge(x[i],y[i]);
    int ans=0;
    for(auto &[k,v]:mp)
        if(k==v) ++ans;
    --ans;
    printf("%d\n",ans);
}