QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #857830 | #9921. Yelkrab | Xia_uwu | WA | 0ms | 3584kb | C++20 | 8.9kb | 2025-01-16 04:26:14 | 2025-01-16 04:26:16 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
/*
sum s = 1e6
n = 5e5
如何判断分支？
1e6 * 26 = 2e7，不会T
直接枚举26次
*/
struct trie {
std::vector<std::array<int, 26>> next;
std::vector<int> exist;
std::vector<int> g;
std::vector<std::multiset<int>> val, res_val;//保证val + res_val的size小于等于 g.size() / i
int cnt = 0;
int time = 0;
i64 ans = 0;
trie(int size, int n) {//size大小应满足 ：n <= sum(|s|)
next.resize(size + 1);
exist.resize(size + 1);
g.resize(n + 1);
val.resize(n + 1);
res_val.resize(n + 1);
}
void insert(const std::string& s) {
time++;
int p = 0;
for (int i = 0; i < s.size(); i++) {//dep实际上就是i + 1吧
int c = s[i] - 'a';
if (!next[p][c]) next[p][c] = ++cnt;
p = next[p][c];
exist[p]++;
//std::cout << "^&*(^&*(^&*()))";
for (int j = 1; j * j <= exist[p]; j++) {
if (!(exist[p] % j)) {
// dep = (i + 1)
//判断要新增，还是只是替换
//和添加次数有关应该
//如果val[j].size() < time / j，那么可以新增
//反之则只是替换
auto work = [&](int j) {
res_val[j].insert(i + 1);
if (val[j].size() < time / j) {//新增，其实新增也能新增之前预存的贡献，所以其实要开两个multiset
//保证val + res_val的size小于等于 g.size() / i
ans ^= g[j] * j;
int get = *res_val[j].rbegin();
res_val[j].extract(get);
g[j] += get;
val[j].insert(get);
ans ^= g[j] * j;
} else {//只是替换最小的
ans ^= g[j] * j;
int get = *res_val[j].rbegin();
res_val[j].extract(get);
g[j] += get;
val[j].insert(get);
get = *val[j].begin();
g[j] -= get;
res_val[j].insert(get);
val[j].extract(get);
ans ^= g[j] * j;
}
while (val[j].size() && res_val[j].size() && *val[j].begin() < *res_val[j].rbegin()) {
int a = *val[j].begin();
int b = *res_val[j].rbegin();
val[j].extract(a);
res_val[j].extract(b);
val[j].insert(b);
res_val[j].insert(a);
}
while (val[j].size() + res_val[j].size() > ((int)g.size() - 1) / j) {
res_val[j].extract(*res_val[j].begin());
}
};
work(j);
//然后保证俩set元素之和不大于实际容许体积
//std::cout << "{" << j << "->" << g[j] << "}\n";
if (exist[p] / j != j) {
int j_ = exist[p] / j;
work(j_);
}
}
}
}
// exist[p]++;
// for (int j = 1; j * j <= exist[p]; j++) {
// if (!(exist[p] % j)) {
// // dep = (i + 1)
// //判断要新增，还是只是替换
// //和添加次数有关应该
// //如果val[j].size() < time / j，那么可以新增
// //反之则只是替换
// if (val[j].size() < time / j) {//新增
// ans ^= g[j] * j;
// val[j].insert(s.size());
// g[j] += s.size();
// ans ^= g[j] * j;
// } else {//只是替换最小的
// ans ^= g[j] * j;
// g[j] -= *val[j].begin();
// val[j].extract(*val[j].begin());
// val[j].insert(s.size());
// g[j] += s.size();
// ans ^= g[j] * j;
// }
// if (exist[p] / j != j) {
// int j_ = exist[p] / j;
// if (val[j_].size() < time / j_) {//新增
// ans ^= g[j_] * j_;
// val[j_].insert(s.size());
// g[j_] += s.size();
// ans ^= g[j_] * j_;
// } else {//只是替换最小的
// ans ^= g[j_] * j_;
// g[j_] -= *val[j_].begin();
// val[j_].extract(*val[j_].begin());
// val[j_].insert(s.size());
// g[j_] += s.size();
// ans ^= g[j_] * j_;
// }
// }
// }
// }
}
std::set<int> dfs_val;//存权值
int dfs_g;
void dfs(int now, int dep, int k) {// [可选] 先序遍历所有字符串（初始参数：0, 0）
// if (exist[now]) {
// std::cout << t.substr(0, dep) << "\n";// [editable] 该字符串即为一次遍历结果，这里修改对其进行的操作
// }
/*
if (!(exist[p] % j)) {
// dep = (i + 1)
//判断要新增，还是只是替换
//和添加次数有关应该
//如果val[j].size() < time / j，那么可以新增
//反之则只是替换
if (val[j].size() < time / j) {//新增
ans ^= g[j] * j;
val[j].insert(i + 1);
g[j] += i + 1;
ans ^= g[j] * j;
} else {//只是替换最小的
ans ^= g[j] * j;
g[j] -= *val[j].begin();
val[j].extract(*val[j].begin());
val[j].insert(i + 1);
g[j] += i + 1;
ans ^= g[j] * j;
}
*/
for (int j = 1; j <= exist[now]; j++) {
if (!(exist[now] % j)) {
if (dfs_val.size() < time / j) {
dfs_val.insert(dep);
dfs_g += dep;
} else {
dfs_g -= *dfs_val.begin();
dfs_val.extract(*dfs_val.begin());
dfs_val.insert(dep);
dfs_g += dep;
}
}
}
for (int i = 0; i < 26; i++) {
if (next[now][i]) {
dfs(next[now][i], dep + 1, k);
//t[dep] = 'a' + i;
//sum += dfs(next[now][i], dep + 1, k) + exist[next[now][i]] / k * (dep + 1);
}
}
}
i64 f(int k) {
dfs_val.clear();
dfs_g = 0;
dfs(0, 0, k);
return dfs_g;
}
};
/*
3 4 12 3 2
15
*/
void solve0() {
int n;
std::cin >> n;
int len = 0;
std::vector<std::string> a(n);
for (auto &s : a) {
std::cin >> s;
len += s.size();
}
trie tr(len, n);
//如何求f(i, j)
for (int i = 1; i <= n; i++) {
tr.insert(a[i - 1]);
i64 ans = 0;
std::cout << "[" << i << ": ";
for (int j = 1; j <= i; j++) {
std::cout << tr.f(j) << " ";
ans ^= tr.f(j) * j;
}
std::cout << "]\n";
std::cout << ans << " ";
}
std::cout << "\n";
}
/*
2 4 6 10 11
5
*/
void solve() {
int n;
std::cin >> n;
int len = 0;
std::vector<std::string> a(n);
for (auto &s : a) {
std::cin >> s;
len += s.size();
}
trie tr(len, n);
for (int i = 1; i <= n; i++) {
tr.insert(a[i - 1]);
// std::cout << "[" << i << ": ";
// for (int j = 1; j <= i; j++) {
// std::cout << tr.g[j] << " ";
// }
// std::cout << "]\n";
std::cout << tr.ans << " ";
}
std::cout << "\n";
}
signed main() {
std::cin.tie(0) -> sync_with_stdio(false);
int t = 1;
std::cin >> t;
while (t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 5 aa ab ab ac d 1 aaaaa
output:
2 6 1 9 8 5
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
input:
10 10 bba bbaaaabbbaaabaabbbaaaaaababaababbb b baaabbaab babbb bbbbbaaaaababbabbabbb bbaaaabbabb b aaaaabab abbbabbabab 10 abb ab bbaaaba bbabbabba bbbabbbababaaaab b aaaa babababbb ab a 2 aaaaabbaabbbbbababbbbbaabababbbaaababbbaaaaabbbaabaabababbaababbabbabbaababbbbbabbbabaaabbbabab abbaaaaaaaabbaa...
output:
3 69 102 143 168 189 240 207 309 276 3 1 22 21 74 93 88 98 127 107 95 191 32 59 95 122 150 166 200 235 283 267 3 37 64 191 227 281 312 376 407 40 77 114 158 12 67 97 131 163 201 219 255 277 289 10 69 100 136 168 12 19 38 57 75 86 120 147 148 154 50
result:
wrong answer 2nd numbers differ - expected: '35', found: '69'