[数据结构与算法]AtCoder Beginner Contest 213 题解(A-E)

AtCoder Beginner Contest 213 题解(A-E)

A. Bitwise Exclusive Or

题目大意：

给出两个整数$A$和$B$，找出一个非负整数$C$使得$A\oplus C=B$。

解题思路：

因为异或是自反的，所以$C=A\oplus B$。

代码：

#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
    cin>>a>>b;
    cout<<(a^b)<<endl;
    return 0;
}

B. Booby Prize

题目大意：

给出$n$个不同的整数，问第二大的整数的第几个整数。

解题思路：

每个整数带上序号排序即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct Node{
    int id,sc;
}a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].sc;
        a[i].id=i;
    }
    sort(a+1,a+1+n,[&](Node a,Node b){
            return a.sc>b.sc;
         });
    cout<<a[2].id<<endl;
    return 0;
}

C. Reorder Cards

题目大意：

有一个$H\times W$的矩阵，有$N$个位置上分别写有数字，第$i$个数字写在第$A_i$行第$B_i$列。

会将所有不存在数字的行和列全部删去，问最后这$N$个数字的下标是多少。

• $1\le H,W\le 10^9$
• $1\le N\le \min (10^5,H\times W)$

解题思路：

因为所有不存在数字的行和列都会被删去，所以留下来的一定是存在数字的行和列。

那么对行和列分别进行离散化，就能知道行和列在所有行列中的相对位置。

时间复杂度$O(NlogN)$

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct Node{
    int x,y;
}a[N];
int h,w,n;
int px[N],py[N];
vector<int> vx,vy;
int get(int x,vector<int> &v){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int main()
{
    scanf("%d%d%d",&h,&w,&n);
    for(int i=1;i<=n;i++){
         scanf("%d%d",&a[i].x,&a[i].y);
         vx.push_back(a[i].x);
         vy.push_back(a[i].y);
    }
    sort(vx.begin(),vx.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    sort(vy.begin(),vy.end());
    vy.erase(unique(vy.begin(),vy.end()),vy.end());
    for(int i=1;i<=n;i++) printf("%d %d\n",get(a[i].x,vx),get(a[i].y,vy));
    return 0;
}

D. Takahashi Tour

题目大意：

有$N$座城市，所有城市之间有$N?1$条无向边。

现在从城市$1$开始旅行：

• 对于每个城市都会去按照从小到大的顺序去未访问过的相邻城市旅游
• 如果当前城市已经没有未访问的相邻城市：
  • 如果当前城市是城市1就结束旅行
  • 否则往回走。

输出旅行访问的城市顺序。

解题思路：

因为是一棵树，所以按照题意从点$1$进行dfs就行了。

对于每个点按照从小到大的顺序进行深搜，因为每次都一定会回来，所以除了在要到达每个节点的时候输出一次当前节点，还要在dfs子节点结束之后输出当前节点。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> e[N];
int n;
void dfs(int u,int pre){
    printf("%d ",u);
    bool flag=false;
    for(int i=0;i<e[u].size();i++){
        int j=e[u][i];
        if(j==pre) continue;
        dfs(j,u);
        printf("%d ",u);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        e[b].push_back(a);
        e[a].push_back(b);
    }
    for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end());
    dfs(1,-1);
    return 0;
}

E. Stronger Takahashi

题目大意：

给出一个$N\times M$的平面，一部分格子是可以通过的，另一部分格子上面会有石头阻碍通过。

现在要从左上角走到右下角，因为主角身强体壮，可以一拳击碎$2\times 2$的区域内的所有石头，问最少需要打拳几次才能走到右下角。

解题思路：

如果我们在BFS的过程中，遇到了走不通的情况，在把某个石头作为要击穿的对象，那么这个以这个石头为中心的$3\times 3$区域内的所有格子我们都能花费$1$次的代价走到。

所以整张图就变成了边权只有$0$和$1$的情况，可以考虑用双端队列来进行BFS。

边权为0的就加入到队头，边权为1的就加入到队尾。

时间复杂度$O(N?M)$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=510;
int g[N][N];
int n,m;
int nxt[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int dist[N][N];
bool vis[N][N];
int bfs()
{
    memset(dist,0x3f,sizeof dist);
    deque<PII> que;
    que.push_front({1,1});
    dist[1][1]=0;
    while(!que.empty()){
        PII t=que.front();
        que.pop_front();
        int x=t.first,y=t.second;
        if(vis[x][y]) continue;
        vis[x][y]=true;
        for(int i=0;i<4;i++){
            int tx=x+nxt[i][0];
            int ty=y+nxt[i][1];
            if(tx<=0||tx>n||ty<=0||ty>m||dist[tx][ty]<=dist[x][y]) continue;
            if(!g[tx][ty]){
                dist[tx][ty]=dist[x][y];
                que.push_front({tx,ty});
            }
            else{
                for(int j=-1;j<=1;j++){
                    for(int k=-1;k<=1;k++){
                        int dx=tx+j;
                        int dy=ty+k;
                        if(dx<=0||dx>n||dy<=0||dy>m||dist[dx][dy]<=dist[x][y]+1) continue;
                        dist[dx][dy]=dist[x][y]+1;
                        que.push_back({dx,dy});
                    }
                }
            }
        }
    }
    return dist[n][m];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        char s[N];
        scanf("%s",s+1);
        for(int j=1;j<=m;j++) g[i][j]=(s[j]=='.'?0:1);
    }
    printf("%d\n",bfs());
    return 0;
}