QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#569738 | #6618. Encoded Strings II | lmf_up | WA | 0ms | 3808kb | C++20 | 3.7kb | 2024-09-17 09:56:29 | 2024-09-17 09:56:30 |
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];
if(l==n)continue;
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] - sum[l - 1][i] , r + 1, y});
}
}
if(qq.empty())break;
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();
}
}
/*
37
brjnepdaqisnqfipjdodrbetlcslhaeilhnad
41
qdkeehrsjaarcecnimitcbtqpohgcnbonhhlaslpq
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
input:
4 aacc
output:
bbaa
result:
ok single line: 'bbaa'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3608kb
input:
4 acac
output:
bb
result:
wrong answer 1st lines differ - expected: 'bba', found: 'bb'