QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608177 | #2428. Comma Sprinkler | LJY_ljy | AC ✓ | 343ms | 224960kb | C++11 | 2.6kb | 2024-10-03 19:22:43 | 2024-10-03 19:22:44 |
Judging History
answer
//Trie树(字典树)练习
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int MAXN = 1000010;
char str[MAXN], Ans[MAXN];
int exist[MAXN], End[MAXN], len, Bound[MAXN];
int eid, cnt, nex[MAXN][30], Type[MAXN], type[MAXN], Eid;
set<int> G[MAXN][2];
bool E[MAXN][2];
// 空格 0, 句号 1,逗号 2
void dfs(int k, int t) {
//cout << k << " " << t << endl;
for (auto y: G[k][t]) {
if (!E[y][1 - t]) {
E[y][1 - t] = true;
dfs(y, 1 - t);
}
}
}
int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
for (int i = 1; i < MAXN; i++) exist[i] = -1;
while (scanf("%s", str + 1) != EOF) {
int n = strlen(str + 1), m;
cnt++;
if ('a' <= str[n] && str[n] <= 'z') m = n;
else m = n - 1;
Type[cnt] = (Type[cnt - 1] % 3) * 3;
if ('.' == str[n]) Type[cnt] ++;
if (',' == str[n]) Type[cnt] += 2;
for (int i = len + 1; i <= len + m; i++)
Ans[i] = str[i - len];
len = len + m;
Bound[cnt] = len;
int p = 0;
for (int i = 1; i <= m; i++) {
int c = str[i] - 'a';
if (!nex[p][c]) nex[p][c] = ++eid;
p = nex[p][c];
}
if (exist[p] == -1) {
type[p] = ++Eid;
//printf("%d %s\n", Eid, str + 1);
}
if (exist[p] == -1)
exist[p] = 0;
if (Type[cnt] % 3 == 2 && exist[p] % 3 == 0)
exist[p] += 2;
if (Type[cnt] / 3 == 2 && exist[p] / 3 == 0)
exist[p] += 6;
End[cnt] = p;
}
for (int i = 1; i <= cnt; i++) {
if (Type[i + 1] / 3 != 1) {
//cout << "Yes! " << type[End[i]] << " " << type[End[i + 1]] << endl;
G[type[End[i]]][0].insert(type[End[i + 1]]); // ..., -> ,...
}
if (Type[i - 1] % 3 != 1 && !E[type[End[i - 1]]][1]) {
//cout << "Yes2! " << type[End[i]] << " " << type[End[i - 1]] << endl;
G[type[End[i]]][1].insert(type[End[i - 1]]); // ,... -> ...,
}
}
for (int i = 1; i <= Eid; i++) E[i][0] = E[i][1] = false;
for (int i = 1; i <= cnt; i++) {
if (exist[End[i]] % 3 == 2 && !E[type[End[i]]][0]) {
E[type[End[i]]][0] = true;
dfs(type[End[i]], 0);
}
if (exist[End[i]] / 3 == 2 && !E[type[End[i]]][1]) {
E[type[End[i]]][1] = true;
dfs(type[End[i]], 1);
}
}
// for (int i = 1; i <= Eid; i++)
// cout << E[i][0] << " " << E[i][1] << endl;
for (int i = 1; i <= cnt; i++) {
for (int j = Bound[i - 1] + 1; j <= Bound[i]; j++)
printf("%c", Ans[j]);
if (Type[i] % 3 != 1 && (E[type[End[i]]][0] || E[type[End[i + 1]]][1])) printf(",");
if (Type[i] % 3 == 1) printf(".");
printf(" ");
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 15ms
memory: 101600kb
Test #2:
score: 0
Accepted
time: 19ms
memory: 101828kb
Test #3:
score: 0
Accepted
time: 16ms
memory: 101712kb
Test #4:
score: 0
Accepted
time: 15ms
memory: 101500kb
Test #5:
score: 0
Accepted
time: 15ms
memory: 102252kb
Test #6:
score: 0
Accepted
time: 68ms
memory: 109700kb
Test #7:
score: 0
Accepted
time: 74ms
memory: 137224kb
Test #8:
score: 0
Accepted
time: 67ms
memory: 138712kb
Test #9:
score: 0
Accepted
time: 16ms
memory: 106200kb
Test #10:
score: 0
Accepted
time: 11ms
memory: 104264kb
Test #11:
score: 0
Accepted
time: 11ms
memory: 104248kb
Test #12:
score: 0
Accepted
time: 12ms
memory: 106244kb
Test #13:
score: 0
Accepted
time: 26ms
memory: 106300kb
Test #14:
score: 0
Accepted
time: 8ms
memory: 104304kb
Test #15:
score: 0
Accepted
time: 16ms
memory: 106348kb
Test #16:
score: 0
Accepted
time: 186ms
memory: 123396kb
Test #17:
score: 0
Accepted
time: 343ms
memory: 138484kb
Test #18:
score: 0
Accepted
time: 258ms
memory: 138976kb
Test #19:
score: 0
Accepted
time: 15ms
memory: 106248kb
Test #20:
score: 0
Accepted
time: 202ms
memory: 149960kb
Test #21:
score: 0
Accepted
time: 129ms
memory: 170776kb
Test #22:
score: 0
Accepted
time: 107ms
memory: 174208kb
Test #23:
score: 0
Accepted
time: 59ms
memory: 220828kb
Test #24:
score: 0
Accepted
time: 168ms
memory: 144808kb
Test #25:
score: 0
Accepted
time: 135ms
memory: 146344kb
Test #26:
score: 0
Accepted
time: 117ms
memory: 138652kb
Test #27:
score: 0
Accepted
time: 69ms
memory: 122664kb
Test #28:
score: 0
Accepted
time: 139ms
memory: 144120kb
Test #29:
score: 0
Accepted
time: 52ms
memory: 223640kb
Test #30:
score: 0
Accepted
time: 11ms
memory: 106308kb
Test #31:
score: 0
Accepted
time: 31ms
memory: 191856kb
Test #32:
score: 0
Accepted
time: 47ms
memory: 224500kb
Test #33:
score: 0
Accepted
time: 15ms
memory: 106312kb
Test #34:
score: 0
Accepted
time: 12ms
memory: 106228kb
Test #35:
score: 0
Accepted
time: 14ms
memory: 106192kb
Test #36:
score: 0
Accepted
time: 12ms
memory: 104220kb
Test #37:
score: 0
Accepted
time: 20ms
memory: 104200kb
Test #38:
score: 0
Accepted
time: 11ms
memory: 106248kb
Test #39:
score: 0
Accepted
time: 20ms
memory: 106268kb
Test #40:
score: 0
Accepted
time: 16ms
memory: 104208kb
Test #41:
score: 0
Accepted
time: 26ms
memory: 108680kb
Test #42:
score: 0
Accepted
time: 19ms
memory: 106608kb
Test #43:
score: 0
Accepted
time: 19ms
memory: 106644kb
Test #44:
score: 0
Accepted
time: 20ms
memory: 106660kb
Test #45:
score: 0
Accepted
time: 24ms
memory: 108672kb
Test #46:
score: 0
Accepted
time: 20ms
memory: 106736kb
Test #47:
score: 0
Accepted
time: 85ms
memory: 119624kb
Test #48:
score: 0
Accepted
time: 79ms
memory: 119756kb
Test #49:
score: 0
Accepted
time: 76ms
memory: 119704kb
Test #50:
score: 0
Accepted
time: 50ms
memory: 115028kb
Test #51:
score: 0
Accepted
time: 49ms
memory: 111520kb
Test #52:
score: 0
Accepted
time: 48ms
memory: 113300kb
Test #53:
score: 0
Accepted
time: 187ms
memory: 133608kb
Test #54:
score: 0
Accepted
time: 216ms
memory: 134616kb
Test #55:
score: 0
Accepted
time: 190ms
memory: 134016kb
Test #56:
score: 0
Accepted
time: 150ms
memory: 126640kb
Test #57:
score: 0
Accepted
time: 135ms
memory: 126928kb
Test #58:
score: 0
Accepted
time: 146ms
memory: 129484kb
Test #59:
score: 0
Accepted
time: 8ms
memory: 106256kb
Test #60:
score: 0
Accepted
time: 48ms
memory: 224960kb
Test #61:
score: 0
Accepted
time: 44ms
memory: 106372kb
Test #62:
score: 0
Accepted
time: 19ms
memory: 104208kb