HDU 5442 Favorite Donut

你的名字 2022-08-05 10:27 147阅读 0赞

第一种方法，最小表示法  
其实呢，你将每一个字母反转一下，将’a’变成’z’，就是最小表示法。  
但是反转之后，我们如果用最小表示法，得到的是，在原串上位置最靠后的情况，与题意不服，所以我这里就强行将之往后硬判，最坏复杂度是当串所以的字符都相同的情况，退化成*O*(*n*2)。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<50
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    
    const int MAXN=20010;
    
    char str[MAXN],rev[MAXN];
    int n,ch[30];
    
    int init()
    {
        int now='z';
        for(int i=0; i<26; i++)
            ch[i]=now--;
    }
    
    
    int getsmall(string s, bool flag)
    {
        int i,j,k,l;
        int N=s.length();
        s+=s;
        int ans=0;
        for(i=0,j=1; j<N;)
        {
            for(k=0; k<N&&s[i+k]==s[j+k]; k++);
            if(k>=N)
            {
                if(flag)
                {
                    ans=j;
                    j++;
                    continue;
                }
                break;
            }
            if(s[i+k]<s[j+k])
            {
                j+=k+1;
            }
            else
            {
                l=i+k;
                i=j;
                ans=i;
                j=max(l,j)+1;
            }
        }
        return ans;
    }
    
    bool compare(int ans0,int ans1)
    {
        int pos1=ans0,pos2=ans1;
        for(int i=0; i<n; i++)
        {
            if(str[pos1]==str[pos2])
            {
                if(++pos1>=n) pos1-=n;
                if(--pos2<0) pos2+=n;
            }
            else
            {
                return str[pos1]>str[pos2];
            }
        }
        return ans0<=ans1;
    }
    
    string st,en;
    
    int main()
    {
    // freopen("data.txt", "r", stdin);
        init();
        int T;
        read(T);
        while(T--)
        {
            st.clear();
            en.clear();
            read(n);
            scanf("%s",str);
            for(int i=0; i<n; i++)
                st+=ch[str[i]-'a'];
            en=st;
            reverse(en.begin(),en.end());
            int ans0=getsmall(st,false);
            int tmp=getsmall(en,true);
            int ans1=(n-tmp-1)%n;
            if (compare(ans0,ans1))
                printf("%d 0\n",ans0+1);
            else
                printf("%d 1\n",ans1+1);
        }
        return 0;
    }

后缀数组法，裸的后缀数组应用

// xixihaha
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=100010;
    
    char C[MAXN],rC[MAXN];
    int idx[MAXN],mp[MAXN];
    
    int rk[MAXN],sa[MAXN],height[MAXN],w[MAXN],wa[MAXN],ret[MAXN];
    void getSa (int len,int up)
    {
        int *k = rk;
        int *id = height;
        int *r = ret;
        int  *cnt = wa;
        for(int i=0;i<up;i++) cnt[i] = 0;
        for(int i=0;i<len;i++) cnt[k[i] = w[i]]++;
        for(int i=0;i<up;i++) cnt[i+1] += cnt[i];
        for(int i = len - 1; i >= 0; i--) {
            sa[--cnt[k[i]]] = i;
        }
        for(int d = 1,p = 0; p < len;){
            for(int i = len - d; i < len; i++) id[p++] = i;
            for(int i=0;i<len;i++)if(sa[i] >= d) id[p++] = sa[i] - d;
            for(int i=0;i<len;i++) r[i] = k[id[i]];
            for(int i=0;i<up;i++) cnt[i] = 0;
            for(int i=0;i<len;i++) cnt[r[i]]++;
            for(int i=0;i<up;i++) cnt[i+1] += cnt[i];
            for(int i = len - 1; i >= 0; i--) {
                sa[--cnt[r[i]]] = id[i];
            }
            swap(k,r);
            p = 0;
            k[sa[0]] = p++;
            for(int i=0;i<len-1;i++) {
                if(sa[i]+d < len && sa[i+1]+d <len &&r[sa[i]] == r[sa[i+1]]&& r[sa[i]+d] == r[sa[i+1]+d])
                    k[sa[i+1]] = p - 1;
                else k[sa[i+1]] = p++;
            }
            if(p >= len) return ;
            d *= 2,up = p, p = 0;
        }
    }
    void getHeight(int len) {
        for(int i=0;i<len;i++) rk[sa[i]] = i;
        height[0] =  0;
        for(int i = 0,p = 0; i < len - 1; i++) {
            int j = sa[rk[i]-1];
            while(i+p < len&& j+p < len&& w[i+p] == w[j+p]) {
                p++;
            }
            height[rk[i]] = p;
            p = max(0,p - 1);
        }
    }
    int getSuffix(char s[]) {
        int len = strlen(s),up = 0;
        for(int i = 0; i < len; i++) {
            w[i] = s[i];
            up = max(up,w[i]);
        }
        w[len++] = 0;
        getSa(len,up+1);
        getHeight(len);
        return len;
    }
    
    
    int solve(char s[],int n)
    {
        int len=getSuffix(s);
    
        /* for(int i=1;i<len;i++){ printf("%s\n",s+sa[i]); }*/
        int start=len-1;
        while(sa[start]>n/2)start--;
        int ans=idx[sa[start]];
        while(height[start]>=n/2){
            start--;
            ans=min(ans,idx[sa[start]]);
        }
        return ans;
    }
    int cmp(int x,int y,int n)
    {
        for(int i=x,j=y,k=0;k<n;k++,i++,j++){
            if(C[i]==rC[j])continue;
            if(C[i]<rC[j])return -1;
            if(C[i]>rC[j])return 1;
        }
        return 0;
    }
    int main()
    {
        // freopen("in","r",stdin);
        int T;scanf("%d",&T);
        while(T--){
            int n;
            scanf("%d",&n);
            scanf("%s",C);
            for(int i=0;i<n;i++)rC[i]=C[i];
            reverse(rC,rC+n);
            for(int i=0;i<n;i++){
                C[i+n]=C[i];
                idx[i]=idx[i+n]=i;
            }
            C[n*2]='\0';
            int ans=solve(C,n*2),dir=0;
            for(int i=0;i<n;i++){
                rC[i+n]=rC[i];
                idx[i]=idx[n+i]=n-i-1;
                mp[n-i-1]=i;
            }
            rC[n*2]='\0';
            // cout<<rC<<endl;
            int res=solve(rC,n*2);
            // cout<<ans<<"!!"<<res<<endl;
            // cout<<string(C+ans,n)<<endl;
            // cout<<string(rC+mp[res],n)<<endl;
            int flag=cmp(ans,mp[res],n);
            if(flag==-1){
                ans=res,dir=1;
            }
            else if(flag==0){
                if(res<ans){
                    ans=res;
                    dir=1;
                }
            }
            printf("%d %d\n",ans+1,dir);
        }
        return 0;
    }