2019 BUAA Spring Training 16 题解

Solved	A	B	C	D	E	F	G	H	I	J	K	L	M
13/13	O	O	O	O	O	O	Ø	O	O	Ø	O	O	O

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

比赛链接

A Gym 102021A - Attack on Alpha-Zet

题目描述

给一个迷宫，迷宫中所有点互相连通且有且仅有一条道路。给$m$个点，求从$1$号点依次经过这些点到$m$号点的总距离。

解题思路

可以看成一棵树，不停求$LCA$即可。

AC代码

点击

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1100010
struct Edge{
    int e,n;
}e[N<<1];
int hd[N],cnt;
void add(int a,int b){
    e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
}
int fa[25][N],d[N],lg[N];
void dfs(int now,int f){
    d[now]=d[f]+1;
    fa[0][now]=f;
    int i;
    for(i=1;(1<<i)<=d[now];i++)
        fa[i][now]=fa[i-1][fa[i-1][now]];
    for(i=hd[now];i;i=e[i].n){
        int p=e[i].e;
        if(p!=f)dfs(p,now);
    }
}
int lca(int x,int y){
    int i;
    if(d[x]<d[y]){int t=x;x=y;y=t;}
    while(d[x]>d[y])
        x=fa[lg[d[x]-d[y]]][x];
    if(x==y)return x;
    for(i=lg[d[x]];~i;i--)
        if(fa[i][x]!=fa[i][y])
            x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
string g[2200];
int n,m,k;
ll res;
int dir[]={1,0,-1,0};
int id(int x,int y){return(x-1)*m+y;}
void Add(int x,int y){
    int i;
    for(i=0;i<4;++i){
        int nx=x+dir[i],ny=y+dir[3-i];
        if(nx>0&&nx<=n&&ny>0&&ny<=m){
            if(nx==x-1&&g[nx][ny*2-1]=='_') continue;
            if(nx==x+1&&g[x][ny*2-1]=='_') continue;
            if(ny==y-1&&g[nx][ny*2]=='|') continue;
            if(ny==y+1&&g[nx][ny*2-2]=='|') continue;
            add(id(x,y),id(nx,ny));
        }
    }
}
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    getchar();
    for(i=0;i<=n;++i)getline(cin,g[i]);
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)Add(i,j);
    for(i=2;i<N;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
    dfs(id(1,1),0);
    scanf("%d",&k);
    int x,y;
    scanf("%d%d",&x,&y);
    for(i=1;i<k;++i){
        int a,b,i1=id(x,y),i2;
        scanf("%d%d",&a,&b);
        i2=id(a,b);
        res+=d[i1]+d[i2]-2*d[lca(i1,i2)];
        x=a;y=b;
    }
    printf("%lld",res);
    return 0;
}

B Gym 102021B - Battle Royale

题目描述

给两个点，两个点通过的一个圆，求两点间不进入这个圆的最短路径。

解题思路

两切线长加弧长即可。

AC代码

点击

#include<bits/stdc++.h>
using namespace std;
double x1,x2,y,y2,x3,y3,r;
double dis(double a,double b,double c,double d){
    return sqrt((c-a)*(c-a)+(d-b)*(d-b));
}
int main(){
    scanf("%lf%lf",&x1,&y);
    scanf("%lf%lf",&x2,&y2);
    scanf("%lf%lf%lf",&x3,&y3,&r);
    scanf("%lf%lf%lf",&x3,&y3,&r);
    double d1=dis(x1,y,x3,y3);
    double d2=dis(x2,y2,x3,y3);
    double d3=dis(x1,y,x2,y2);
    double c1=sqrt(d1*d1-r*r);
    double c2=sqrt(d2*d2-r*r);
    double j1=acos(r/d1);
    double j2=acos(r/d2);
    double j3=acos((-d3*d3+d1*d1+d2*d2)/(2*d1*d2))-j2-j1;
    printf("%.10f",c1+c2+r*j3);
}

C Gym 102021C - Coolest Ski Route

题目描述

给一个有向无环图，边权为正，求任意能够到达的两点距离的最大值。

解题思路

按拓扑序递推即可。

AC代码

点击

#include<bits/stdc++.h>
using namespace std;
#define N 10010
int n,m,k,vis[N];
int dis[N];
struct Edge{
    int e,n,l;
}e[N<<1];
int hd[N],ind[N],cnt;
void add(int a,int b,int l){
    e[++cnt].e=b;e[cnt].n=hd[a];e[cnt].l=l;hd[a]=cnt++;
}
queue<int>Q;
int main(){
    int i,f,g,w;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&f,&g,&w);
        add(f,g,w);
        ind[g]++;
    }
    for(i=1;i<=n;i++)if(!ind[i])Q.push(i);
    while(!Q.empty()){
        int top=Q.front();Q.pop();
        for(i=hd[top];i;i=e[i].n){
            int q=e[i].e;
            if(dis[q]<dis[top]+e[i].l)dis[q]=dis[top]+e[i].l;
            if(!--ind[e[i].e])Q.push(e[i].e);
        }
    }
    int ans=0;
    for(i=1;i<=n;i++)ans=max(ans,dis[i]);
    printf("%d",ans);
    return 0;
}

D Gym 102021D - Down the Pyramid

题目描述

给定一个数组$B$，求数组$A$，使得$A_i+A_{i+1}=B_i$。问有多少种方法。

解题思路

从前往后找上下界限制，求出上下界最窄的有多少种情况即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 1000010
int n,a[N],up[N],low[N];
int main(){
    int i,ans=1e9;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);a[n]=1e9;
    up[0]=a[0];
    for(i=1;i<=n;i++){
        up[i]=min(a[i-1]-low[i-1],a[i]);
        low[i]=max(0,a[i-1]-up[i-1]);
        ans=min(ans,up[i]-low[i]+1);
    }
    printf("%d",ans<0?0:ans);
    return 0;
}

E Gym 102021E - Expired License

题目描述

求一个小数能否转化成两个质数的比，并输出。

解题思路

特判$1$！特判$1$！特判$1$！

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int p[1000000],A[10000002],tot;
int main(){
    int i,j,n;
    A[0]=A[1]=1;
    for(i=2;i<10000000;i++){
        if(!A[i])p[++tot]=i;
        for(j=1;p[j]*i<10000000&&j<=tot;j++){
            A[p[j]*i]=1;
            if(i%p[j]==0)break;
        }
    }
    scanf("%d",&n);
    for(i=0;i<n;i++){
        double a,b;
        int x,y;
        scanf("%lf%lf",&a,&b);
        a*=100000;b*=100000;
        a+=1e-9,b+=1e-9;
        x=(int)a,y=(int)b;
        if(x==y){
            printf("2 2\n");
            continue;
        }
        int g=__gcd(x,y);
        x/=g,y/=g;
        if(!A[x]&&!A[y])printf("%d %d\n",x,y);
        else printf("impossible\n");
    }
    return 0;
}

F Gym 102021F - Fighting Monsters

题目描述

问一个自然数数组里存在不存在两个数能够互相减，减到$(0,1)$。

解题思路

找斐波那契数列中的相邻两项。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int f[50]={1,1};
struct P{
    int d,i;
    bool operator<(const P&a)const{return d<a.d;}
}a[1000010];
int m[1000010];
int main(){
    int i,n;
    for(i=2;;i++){
        f[i]=f[i-1]+f[i-2];
        if(f[i]>1000000)break;
        m[f[i]]=i;
    }m[1]=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i].d);
        a[i].i=i;
    }
    int flag=0;
    sort(a+1,a+1+n);
    if(a[1].d==1&&a[2].d==1)return printf("%d %d\n",a[1].i,a[2].i),0;
    for(i=1;i<=n;i++){
        if(m[a[i].d]){
            if(!flag||m[a[flag].d]!=m[a[i].d]-1)flag=i;
            else return printf("%d %d\n",a[flag].i,a[i].i),0;
        }
        while(a[i].d==a[i+1].d)i++;
    }
    printf("impossible");
    return 0;
}

G Gym 102021G - GPS

题目描述
给定地球上某一点，给定某个严格圆轨道卫星的轨道描述（两个旋转角度、半径）和轨道上一点经过的角度，求能否到达地球上那一点，如果可以求出时间。

解题思路
根据$x,\phi,\psi$求出卫星上该点坐标，地球上一点用球坐标求出，判断角（地球球心—地球上的点—卫星上该点）是否为锐角，求出距离即可。

注意$\sin$不要打成$\cos$！

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
double x,y,z,r=6371,pi=acos(-1),lo,la;
double X,Y,Z,R,dis;
int main(){
    int n;
    scanf("%d",&n);
    scanf("%lf%lf",&lo,&la);lo*=pi/180,la*=pi/180;
    double theta=lo,phi=pi/2-la;
    x=r*sin(phi)*cos(theta),y=r*sin(phi)*sin(theta),z=r*cos(phi);
    while(n--){
        double a,b,f;
        scanf("%lf%lf%lf%lf",&a,&b,&R,&f);a*=pi/180,b*=pi/180;
        theta=f*2*pi;
        double tx=cos(theta),ty=sin(theta)*cos(b);
        X=tx*cos(a)-ty*sin(a),Y=tx*sin(a)+ty*cos(a);Z=sin(theta)*sin(b);
        X*=R,Y*=R,Z*=R;
        dis=sqrt((x-X)*(x-X)+(y-Y)*(y-Y)+(z-Z)*(z-Z));
        if(dis*dis+r*r<=R*R)printf("%.10f\n",dis/299792.458);
        else printf("no signal\n");
    }
    return 0;
}

H Gym 102021H - Hyper Illuminati

题目描述

求一个$<1e16$的正整数能否被分解成$\sum_{i=0}^{n}x^i$，若能，求出$x,n$。

解题思路

暴力即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    ll i,j,k,n;
    scanf("%lld",&n);
    for(i=3;i<=55;i++){
        ll ans=0;
        for(j=1;j<=n;j++){
            ll temp=1;
            for(k=1;k<i;k++){//j^i
                if((double)temp*j-n>0){temp=n+1;break;}
                temp*=j;
            }
            if((ans+=temp)>n)break;
            if(n==ans)return printf("%lld %lld",i,j),0;
        }
    }
    printf("impossible");
    return 0;
}

I Gym 102021I - It’s Time for a Montage

题目描述

给定$a,b$两个数组，$a$数组可以在$t$时间后每个元素的值$+1$，问至少多少时间后$a$的字典序$\geq b$的字典序。

解题思路

题意倒是很简单，读题真是头疼。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,a[1010],b[1010];
int jud(int x){
    int i;
    for(i=0;i<n;i++){
        if(a[i]+x>b[i])return 1;
        else if(a[i]+x<b[i])return 0;
    }
    return 1;
}
int main(){
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    for(i=0;i<n;i++)scanf("%d",&b[i]);
    for(i=0;;i++)if(jud(i))return printf("%d",i),0;
    return 0;
}

J Gym 102021J - Jigsaw Puzzle

题目描述

给一些拼图，求输出按照给定的接口拼起来的方案。

解题思路

每个接口都只有两个，直接记录搜索即可。

神秘操作，忘记$vector$和数组不一样会超出限制，$RE$了好久没看出来为什么……

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 300010
struct P{int x,y;};//x,0123
vector<P>ans[N];
P p[N<<2][2];
int num[N<<2],a[N][4],w,h,n;
int find(int a1,int a2,int x){
    int i;
    for(i=0;i<4;i++)if(a[x][i]==a1&&a[x][(i+1)%4]==a2)return i;
    return -1;
}
int vis[N];
int solve(){
    vis[0]=1;
    int i,j,right,down,last;
    //find left&up
    int start=0,startnum;
    for(i=1;i<=n;i++){
        if((startnum=find(0,0,i))!=-1){
            start=i;
            break;
        }
    }
    if(!start)return 0;
    vis[start]=1;
    w=1;
    //first row
    right=a[start][(startnum+2)%4],last=start;
    ans[0].push_back({start,startnum});
    while(right){
        P x=(p[right][0].x==last?p[right][1]:p[right][0]);
        if(vis[x.x])return 0;
        vis[x.x]=1;
        if(a[x.x][(x.y+1)%4]!=0)return 0;
        right=a[x.x][(x.y+2)%4];
        last=x.x;
        w++;
        ans[0].push_back(x);
    }
    if(n%w)return 0;
    //row by row
    h=n/w;
    int nowh=1;
    while(nowh<h){
        int noww=1;
        P upper=ans[nowh-1][0];
        down=a[upper.x][(upper.y+3)%4],last=upper.x;
        if(!down)return 0;
        P x=(p[down][0].x==last?p[down][1]:p[down][0]);
        if(vis[x.x])return 0;
        vis[x.x]=1;
        ans[nowh].push_back({x.x,(x.y+3)%4});
        right=a[x.x][(x.y+1)%4],last=x.x;
        while(right){
            if(noww>=w)return 0;
            x=(p[right][0].x==last?p[right][1]:p[right][0]);
            if(vis[x.x])return 0;
            vis[x.x]=1;
            upper=ans[nowh-1][noww];
            if(a[x.x][(x.y+1)%4]!=a[upper.x][(upper.y+3)%4])return 0;
            right=a[x.x][(x.y+2)%4];
            last=x.x;
            noww++;
            ans[nowh].push_back(x);
        }
        if(noww!=w)return 0;
        nowh++;
    }
    //check last
    for(i=0;i<w;i++)if(a[ans[h-1][i].x][(ans[h-1][i].y+3)%4])return 0;
    //print
    printf("%d %d\n",w,h);
    for(i=0;i<w;i++){
        for(j=0;j<h;j++)printf("%d ",ans[j][i].x);
        puts("");
    }
    return 1;
}
int main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=0;j<4;j++){
            scanf("%d",&a[i][j]);
            int x=a[i][j];
            if(x&&num[x]>=2)return printf("impossible"),0;
            if(x)p[x][num[x]++]=(P){i,j};
        }
    }
    if(!solve())printf("impossible");
    return 0;
}

K Gym 102021K - Kitchen Cable Chaos

题目描述

有一个长为$dis$的缝隙和$n$段杆，要求在这段缝隙中加入某些杆，杆与杆之间可以重叠不超过$5$，使得重叠最小的最大，并求出这个重叠长度。

解题思路

$dp[i][j][k]$表示递推到前$i$个，用了$j$个，能否拼出长度为$k$的杆，循环判断即可。可以优化掉一维，不过没必要。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int d[62],dp[62][62][1295+5];
double ans=-1;
int main(){
    int i,j,k,n,dis,mx=0;
    scanf("%d%d",&n,&dis);
    for(i=1;i<=n;i++)scanf("%d",&d[i]),mx+=d[i];
    dp[0][0][0]=1;
    for(i=1;i<=n;i++)
        for(j=0;j<=i;j++)
            for(k=0;k<=mx&&k<=1295;k++)
                if(k>=d[i]&&j)dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-1][k-d[i]]);
                else dp[i][j][k]=dp[i-1][j][k];
    for(i=1;i<=n;i++)
        for(k=dis-10;k<=dis+5*(i-1);k++)
            if(dp[n][i][k])
                ans=max(ans,(k+10-dis)*1.0/(i+1));
    if(ans>=0)printf("%.10f",ans);
    else printf("impossible");
    return 0;
}

L Gym 102021L - Logic Puzzle

题目描述

扫雷，给定一个雷数矩阵（包含自己的九格雷数），最外圈没有雷，求最终雷的位置并判断合法性。

解题思路

从$(2,2)$开始找，每一次找它左上的雷数，如果是$1$那么有雷，$0$那么无雷，否则不合法。再判断最右一列的合法性即可。

AC代码

点击

#include<bits/stdc++.h>
using namespace std;
int num[200][200];
char res[200][200];
void setz(int i,int j){
    num[i][j]--;num[i][j+1]--;num[i][j-1]--;
    num[i+1][j+1]--;num[i+1][j]--;num[i+1][j-1]--;
    num[i-1][j+1]--;num[i-1][j]--;num[i-1][j-1]--;
}
int main(){
    int i,j,h,w;
    scanf("%d%d",&h,&w);
    for(i=0;i<=h+1;i++)for(j=0;j<=w+1;j++)scanf("%d",&num[i][j]);
    for(i=0;i<=h;i++){
        for(j=0;j<=w;j++){
            if(num[i][j]==1)res[i+1][j+1]='X',setz(i+1,j+1);
            else if(num[i][j]==0)res[i+1][j+1]='.';
            else return printf("impossible"),0;
        }
        if(num[i][w+1])return printf("impossible"),0;
    }
    for(j=0;j<=w+1;j++)if(num[h+1][j]!=0)return printf("impossible"),0;
    for(i=1;i<=h;i++){
        res[i][w+1]='\0';
        printf("%s\n",res[i]+1);
    }
    return 0;
}

M Gym 102021M - Mountaineers

题目描述

给一个矩阵，求给定两点间的路径中最大元素最小值。

解题思路

考虑$LCA$，其实这个思想和$A$题基本重合。建图的过程为：开始时，所有的点都不联通；按高度从小到大枚举每个点，每个点向它周围四个方向寻找已经访问过的（高度小于等于它的）且与不在同一连通块中的点，将它们联通，用并查集维护连通块，用树存储连边关系。注意加边和修改父亲的顺序。最后求$LCA$的深度即可。注意排完序的顺序是改变了的，搞清楚哪里维护的是初始状态，哪里维护的是排序后的状态。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,q;
#define N 260000
int id(int x,int y){return (x-1)*m+y;}
struct Point{
    int x,y,h,id;
    bool operator<(const Point &p)const{return h<p.h;}
}p[N];
#define M 510
int tot,f[N],a[M][M],vis[N],H[N];
int find(int x){
    return x==f[x]?f[x]:(f[x]=find(f[x]));
}
struct Edge{
    int e,n;
}e[N<<1];
int hd[N],cnt;
void add(int a,int b){
    e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
}
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int fa[23][N],d[N],lg[N];
void dfs(int now,int f){
    d[now]=d[f]+1;
    fa[0][now]=f;
    int i;
    for(i=1;(1<<i)<=d[now];i++)
        fa[i][now]=fa[i-1][fa[i-1][now]];
    for(i=hd[now];i;i=e[i].n){
        int p=e[i].e;
        if(p!=f)dfs(p,now);
    }
}
int lca(int x,int y){
    int i;
    if(d[x]<d[y]){int t=x;x=y;y=t;}
    while(d[x]>d[y])
        x=fa[lg[d[x]-d[y]]][x];
    if(x==y)return x;
    for(i=lg[d[x]];~i;i--)
        if(fa[i][x]!=fa[i][y])
            x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
int in(int x,int y){
    return x>=1&&y>=1&&x<=n&&y<=m;
}
int pos[N];
int main(){
    int i,j;
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            p[++tot]=(Point){i,j,a[i][j],id(i,j)};
            f[tot]=tot;
            H[tot]=a[i][j];
        }
    }
    for(i=1;i<=tot;i++)pos[p[i].id]=i;
    sort(p+1,p+1+tot);
    for(i=1;i<=tot;i++){
        int x=p[i].x,y=p[i].y,idnow=p[i].id;
        for(j=0;j<4;j++){
            int tx=x+dx[j],ty=y+dy[j],idt=id(tx,ty);
            if(in(tx,ty)&&vis[idt]&&find(idt)!=find(idnow)){
                add(f[idnow],f[find(idt)]);
                f[find(idt)]=f[idnow];
            }
        }
        vis[idnow]=1;
    }
    dfs(p[tot].id,0);
    for(i=2;i<N;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
    for(i=0;i<q;i++){
        int X1,X2,Y1,Y2;
        scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
        int id1=pos[id(X1,Y1)],id2=pos[id(X2,Y2)];
        printf("%d\n",H[lca(id1,id2)]);
    }
    return 0;
}