| 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代码
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
31
32
33
34
35
36
37
38
39
40
typedef long long ll;
using namespace std;
char c[5],a[1010][1010];
struct E{
int e,n;
}e[10010];
int hd[30],cnt;
void add(int a,int b){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;}
int ind[30],oud[30];
queue<int>Q;
char seq[30];int top;
int main(){
int i,n;
scanf("%s%d",c,&n);
for(i=0;i<n;i++)scanf("%s",a[i]);
for(i=0;i<n-1;i++){
int j=0;
while(a[i][j]&&a[i][j]==a[i+1][j])j++;
if(a[i][j]){
int s=a[i][j]-'a',t=a[i+1][j]-'a';
add(s,t);
ind[t]++;oud[s]++;
}
}
int tot=0;
for(i=0;i<=c[0]-'a';i++)if(!ind[i])Q.push(i),tot++;
while(!Q.empty()){
int t=Q.front();Q.pop();
seq[++top]=t+'a';
for(i=hd[t];i;i=e[i].n){
int q=e[i].e;
if(!--ind[q])Q.push(q);
}
}
if(top!=c[0]-'a'+1)printf("IMPOSSIBLE");
else if(tot>1)printf("AMBIGUOUS");
else if(tot==1)printf("%s",seq+1);
return 0;
}
B Kattis - Falling Apples
题目描述
模拟重力掉落苹果。
解题思路
暴力模拟就行了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;
using namespace std;
char a[50010][12];
int main(){
int i,n,m,j;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%s",a[i]);
for(i=0;i<m;i++){
int now=n-1;
for(j=n-1;j>=0;j--){
if(a[j][i]=='a'){
a[now][i]='a';
if(now!=j)a[j][i]='.';
now--;
}else if(a[j][i]=='#')now=j-1;
}
}
for(i=0;i<n;i++)printf("%s\n",a[i]);
return 0;
}
C Kattis - Square Deal
题目描述
给三个矩形，问能不能够把他们无缝拼成一个正方形。
解题思路
首先必然有，三个矩形中最长的边的长度为正方形长度。
求出面积和即可求出边长，进而分两类讨论剩下两个如何拼即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;
using namespace std;
pair<int,int>p[5];
int solve(){
int i,sq=0;
for(i=0;i<3;i++)scanf("%d%d",&p[i].x,&p[i].y),sq+=p[i].x*p[i].y;
sort(p,p+3);
int l=sqrt(sq),now=l-p[2].y;
if(l*l!=sq||l!=p[2].x)return 0;
if(p[0].x==l&&p[1].x==l)return 1;
if(p[0].x==now){if(p[1].x==now||p[1].y==now)return 1;}
else if(p[1].x==now||p[1].y==now)return 1;
return 0;
}
int main(){
printf("%s",solve()?"YES":"NO");
return 0;
}
D Kattis - Buggy Robot
题目描述
给一张有障碍的图，上面有起点和终点。给定一段走路方向序列，要求用最少次数修改这个序列使得能够从起点走到终点。修改的方法有两种：删除一个、插入一个。走到终点后的所有序列会自动忽略。
解题思路
$dp[i][x][y]$表示用序列前$i$项、走到$(x,y)$所需要最少修改次数。存状态宽搜即可。
AC代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
typedef long long ll;
using namespace std;
int dp[102][51][51],ti,tj;
char a[52][52],s[52];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int f[260],n,m;
struct P{int i,x,y;};
queue<P>Q;
int in(int x,int y){return x>=0&&y>=0&&x<n&&y<m&&a[x][y]!='#';}
void bfs(){
while(!Q.empty()){
int i,x,y;
P top=Q.front();Q.pop();
for(i=0;i<4;i++){//add
x=top.x+dx[i],y=top.y+dy[i];
if(in(x,y)&&dp[top.i][x][y]>dp[top.i][top.x][top.y]+1)
dp[top.i][x][y]=dp[top.i][top.x][top.y]+1,Q.push({top.i,x,y});
}
if(s[top.i]){
if(dp[top.i+1][top.x][top.y]>dp[top.i][top.x][top.y]+1)//del
dp[top.i+1][top.x][top.y]=dp[top.i][top.x][top.y]+1,Q.push({top.i+1,top.x,top.y});
x=top.x+dx[f[s[top.i]]],y=top.y+dy[f[s[top.i]]];
if(in(x,y)){//keep
if(dp[top.i+1][x][y]>dp[top.i][top.x][top.y])
dp[top.i+1][x][y]=dp[top.i][top.x][top.y],Q.push({top.i+1,x,y});
}else{
if(dp[top.i+1][top.x][top.y]>dp[top.i][top.x][top.y])
dp[top.i+1][top.x][top.y]=dp[top.i][top.x][top.y],Q.push({top.i+1,top.x,top.y});
}
}
}
}
int main(){
int i,j,ans=1e9;
f['L']=0;f['R']=1;f['U']=2;f['D']=3;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%s",a[i]);
memset(dp,0x3f,sizeof(dp));
for(i=0;i<n;i++)for(j=0;j<m;j++)
if(a[i][j]=='S')dp[0][i][j]=0,Q.push({0,i,j});
else if(a[i][j]=='G')ti=i,tj=j;
scanf("%s",s);
bfs();
for(i=0;i<=strlen(s);i++)ans=min(ans,dp[i][ti][tj]);
printf("%d",ans);
return 0;
}
E Kattis - Construction Toy
题目描述
给小于$9$个线段，要拼成一堆边邻三角形，其中一条边为基线，问离这条线最远的点有多远。
解题思路
暴力枚举，每次枚举到哪条边上加边，保存边的使用与否，可以获得$TLE(10/15)$。
TLE代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
typedef long long ll;
using namespace std;
int n,l[10];
struct Seg{
double a1,b1,a2,b2;
int l;
}a[10];
int tot;
double ans=0,pi=acos(-1);
int proper(int a,int b,int c){return a+b>c&&a+c>b&&b+c>a;}
void deal(int flag,Seg pre,int b,int c){
int l=pre.l;
double a1=pre.a1,a2=pre.a2,b1=pre.b1,b2=pre.b2;
double theta=atan2(b2-b1,a2-a1)+acos((b*b+l*l-c*c)/(2.0*b*l))*(flag==1?-1:1);
double tx=cos(theta)*b+a1,ty=sin(theta)*b+b1;
a[tot++]={a1,b1,tx,ty,b};
a[tot++]={a2,b2,tx,ty,c};
}
int vis[10];
void dfs(){
int i,k,j;
for(i=0;i<tot;i++)ans=max(ans,max(a[i].a1,a[i].a2));
if(tot>=n-1)return;
for(k=0;k<tot;k++){
if(vis[k])continue;
i=tot,j=tot+1;
if(proper(a[k].l,l[i],l[j])){
vis[k]=1;
deal(1,a[k],l[i],l[j]);
if(a[tot-1].a1>=0&&a[tot-2].a2>=0)dfs();
tot-=2;
if(tot==1){
vis[k]=0;
continue;
}
deal(2,a[k],l[i],l[j]);
if(a[tot-1].a1>=0&&a[tot-2].a2>=0)dfs();
tot-=2;
vis[k]=0;
}
}
}
int main(){
int i;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&l[i]);
sort(l,l+n);
do{
a[0]={0,0,0,l[0],l[0]};tot=1;
dfs();
}while(next_permutation(l,l+n));
printf("%.10f",ans);
return 0;
}
其实这样会引起很多重复，我们只需要每次在新扩展出的边上进行$DFS$即可，可以获得$AC$。
AC代码
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
31
32
33
typedef long long ll;
using namespace std;
int n,l[10];
double ans=0,pi=acos(-1);
int proper(double a,double b,double c){return a+b>c&&a+c>b&&b+c>a;}
int vis[10];
void dfs(double a1,double b1,double a2,double b2,int dep){
int i;
if(dep>n-1)return;
double a=sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2)),b=l[dep],c=l[dep+1];
if(!proper(a,b,c))return;
for(i=0;i<2;i++){
double theta=atan2(b2-b1,a2-a1)+acos((b*b+a*a-c*c)/(2.0*b*a))*(i?1:-1);
double tx=cos(theta)*b+a1,ty=sin(theta)*b+b1;
if(tx<0)continue;
dfs(a1,b1,tx,ty,dep+2);
dfs(a2,b2,tx,ty,dep+2);
ans=max(ans,tx);
if(dep==1)break;
}
}
int main(){
int i;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&l[i]);
sort(l,l+n);
do{
dfs(0,0,0,l[0],1);
}while(next_permutation(l,l+n));
printf("%.10f",ans);
return 0;
}
F Kattis - Around and Around We Go
题目描述
按照节拍对齐两个声部并输出。
解题思路
分拍模拟即可，但不知道为什么会WA。
迫 真 码 农 题
AC代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
typedef long long ll;
using namespace std;
int n;
char p[21][80][80],c;
int t[21][80],num[21];
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代码
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
typedef long long ll;
using namespace std;
ll a[15];
ll temp[15][15];
int main(){
int i,j,n;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%lld",&a[i]),temp[0][i]=a[i];
int now=n-1;
for(i=1;;i++){
int flag=0;
for(j=0;j<now;j++)temp[i][j]=temp[i-1][j+1]-temp[i-1][j];
for(j=0;j<now;j++)if(temp[i][j]!=temp[i][1]){
flag=1;
break;
}
if(!flag)break;
now--;
}
temp[i][n-i]=temp[i][0];
int ans=i;
for(i--;i>=0;i--)temp[i][n-i]=temp[i][n-i-1]+temp[i+1][n-i-1];
printf("%d %lld",ans,temp[0][n]);
return 0;
}
H Kattis - Ghostbusters 2
题目描述
平面上有一些放着武器的点，武器可以水平或竖直放置，武器的攻击范围为两侧对称的一定长度，问不互相打到最大的攻击范围是多少。
解题思路
二分答案，一个武器水平或竖直放置是一个$0/1$问题，用$2-sat$解决。
AC代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int n;
struct P{
int x,y;
}a[N];
struct Edge{
int e,n;
}e[N*N];
int hd[N],count;
void add(int a,int b){e[++count].e=b;e[count].n=hd[a];hd[a]=count;}
int col[N],sta[N],dfn[N],low[N],cnt,tot,top,vis[N];
void tarjan(int p){
int i,q;
dfn[p]=low[p]=++cnt;
sta[++top]=p;vis[p]=1;
for(i=hd[p];i;i=e[i].n){
q=e[i].e;
if(!dfn[q])tarjan(q),low[p]=std::min(low[p],low[q]);
else if(vis[q])low[p]=std::min(low[p],dfn[q]);
}
if(low[p]==dfn[p]){
tot++;
do{
q=sta[top--];
col[q]=tot;
vis[q]=0;
}while(q!=p);
}
}
int jud(int x){//horizontal 1;vertical 0(+n)
cl(dfn);cl(col);cl(hd);cl(vis);cl(low);count=top=tot=cnt=0;
int i,j;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(a[i].x==a[j].x&&(fabs(a[i].y-a[j].y)-1)/2<x)add(i,j+n),add(j,i+n);
if(a[i].y==a[j].y&&(fabs(a[i].x-a[j].x)-1)/2<x)add(i+n,j),add(j+n,i);
}
}
for(i=0;i<n<<1;i++)if(!dfn[i])tarjan(i);
for(i=0;i<n;i++)if(col[i]==col[i+n])return 0;
return 1;
}
int main(){
int i;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);
int ans=0,l=0,r=1000010;
if(jud(r))return printf("UNLIMITED"),0;
while(l<=r){
int mid=(l+r)>>1;
if(jud(mid))ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
return 0;
}
I Kattis - Postal Delivery
题目描述
一个邮递员要从原点向数轴上某些点投一定量的邮件，每次装车件数有限制。求最短总路程。
解题思路
贪心就行了，分正负两部分解决即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
typedef long long ll;
int a[1010],b[1010],n,k;
int main(){
int i;
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)scanf("%d%d",&a[i],&b[i]);
ll ans=0;
int pos=n;
for(i=0;i<n;i++)if(a[i]>0){pos=i;break;}
int now=0;
for(i=0;i<pos;i++){
while(now<b[i])ans+=-a[i]*2,b[i]-=now,now=k;
now-=b[i];
}
now=0;
for(i=n-1;i>=pos;i--){
while(now<b[i])ans+=a[i]*2,b[i]-=now,now=k;
now-=b[i];
}
printf("%lld",ans);
}
J Kattis - Windy Path
题目描述
给定平面上的一些点，找出一个不自交的路径序列保证符合给定的转弯顺序。保证没有三点共线。
解题思路
先找到左下角的点（保证在边界），当下一个要转向右时，找到相对最左的那个点（与上一个形成的线段之间的夹角最小），否则找最右那个点。这个构造方法保证了每一次能够使得下一次无论选择哪个点都是正确的转向，同时选择斜率最大保证了不自交。
AC代码
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
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;
}