QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#569733 | #6618. Encoded Strings II | lmf_up | RE | 0ms | 3828kb | C++20 | 3.6kb | 2024-09-17 09:46:16 | 2024-09-17 09:46:17 |
Judging History
answer
#include<bits/stdc++.h>
#define lmf_up signed main()
#define lmf_up_up std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
const int TIAO = 1;
//const int mod = 998244353;
const int maxn = 3e5 + 10;
//#define int long long
inline void read(int &x)
{
x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')ch = getchar();
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
}
const int INF = 1e9;
void solve()
{
int n;
std::cin >> n;
std::string s;
std::cin >> s;
int m = 0;
{
std::vector<char> vis(20);
for (int i = 0; i < n; i++)
vis[s[i] - 'a']++;
for (int i = 0; i < 20; i++)
{
if (vis[i])
{
vis[i] = m + 'a';
m++;
}
}
for (int i = 0; i < n; i++)
s[i] = vis[s[i] - 'a'];
}
s = " " + s;
std::vector<int> ans(m);
int len = 1 << m;
std::vector<int> vv(len, n + 1);
std::vector<int> lst(len, 0);
{
int res = 0;
for (int i = n; i >= 1; i--)
{
int v = s[i] - 'a';
res |= 1 << v;
lst[res] = std::max(lst[res], i);
}
for (int i = 0; i < len; i++)
{
for (int j = (i - 1) & i; j; j = (j - 1) & i)
{
lst[j] = std::max(lst[j], lst[i]);
}
}
lst[0] = n + 1;
}
std::vector<int> q;
std::vector<std::vector<int>> sum(n + 2, std::vector<int>(m));
std::vector<std::vector<int>> pre(n + 2, std::vector<int>(m));
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1];
sum[i][s[i] - 'a']++;
}
sum[n+1]=sum[n];
for (int i = 1; i <= n ; i++)
{
pre[i] = pre[i - 1];
pre[i][s[i] - 'a'] = i;
}
pre[n+1]=pre[n];
q.push_back(0);
vv[0] = 1;
const int all = len - 1;
int ans_cnt = 0;
while (!q.empty())
{
std::vector<int> nq;
std::vector<std::array<int, 3>> qq;
for (auto x: q)
{
int l = vv[x];
for (int i = 0; i < m; i++)
{
if ((x >> i) & 1)continue;
int y = x | (1 << i);
int z = all ^ y;
int loc = lst[z];
if (loc < l)
continue;
int r = pre[loc][i];
if (r < l)
continue;
qq.push_back({sum[r][i] - (l ? sum[l - 1][i] : 0), r + 1, y});
}
}
std::sort(qq.begin(), qq.end(), std::greater());
for (int i = 0; i < qq.size(); i++)
{
if (qq[i][0] == qq[0][0])
{
vv[qq[i][2]] = std::min(vv[qq[i][2]], qq[i][1]);
nq.push_back(qq[i][2]);
}
else break;
}
ans[ans_cnt] = qq[0][0];
ans_cnt++;
if (ans_cnt == m)break;
if(nq.empty())break;
std::sort(nq.begin(), nq.end());
nq.erase(std::unique(nq.begin(), nq.end()), nq.end());
q = nq;
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < ans[i]; j++)
std::cout << (char) ('a' +m- i-1);
}
}
lmf_up
{
lmf_up_up
// if(TIAO)
// freopen("P4180_12.in","r",stdin);
// std::cout << std::fixed << std::setprecision(4);
int T = 1;
for (int i = 1; i <= T; i++)
{
solve();
}
}
/*
4
1 3 1 7
8
3 3 8 4 5 3 8 5
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
4 acac
output:
bba
result:
ok single line: 'bba'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1 t
output:
a
result:
ok single line: 'a'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
12 bcabcabcbcbb
output:
ccbbaa
result:
ok single line: 'ccbbaa'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok single line: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1000 ggkkkggggggkgggkgkgkkkkkggkkkgggkgkgggkkgkkgkgkgkgkgggkgkkkkgkgkkgkggkgggkgggkgkkgggggkkgkgkkkkgkkkkkkgkkggkkkkggkkkgkgggkggkkgkkgkgggkkggggkkggggkggkkggkgkgkgkkkgkkgkgkkgkkgkgkggkgggkgkkkgkkkgkkggkkggkkgkgkgkkkkkgkkggkgggkkkkgggkggkgggkkkgkkkkggggkkggkkkkgkkggkkkkkkgkgggkkkkkgggggggkgggkkkggkg...
output:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
result:
ok single line: 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaa'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1000 edbbbbedddbeebedeedbddebddddbedbbdddeddeeddeebdedbbbdedddeeddbdddbbebbbdbeddbbbbbdeedebdddbbbebebbbdebebbeebbeeddddebdbdedbedddeebedebbddbededbdeebbbbbdbebddbebdbddebbddddbdeebbbddddbedddbedbeebdeeebdedbdededdbdebbedbbbeedbbedebddebbeebddebbebbdebeebddbdeddbdebdebebbdbebdddedbbdbedbbdbebbbddddd...
output:
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...
result:
ok single line: 'cccccccccccccccccccccccccccccc...ccccccccccccccccccccccccccbbbaa'
Test #8:
score: -100
Runtime Error
input:
1000 hhqjhgqqjhqhqhgggqhgqghhjjgjjqqqhhjhhjqqjqqjqqhghghjhqhghhqhgjgjhqhjjjqjqgjgjgqhqqgjgqghgqjjhqjjgqghjqjhqjhghhghgqjqjhggjjhhjjqhqgqhjjhqqjqjghjjhjhqghqggjqjqjghjqhqjqgjqqjjqjjhjjqghqjjhhjhghhjggqqjjqgjqgqjhqhjqhjqqgjqhghghhjqqhhhjhjjgjjgjqgjqqqggjggqhqgjhqhqqgggqqhqqqjhqgjghhhqgghqqjgjhjqjhhqgh...