QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783473#6618. Encoded Strings IILoxilanteWA 180ms192672kbC++201.9kb2024-11-26 10:04:242024-11-26 10:04:25

Judging History

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

  • [2024-11-26 10:04:25]
  • 评测
  • 测评结果:WA
  • 用时:180ms
  • 内存:192672kb
  • [2024-11-26 10:04:24]
  • 提交

answer

#define F_C
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; i++)
#define hrp(i, l, r) for(int i = l; i <= r; i++)
#define rev(i, r, l) for(int i = r; i >= l; i--)
#define int ll
using namespace std;
typedef long long ll;
template<typename tn = int> tn next(void) { tn k; cin>>k; return k; }
#ifndef LOCAL
#define D(...) 0
#endif
const int C = 20, U = 1200;
int dp[(1<<C)+U], maxap[(1<<C)+U][C], from[(1<<C)+U], pos[(1<<C)+U];
int sum[C+5][U], lst[C+5][U];
signed main(void)
{
    #ifdef LOCAL
//	freopen("C:\\Users\\Loxil\\Desktop\\IN.txt", "r", stdin);
//	freopen("C:\\Users\\Loxil\\Desktop\\OUT.txt", "w", stdout);
    #endif
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    string str;
    cin>>n>>str;
    str = '$'+str;

    hrp(i, 1, n) rep(j, 0, C) sum[j][i] = sum[j][i-1]+(j == str[i]-'a'), lst[j][i] = j == str[i]-'a' ? i : lst[j][i-1];

    rep(msk, 0, 1<<C)
    {
        int minn = n+1;
        rep(i, 0, 20) if (!((msk>>i)&1) && lst[i][n]) minn = min(minn, lst[i][n]);
        pos[msk] = minn-1;
    }

    rep(msk, 0, 1<<C)
    {
        int cnt1 = __builtin_popcount(msk); 
        rep(i, 0, 20) if (!(msk&(1<<i)))
        {
            int cntn = sum[i][pos[msk|(1<<i)]]-sum[i][dp[msk]];
            if (cntn > maxap[msk|(1<<i)][cnt1+1]) dp[msk|(1<<i)] = lst[i][pos[msk|(1<<i)]], maxap[msk|(1<<i)][cnt1+1] = cntn, from[msk|(1<<i)] = i;
            else if (cntn == maxap[msk|(1<<i)][cnt1+1]) dp[msk|(1<<i)] = min(dp[msk|(1<<i)], lst[i][pos[msk|(1<<i)]]);
        }
    }

    int resmsk = 0, ch = 'a';
    rep(i, 0, 20) if (sum[i][n]) resmsk |= 1<<i;

    string ans;
    while(resmsk)
    {
        int f = from[resmsk], cnt = maxap[resmsk][__builtin_popcount(resmsk)]; D(resmsk, cnt);
        rep(i, 0, cnt) ans += ch;
        resmsk ^= 1<<f;
        ch++;
    }

    reverse(ans.begin(), ans.end());
    cout<<ans<<endl;
    
    return 0;
}
/*

 */

详细

Test #1:

score: 100
Accepted
time: 152ms
memory: 192408kb

input:

4
aacc

output:

bbaa

result:

ok single line: 'bbaa'

Test #2:

score: 0
Accepted
time: 163ms
memory: 192200kb

input:

4
acac

output:

bba

result:

ok single line: 'bba'

Test #3:

score: 0
Accepted
time: 156ms
memory: 108236kb

input:

1
t

output:

a

result:

ok single line: 'a'

Test #4:

score: 0
Accepted
time: 180ms
memory: 192248kb

input:

12
bcabcabcbcbb

output:

ccbbaa

result:

ok single line: 'ccbbaa'

Test #5:

score: 0
Accepted
time: 156ms
memory: 192672kb

input:

1000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result:

ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'

Test #6:

score: 0
Accepted
time: 150ms
memory: 176052kb

input:

1000
ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

result:

ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'

Test #7:

score: -100
Wrong Answer
time: 160ms
memory: 192368kb

input:

1000
edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...

output:

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

result:

wrong answer 1st lines differ - expected: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa', found: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbaaa'