1602 Zip

「1602 Zip」の編集履歴(バックアップ)一覧はこちら

1602 Zip」(2006/04/17 (月) 01:46:34) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

** 1602 Zip ** 問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=1602 ** 解答例 import java.util.*; public class Main { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); String mode = sc.next(); if(mode.equals("A")){ int n = sc.nextInt(); char[] str = new char[n]; str = sc.next().toCharArray(); if(n==1){ System.out.println(str); System.out.println(1); return; } // n>1 ZipString[] zs = new ZipString[n]; for(int i=0;i<n;i++){ char head = str[i]; char tail = str[(i+n-1)%n]; ZipString z = new ZipString(i,head,tail); zs[i] = z; } Arrays.sort(zs); char[] zstr = new char[n]; int p = -1; for(int i=0;i<n;i++){ zstr[i] = zs[i].tail; if(zs[i].k==1) p = i; } System.out.println(zstr); System.out.println(p+1); } else if(mode.equals("B")){ int n = sc.nextInt(); char[] zstr = new char[n]; zstr = sc.next().toCharArray(); int p = sc.nextInt()-1; char[] zstr_next = new char[n]; for(int i=0;i<n;i++) zstr_next[i] = zstr[i]; Arrays.sort(zstr_next); int[] m = new int[26]; Arrays.fill(m,-1); for(int i=0;i<n;i++) m[(zstr_next[i])-'a'] = i; char[] str = new char[n]; int a = -1; for(int i=0;i<n;i++){ if(zstr_next[i]==zstr[p]){ a = i; break; } } str[n-1] = zstr[a]; for(int i=n-1;i>0;i--){ int k = m[str[i]-'a']; str[i-1] = zstr[k]; m[str[i]-'a'] = k-1; } System.out.println(str); } else throw new Exception(); } } class ZipString implements Comparable<ZipString>{ int k; char head; char tail; ZipString(int k, char head,char tail) { this.k = k; this.head = head; this.tail = tail; } public boolean equals(Object o){ ZipString z = (ZipString)o; return this.head==z.head; } public int compareTo(ZipString z){ return this.head-z.head; } }
**1602 Zip **問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=1602 **解答例 import java.util.*; public class Main { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); String mode = sc.next(); if(mode.equals("A")){ int n = sc.nextInt(); char[] str = new char[n]; str = sc.next().toCharArray(); if(n==1){ System.out.println(str); System.out.println(1); return; } // n>1 ZipString[] zs = new ZipString[n]; for(int i=0;i<n;i++){ char head = str[i]; char tail = str[(i+n-1)%n]; ZipString z = new ZipString(i,head,tail); zs[i] = z; } Arrays.sort(zs); char[] zstr = new char[n]; int p = -1; for(int i=0;i<n;i++){ zstr[i] = zs[i].tail; if(zs[i].k==1) p = i; } System.out.println(zstr); System.out.println(p+1); } else if(mode.equals("B")){ int n = sc.nextInt(); char[] zstr = new char[n]; zstr = sc.next().toCharArray(); int p = sc.nextInt()-1; char[] zstr_next = new char[n]; for(int i=0;i<n;i++) zstr_next[i] = zstr[i]; Arrays.sort(zstr_next); int[] m = new int[26]; Arrays.fill(m,-1); for(int i=0;i<n;i++) m[(zstr_next[i])-'a'] = i; char[] str = new char[n]; int a = -1; for(int i=0;i<n;i++){ if(zstr_next[i]==zstr[p]){ a = i; break; } } str[n-1] = zstr[a]; for(int i=n-1;i>0;i--){ int k = m[str[i]-'a']; str[i-1] = zstr[k]; m[str[i]-'a'] = k-1; } System.out.println(str); } else throw new Exception(); } } class ZipString implements Comparable<ZipString>{ int k; char head; char tail; ZipString(int k, char head,char tail) { this.k = k; this.head = head; this.tail = tail; } public boolean equals(Object o){ ZipString z = (ZipString)o; return this.head==z.head; } public int compareTo(ZipString z){ return this.head-z.head; } }

表示オプション

横に並べて表示:
変化行の前後のみ表示:
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。