QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771600#6618. Encoded Strings IIucup-team3161#WA 2ms7956kbC++171.5kb2024-11-22 14:30:162024-11-22 14:30:17

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 14:30:17]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7956kb
  • [2024-11-22 14:30:16]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define Dow(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

const int N = 1010, M = 1<<20|10;
int n,las[N][26],pre[N][26],all,r[M];
char s[N];
struct node{
    int cnt,a[21],las;
}f[M];

inline int get(int c,int l,int r){
    return pre[r][c]-pre[l-1][c];
}

inline bool cmp(node *x,node *y){
    For(i,1,x->cnt){
        if (x->a[i] > y->a[i]) return 1;
        if (x->a[i] < y->a[i]) return 0;
    }
    return x->las < y->las;
}

int main(){
    scanf("%d%s",&n,s+1);
    For(i,1,n){
        For(j,0,19) las[i][j]=las[i-1][j];
        las[i][s[i]-'a']=i;
        all|=(1<<(s[i]-'a'));
    }
    For(i,1,n){
        For(j,0,19) pre[i][j]=pre[i-1][j];
        pre[i][s[i]-'a']++;
    }
    FOR(i,0,1<<20) if ((i&all)==i){
        r[i]=n+1;
        For(j,0,19) if (i>>j&1) r[i]=min(r[i],las[n][j]);
    }
    Dow(i,(1<<20)-1,1) if ((i&all)==i){
        if (i!=all&&!f[i].cnt) continue;
        node tmp=f[i];
        ++tmp.cnt;
        For(j,0,19) if (i>>j&1){
            int k=i^(1<<j);
            tmp.a[tmp.cnt]=get(j,tmp.las+1,r[k]-1);
            tmp.las=las[r[k]-1][j];
            if (tmp.a[tmp.cnt]<=0) continue;
            if (!f[k].cnt) f[k]=tmp;
            else if (cmp(&tmp,&f[k])) f[k]=tmp;
        }
    }
    For(i,1,f[0].cnt){
        For(j,1,f[0].a[i]) printf("%c",f[0].cnt-i+'a');
    }
}
/*
6
aabbcc

4
abab

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5808kb

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5896kb

input:

4
acac

output:

bba

result:

ok single line: 'bba'

Test #3:

score: 0
Accepted
time: 2ms
memory: 7956kb

input:

1
t

output:

a

result:

ok single line: 'a'

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 5884kb

input:

12
bcabcabcbcbb

output:

ccbba

result:

wrong answer 1st lines differ - expected: 'ccbbaa', found: 'ccbba'