2019 BUAA Spring Training 13 题解

Solved	A	B	C	D	E	F	G	H	I	J
10/10	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 Kattis - As Easy as CAB

题目描述

给定一系列按照某种字典序排好的字符串，求字典序。

解题思路

那就按照从小到大连边，找出这个图集的拓扑序，如果有环则拓扑序长度与给定长度不等，输出IMPOSSIBLE；否则一定能够找到一种方法，如果刚开始的入度为零的点为一是一条链那么就输出拓扑序，否则输出AMBIGUOUS。

AC代码

点击

B Kattis - Falling Apples

题目描述

模拟重力掉落苹果。

解题思路

暴力模拟就行了。

AC代码

点击

C Kattis - Square Deal

题目描述

给三个矩形，问能不能够把他们无缝拼成一个正方形。

解题思路

首先必然有，三个矩形中最长的边的长度为正方形长度。

求出面积和即可求出边长，进而分两类讨论剩下两个如何拼即可。

AC代码

点击

D Kattis - Buggy Robot

题目描述

给一张有障碍的图，上面有起点和终点。给定一段走路方向序列，要求用最少次数修改这个序列使得能够从起点走到终点。修改的方法有两种：删除一个、插入一个。走到终点后的所有序列会自动忽略。

解题思路

$dp[i][x][y]$ 表示用序列前 $i$ 项、走到 $(x,y)$ 所需要最少修改次数。存状态宽搜即可。

AC代码

点击

E Kattis - Construction Toy

题目描述

给小于 $9$ 个线段，要拼成一堆边邻三角形，其中一条边为基线，问离这条线最远的点有多远。

解题思路

暴力枚举，每次枚举到哪条边上加边，保存边的使用与否，可以获得 $TLE(10/15)$ 。

TLE代码

点击

其实这样会引起很多重复，我们只需要每次在新扩展出的边上进行 $DFS$ 即可，可以获得 $AC$ 。

AC代码

点击

F Kattis - Around and Around We Go

题目描述

按照节拍对齐两个声部并输出。

解题思路

分拍模拟即可，但不知道为什么会WA。

迫真码农题

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
char p[21][80][80],c;
int t[21][80],num[21];
#define N 1610
char inin[N];
void read(int x){
    fgets(inin,1600,stdin);
    int i;
    for(i=0;i<strlen(inin);i++){
        int charnow=0;
        while(inin[i]==' ')i++;
        c=inin[i];
        while(c&&c!=' '&&c!='\n'&&c!='\r'){
            p[x][num[x]][charnow++]=c;
            c=inin[++i];
        }
        num[x]++;
    }
    fgets(inin,1600,stdin);
    int number=0;
    for(i=0;i<strlen(inin);i++){
        int num=0;
        while(inin[i]==' ')i++;
        c=inin[i];
        while(c>='0'&&c<='9')num=num*10+c-'0',c=inin[++i];
        t[x][number++]=num;
    }
}
pair<int,pair<int,int> >pai[16620],pai2[16620];
int tot,cnt[N];
char ans[N][N],ans2[N][N];
int main(){
    int i,j,d;
    scanf("%d%d",&n,&d);
    fgets(inin,1600,stdin);
    for(i=0;i<n;i++)read(i);
    for(i=0;i<n;i++){
        for(j=0;j<num[i];j++){
            pai[tot]=make_pair(1,make_pair(i,j));
            tot+=t[i][j];
        }
    }
    for(i=0;i<d;i++)pai2[i]=make_pair(0,make_pair(0,0));
    for(i=0;i<=tot;i++)pai2[d+i]=pai[i];
    for(i=0;i<n;i++){
        for(j=0;j<num[i];j++)cnt[i]+=t[i][j];
        cnt[i]+=i?cnt[i-1]:0;
    }
    int bt=0;
    for(i=0;i<n;i++){
        int pre=-1;
        while(bt<cnt[i]){
            if(pai[bt].first&&pai2[bt].first){
                pre=max(strlen(ans[i]),strlen(ans2[i]));
                for(j=0;j<pre;j++){
                    if(!ans[i][j])ans[i][j]='_';
                    if(!ans2[i][j])ans2[i][j]='_';
                }
                strcat(ans[i],p[pai[bt].second.first][pai[bt].second.second]);
                strcat(ans[i],"_");
                strcat(ans2[i],p[pai2[bt].second.first][pai2[bt].second.second]);
                strcat(ans2[i],"_");
            }else if(pai[bt].first){
                pre=strlen(ans[i]);
                for(j=strlen(ans2[i]);j<=strlen(ans[i]);j++)ans2[i][j]='_';
                strcat(ans[i],p[pai[bt].second.first][pai[bt].second.second]);
                strcat(ans[i],"_");
            }else if(pai2[bt].first){
                pre=strlen(ans2[i]);
                for(j=strlen(ans[i]);j<=strlen(ans2[i]);j++)ans[i][j]='_';
                strcat(ans2[i],p[pai2[bt].second.first][pai2[bt].second.second]);
                strcat(ans2[i],"_");
            }
            bt++;
        }
        while(ans[i][strlen(ans[i])-1]=='_')ans[i][strlen(ans[i])-1]=0;
        while(ans2[i][strlen(ans2[i])-1]=='_')ans2[i][strlen(ans2[i])-1]=0;
        printf("%s\n%s\n",ans[i],ans2[i][0]?ans2[i]:"/");
    }
    return 0;
}

G Kattis - The Calculus of Ada

题目描述

给一个数组，问多少次差分之后能把它们全变为相同的数，并预测数列的下一项。

解题思路

搞个矩阵模拟一下就好了。

AC代码

点击

H Kattis - Ghostbusters 2

题目描述

平面上有一些放着武器的点，武器可以水平或竖直放置，武器的攻击范围为两侧对称的一定长度，问不互相打到最大的攻击范围是多少。

解题思路

二分答案，一个武器水平或竖直放置是一个 $0/1$ 问题，用 $2-sat$ 解决。

AC代码

点击

I Kattis - Postal Delivery

题目描述

一个邮递员要从原点向数轴上某些点投一定量的邮件，每次装车件数有限制。求最短总路程。

解题思路

贪心就行了，分正负两部分解决即可。

AC代码

点击

J Kattis - Windy Path

题目描述
给定平面上的一些点，找出一个不自交的路径序列保证符合给定的转弯顺序。保证没有三点共线。

解题思路
先找到左下角的点（保证在边界），当下一个要转向右时，找到相对最左的那个点（与上一个形成的线段之间的夹角最小），否则找最右那个点。这个构造方法保证了每一次能够使得下一次无论选择哪个点都是正确的转向，同时选择斜率最大保证了不自交。

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
25
26
27
28
29
30
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct P{
    int x,y,i,flag;
    bool operator<(const P&a)const{return x<a.x||x==a.x&&y<a.y;}
    P operator-(const P&a)const{return {x-a.x,y-a.y};}
}a[52];
char dir[52];
int seq[52];
int cross(P a,P b){
    return a.x*b.y-a.y*b.x;
}
int main(){
    int i,j,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),a[i].i=i;
    scanf("%s",dir);
    sort(a+1,a+n+1);
    for(i=2;i<n;i++){
        int flag=dir[i-2]=='L'?-1:1;
        int nxt=i;
        for(j=i+1;j<=n;j++)
            if(cross(a[nxt]-a[i-1],a[j]-a[i-1])*flag>0)
                nxt=j;
        swap(a[nxt],a[i]);
    }
    for(i=1;i<=n;i++)printf("%d ",a[i].i);
    return 0;
}