latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年1月5日 星期二

[ UVA ] 741 - Burrows Wheeler Decoder

題目:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=682

解法:
BWT逆轉換,可以參考Morris的這篇,透過觀察題目範例:

1. A B A N A N
2. A N A B A N
3. A N A N A B
4. B A N A N A
5. N A B A N A
6. N A N A B A
(我們只知道最後一行(設為字串s)的NNBAAA和原字串在第4個位置)

發現我們只能利用排序求出第一行的AAABNN,因為BWT轉換是利用字串rotate,所以可以把s和它結合起來
NA
NA
BA
AB
AN
AN
在排序就可以得到前兩行了
AB
AN
AN
BA
NA
AN
同樣發現因為rotate的關係,所以可以再開頭加上s求出前三行.....以此類推

code:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main(){
    bool is=0;
    string s;
    for(int p;cin>>s>>p;){
        if(s=="END")break;
        if(is)cout<<endl;
        is=1;
        int n=s.length();
        string a[n];
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j)a[j]=s[j]+a[j];
            sort(a,a+n);
        }
        cout<<a[p-1]<<endl;
    }
    return 0;
}

沒有留言:

張貼留言