PKU演習問メモ(9/5)
ノルマ終わらないやばい
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 1577 | Falling Leaves | グラフ・二分探索木 | ★★★★☆ |
| 1590 | Palindromes | 実装 | ★★☆☆☆ |
| 1325 | Machine Schedule | 二部グラフの最小辺被覆 | ★★★☆☆ |
| 1313 | Booklet Printing | 実装 | ★★☆☆☆ |
| 1473 | There's Treasure Everywhere! | 実装 | ★★☆☆☆ |
1577 Falling Leaves
問題概要
各辺の値が英大文字一文字（またはnull）であるような二分探索木がある。
この木の葉をむしり、左側に葉から順にその文字を出力する。
つぎにその残りの木に同じ操作をする。これを木がなくなるまで繰り返す。
このような操作により出力された文字列が与えられた時、元の二分探索木を復元し、それを行きがけ順で出力せよ。
条件を満たす木はただ一通りに定まるとしてよい。
解法
そんな難しくないはずなのにだいぶ苦戦した……ので難易度高くしておいたｗ
まず、問題文で考える木は二分探索木なので、各ノードにつき子の数は最大2つ。
更に、左側の子の値は自分より小さく、右側の子の値は自分より大きい。
根から葉を復元する方針で行く。
ある段階で出力される葉は、その前の段階では葉ではなかったので、
根から葉を復元している際に、葉をつける条件として、
- 上の二分探索木の条件を満たす
- 全ての（さっきの）葉に子をつける
ことが必要になる。これを探索により定めていけばよい。
木のノード数は最高でも26なのでこの方針で十分間に合う。
ソースコード
char in[30][30]; int l[30],r[30],n,m,cld[30],cn; char tree[30]; void pre(int c) { putchar(tree[c]); if(l[c]>=0)pre(l[c]); if(r[c]>=0)pre(r[c]); } void getcld(int c) { if(l[c]<0)cld[cn++]=c; else getcld(l[c]); if(r[c]<0)cld[cn++]=c; else getcld(r[c]); } bool rec(int p,int q,char *s) { if(!s[p]) { for(;q<cn;q++)if(l[cld[q]]<0&&r[cld[q]]<0)return 0; return 1; } int c=cld[q]; if(l[c]<0&&tree[c]>s[p]) { l[c]=n; tree[n++]=s[p]; if(rec(p+1,q,s))return 1; l[c]=-1; n--; } if(r[c]<0&&tree[c]<s[p]) { r[c]=n; tree[n++]=s[p]; if(rec(p+1,q,s))return 1; r[c]=-1; n--; } if((l[c]>=0||r[c]>=0)&&q+1<cn&&rec(p,q+1,s))return 1; return 0; } int main() { do { m=0; n=1; rep(i,30)tree[i]=0,l[i]=r[i]=-1; while(scanf("%s",in[m]),isalpha(in[m][0]))m++; tree[0]=in[m-1][0]; for(int i=m-2;i>=0;i--) { cn=0; getcld(0); rec(0,0,in[i]); } pre(0); puts(""); } while(in[m][0]!='$'); return 0; }
1590 Palindromes
問題概要
与えられた文字列が
- 回文
- 線対称
- 回文かつ線対称
- いずれでもない
のどれかを判定せよ。
回文とは逆から読んでも自身と同じになるような文字列であり、線対称な文は、
それの文字列の中心を通り、鉛直な軸について対称移動しても自身と同じになる文字列をいう。
ある文字を鏡文字にした文字の表は与えられる（省略）
解法
特に工夫は必要なく通る。
mirroredのほうは逆順に、文字を鏡文字にしながら自身と一致するかを見ていけばよい。
ソースコード
char in[25]; int main() { char rev[256]={0}; char *revs="AAE3HHIIJLLJMMOOS2TTUUVVWWXXYYZ5112S3E5Z88"; for(int i=0;revs[i];i++)rev[revs[i]]=revs[++i]; while(~scanf("%s",in)) { bool pali=1,mir=1; for(int i=0,j=strlen(in)-1;i<=j;i++,j--) { if(in[i]!=in[j])pali=0; if(rev[in[i]]==0||rev[in[j]]==0|| rev[in[i]]!=in[j]||rev[in[j]]!=in[i])mir=0; } printf("%s -- ",in); if(pali&&mir)puts("is a mirrored palindrome."); else if(pali)puts("is a regular palindrome."); else if(mir)puts("is a mirrored string."); else puts("is not a palindrome."); puts(""); } return 0; }
1325 Machine Schedule
問題概要
二台の機械A,Bがある。Aはn通り、Bはm通りの動作モードがある。
k個のタスクがあたえられる。それらはAのモードa,Bのモードbでのいずれかにより処理できる。
機械の動作モードを変更するには手間がかかるので、できるだけその回数を最小にしたい。
そのような回数を求めよ。初め、二つの機械のモードはともに0である。
n,m＜100, k＜1000を満たす。
解法
複数入力ケースがあるので対応させないとWA.
n個の赤い頂点とm個の青い頂点をもった二部グラフを作る。
1つのタスクがモードaとモードbのいずれかで処理できるとき、赤い頂点のa番目と青い頂点のb番目を辺で結ぶ。
すると、機械の動作モードの変更回数はグラフの最小辺被覆となる。
つまり、二部グラフの最大マッチングに帰結する。
（0番のモードは最初に処理できるので、そのタスクは辺を張る必要はない）
ソースコード
int n,m,k; vector<vi> e; int p[1000]; bool v[1000]; bool match(int s) { if(s<0)return 1; fr(i,e[s])if(!v[*i]) { v[*i]=1; if(match(p[*i]))return p[*i]=s,p[s]=*i,1; } return 0; } int main() { while(scanf("%d",&n),n) { scanf("%d%d",&m,&k); e.clear(); e.resize(n+m); rep(i,k) { int dmy,a,b; scanf("%d%d%d",&dmy,&a,&b); if(a==0||b==0)continue; e[a].pb(b+n); e[b+n].pb(a); } int ans=0; rep(i,n+m)p[i]=-1; rep(i,n) { rep(j,n+m)v[j]=0; if(match(i))ans++; } printf("%d\n",ans); } return 0; }
1313 Booklet Printing
問題概要
両面印刷で、折りたたまれた本を印刷するにはたとえば4ページの本なら、
1枚目の表に左側に4ページ目、右側に1ページ目
裏の左側に2ページ目、右側に3ページ目を印刷する。
ページの数が与えられたとき、各紙の裏表の左右に印刷されるページ番号を出力せよ。
解法
backと:の間のスペースを忘れるとPEになる。同じ間違いをしている人が結構いるような……
1枚目の表に(最後のページ) 1ページ目、
裏に2ページ目 最後から2番目のページ……と印刷されてく。
それを配列か何かに書き込んで出力すればよい。
ソースコード
int main() { int n; while(scanf("%d",&n),n) { int m=n/4+(n%4!=0),s[25][4]={0}; rep(i,m) { s[i][0]=4*m-2*i; s[i][1]=2*i+1; s[i][2]=2*i+2; s[i][3]=4*m-2*i-1; } rep(i,m)rep(j,4)if(s[i][j]>n)s[i][j]=0; printf("Printing order for %d pages:\n",n); rep(i,m) { if(s[i][0]||s[i][1]) { printf("Sheet %d, front: ",i+1); if(!s[i][0])printf("Blank, "); else printf("%d, ",s[i][0]); if(!s[i][1])printf("Blank\n"); else printf("%d\n",s[i][1]); } if(s[i][2]||s[i][3]) { printf("Sheet %d, back : ",i+1); if(!s[i][2])printf("Blank, "); else printf("%d, ",s[i][2]); if(!s[i][3])printf("Blank\n"); else printf("%d\n",s[i][3]); } } } return 0; }
1473 There's Treasure Everywhere!
問題概要
原点から8方位に、距離1ずつ何度か移動する。
移動が文字列により与えられたとき、最終地点の座標および原点からの距離を求めよ。
解法
x座標とy座標を足してけばよい。んだけど文字列のパーズが面倒。
ソースコード
なんか汚い。
char in[201]; int main() { int cs=0; while(gets(in),in[0]!='E') { for(int i=0;in[i];i++)if(!isdigit(in[i])&& in[i]!='N'&&in[i]!='E'&&in[i]!='S'&&in[i]!='W') in[i]=' '; double x=0,y=0; for(int c=0;in[c];c++) { double d=0; char dir[3]={0}; for(;in[c]&&in[c]!='N'&&in[c]!='E'&&in[c]!='S'&&in[c]!='W';c++) d*=10,d+=in[c]-'0'; for(int i=0;in[c]&&in[c]!=' ';i++,c++)dir[i]=in[c]; int dx=0,dy=0; for(int i=0;dir[i];i++) { if(dir[i]=='N')dy=1; if(dir[i]=='S')dy=-1; if(dir[i]=='W')dx=-1; if(dir[i]=='E')dx=1; } if(dy==0&&dx==0)break; d/=hypot(dx,dy); x+=dx*d; y+=dy*d; } printf("Map #%d\n",++cs); printf("The treasure is located at (%.3f,%.3f).\n",x,y); printf("The distance to the treasure is %.3f.\n\n",hypot(x,y)); } return 0; }
