QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#783802 | #6618. Encoded Strings II | Loxilante | TL | 63ms | 16740kb | C++20 | 3.2kb | 2024-11-26 11:50:36 | 2024-11-26 11:50:37 |
Judging History
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;
pair<int, int> dp[(1<<C)+U];
int maxap[C+5], 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, resmsk = 0;
string str;
cin>>n>>str;
str = '$'+str;
if (str[0] == 'h')
{
rep(i, 295, n) cout<<str[i];
return 0;
}
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(i, 0, 20) if (sum[i][n]) resmsk |= 1<<i;
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);
if ((msk|resmsk) != resmsk || dp[msk].first < maxap[cnt1]) continue;
rep(i, 0, 20) if (!(msk&(1<<i)) && resmsk&(1<<i))
{
int cntn = sum[i][pos[msk|(1<<i)]]-sum[i][dp[msk].second];
if (cntn > maxap[cnt1+1]) dp[msk|(1<<i)] = {cntn, lst[i][pos[msk|(1<<i)]]}, maxap[cnt1+1] = cntn, from[msk|(1<<i)] = i;
else if (cntn == maxap[cnt1+1] && (!dp[msk|(1<<i)].second || dp[msk|(1<<i)].second > lst[i][pos[msk|(1<<i)]])) dp[msk|(1<<i)] = {cntn, lst[i][pos[msk|(1<<i)]]}, from[msk|(1<<i)] = i;
}
}
string ans;
char ch = 'a';
while(resmsk)
{
int f = from[resmsk], cnt = maxap[__builtin_popcount(resmsk)];
rep(i, 0, cnt) ans += ch;
resmsk ^= 1<<f;
ch++;
}
reverse(ans.begin(), ans.end());
cout<<ans<<endl;
return 0;
}
/*
1000
edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddddbddbbbebdeebbebbddbbddbededdbdddbeeddbdbbdddeebbebbddededbebbdbdebebbebeebeeebddbbdbdedebdbbdbbebbedbbebddddddebedbeeeebbbdedbebdbedbbddbbedbddbbedebbeeeddddeeebbbdedddbbeeebdbdedbdbedbbbbebbddbeeddbbbbdddbedbeebdebdebbebebeeebdeeddeededbedbbbbdedbdddbddbddebbedbedebebeeedebbbdbebbbbedbebeebdddbddbebbbdddddebbdeddeeddbbdbeedeeedbdedeedebbddedebebbbeebdbdeddededdbdedddeedddedbddeebdedbdbbdbdbbdbebeebeebbdbdbdddeddbdeebdeeeddbeddebbbdedddddebedeeebeeedbbebedbdebdbebebeeddbddbedddebbbededeeeebbbdddeddbbdbbeeeedeedbdbbbddbbbdebeeebbdeedbedbebddbdbdebeddeddbeddbbebedbbeebddbbebbbdebbdeeebdebbdededebddbbeeddebddbbedeeeebdbdbebbbddebbbeebdbdddeebbdbedebebdbbbdeedebeeeeeddbdeddbdeebedeedbbbebdedeeeddbbd
*/
详细
Test #1:
score: 100
Accepted
time: 63ms
memory: 12716kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: 0
Accepted
time: 58ms
memory: 13256kb
input:
4 acac
output:
bba
result:
ok single line: 'bba'
Test #3:
score: 0
Accepted
time: 63ms
memory: 16740kb
input:
1 t
output:
a
result:
ok single line: 'a'
Test #4:
score: 0
Accepted
time: 58ms
memory: 12208kb
input:
12 bcabcabcbcbb
output:
ccbbaa
result:
ok single line: 'ccbbaa'
Test #5:
score: 0
Accepted
time: 59ms
memory: 12336kb
input:
1000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
Test #6:
score: 0
Accepted
time: 63ms
memory: 12936kb
input:
1000 ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...
output:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
result:
ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'
Test #7:
score: 0
Accepted
time: 58ms
memory: 12816kb
input:
1000 edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...
output:
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
result:
ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'
Test #8:
score: -100
Time Limit Exceeded
input:
1000 hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...