QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #857825 | #9921. Yelkrab | Xia_uwu | WA | 1ms | 3584kb | C++20 | 8.2kb | 2025-01-16 03:57:03 | 2025-01-16 03:57:11 |
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;
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);
}
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，那么可以新增
//反之则只是替换
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;
}
//std::cout << "{" << j << "->" << g[j] << "}\n";
if (exist[p] / j != j) {
int j_ = exist[p] / j;
if (val[j_].size() < time / j_) {//新增
ans ^= g[j_] * j_;
val[j_].insert(i + 1);
g[j_] += i + 1;
ans ^= g[j_] * j_;
//std::cout << "!!";
} 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_;
//std::cout << "??";
}
//std::cout << "{{" << j_ << "->" << g[j_] << "}}\n";
}
}
}
}
// 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: 1ms
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: 1ms
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 65 91 81 147 181 190 136 155 3 1 22 21 74 73 76 90 108 98 95 146 32 38 39 47 54 170 166 161 204 255 3 37 64 191 190 231 247 230 282 40 53 62 63 12 67 68 70 161 187 177 200 195 197 10 69 72 88 140 12 22 26 57 75 86 113 145 155 153 50
result:
wrong answer 2nd numbers differ - expected: '35', found: '69'