QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644982 | #9466. Domains | Afterlife# | AC ✓ | 191ms | 186948kb | C++20 | 4.5kb | 2024-10-16 16:19:13 | 2024-10-16 16:19:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n , q;
bool is_domain(char c) {
return c == '-' || c == '*' || c == '#' || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9') || c == '.' ;
}
bool is_alpha(char c) {
return 'a' <= c && c <= 'z';
}
bool is_vpn(char c) {
return c == '-' || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9');
}
int to_int(char c) {
if('a' <= c && c <= 'z') return c- 'a';
if('0' <= c && c <= '9') return c - '0' + 26 ;
if(c == '-') return 36;
if(c == '*') return 37;
if(c == '#') return 38;
if(c == '.') return 39;
assert(0);
}
const int N = 2e6 + 5;
struct trie {
int ch[40];
int cnt[3]; //// *count , #count , blankcount
int cur[3];
}T[N];
int rt , cc;
void cls(int u) {
memset(T[u].cnt , 0 , sizeof(T[u].cnt)) ;
memset(T[u].cur , 0 , sizeof(T[u].cur));
memset(T[u].ch,0,sizeof(T[u]));
}
bool ins(string s) {
int u = rt;
reverse(s.begin() , s.end());
int tc ;
if(s.back() == '*') tc = 0 , s.pop_back();
else if(s.back() == '#') tc = 1 , s.pop_back();
else tc = 2;
for(int i = 0;i < s.size();i++) {
int t = to_int(s[i]) ;
if(!T[u].ch[t]) {
T[u].ch[t] = ++cc;
cls(cc);
}
if(T[u].cur[0]) return 0;
if(tc == 1 && T[u].cur[1]) return 0;
u = T[u].ch[t];
}
if(T[u].cur[0]) return 0;
if(tc == 1 && T[u].cur[1]) return 0;
if(tc == 0) {
if(T[u].cnt[0] || T[u].cnt[1] || T[u].cnt[2]) return 0;
}
else if(tc == 1) {
if(T[u].cnt[1]) return 0;
}
else {
if(T[u].cur[2]) return 0;
}
u = rt;
for(int i = 0;i < s.size();i++) {
int t = to_int(s[i]) ;
T[u].cnt[tc]++ ;
u = T[u].ch[t];
}
T[u].cnt[tc]++ ;T[u].cur[tc]++ ;
// printf("Ad %d %d\n",u,tc);
return 1;
}
int calc(string t) {
reverse(t.begin() , t.end()) ;
int tc;
if(t.back() == '*') tc = 0 , t.pop_back() ;
else tc = 2;
int ans = 0 , ans1 = 0;
int u = rt;
for(int i = 0;i < t.size();i++) {
ans += T[u].cur[0] ;
ans1 += T[u].cur[1] ;
// printf("tu %d : %d\n",u,T[u].cur[0]);
if(T[u].cur[0]) ans1 = 0;
int tt = to_int(t[i]) ;
if(T[u].ch[tt] == 0) {
u = cc + 1 ;
cls(cc + 1) ;
break ;
}
u = T[u].ch[tt];
}
ans += T[u].cur[0];
ans1 += T[u].cur[1] ;
if(T[u].cur[0]) ans1 = 0;
if(tc == 2) {
ans += T[u].cur[2] ;
// printf("Tcur %d : %d\n",T[u].cur[0] , u);
if(ans) return ans;
return ans1;
}
else {
ans += (T[u].cnt[0] - T[u].cur[0]) ;
ans += T[u].cnt[2] ;
ans1 += (T[u].cnt[1] - T[u].cur[1]) ;
return ans + ans1;
}
// if(ans ) return ans;
// return ans1;
}
void solv() {
int cnt = 0; rt = 0;cc = 0;
cls(0);
for(int i = 1;i <= n;i++) {
string a,b;cin >> a >> b;
bool ff = 1;
for(auto x : a) {
if(!is_domain(x)) {ff = 0 ;break ;}
}
if(a[0] == '.' || a.back() == '.') ff =0;
for(int i = 0;i + 1 < a.size();i++) {
if(a[i] == '.' && a[i + 1] == '.') ff = 0;
}
if((a[0] == '#' || a[0] == '*') && (a.size() > 1 && a[1] != '.')) ff = 0;
for(int i = 1;i < a.size();i++) {
if(a[i] == '#' || a[i] == '*') ff = 0;
}
for(int i = 0;i < a.size();i++) {
if(a[i] == '-') {
if(i == 0 || i == a.size() - 1) ff = 0;
else if(!is_alpha(a[i - 1]) || !is_alpha(a[i + 1])) ff = 0;
}
}
for(auto x : b) {
if(!is_vpn(x)) ff = 0;
}
if(!is_alpha(b[0])) ff = 0;
for(int i = 0;i < b.size();i++) {
if(b[i] == '-') {
if(i == 0 || i == b.size() - 1) ff = 0;
else if(!is_alpha(b[i - 1]) || !is_alpha(b[i + 1])) ff = 0;
}
}
if(!ff) {
// cout << "bad1 " << i << '\n';
++cnt ; continue ;
}
if(!ins(a)) {
// cout << "bad2 " << i << '\n';
++cnt ; continue ;
}
}
cout << cnt << '\n' ;
cin >> q;
while(q--) {
string t ; cin >> t;
cout << calc(t) << '\n';
}
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
while(cin >> n) solv() ;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
11 a.c a.c poj.org vpn-china www.pku.edu.cn vpn-pku1 mail.pku.edu.cn vpn-pku1 *.test.pku.edu.cn vpn-pku2 *.test.pku.edu.cn vpn-pku2 *.a.test.pku.edu.cn vpn-pku2 *.test2.pku.edu.cn vpn-pku2 *.pku.edu.cn vpn-pku2 #.pku.edu.cn vpn-pku0 #.www.pku.edu.cn vpn-pku0 5 a.c mail.pku.edu.cn *.test.pku.edu.cn *...
output:
5 0 1 1 5 6
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 191ms
memory: 186948kb
input:
1 nwlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmcoqhnwnkuewhsqmgbbuqcljjivswmdkqtbxixmvtrrbljptnsnfwzqfjmafadrrwsofsbcnuvqhffbsaqxwpqcacehchzvfrkmlnozjkpqpxrjxkitzyxacbhhkicqcoendtomfgdwdwfcgpxiqvkuytdlcgdewhtaciohordtqkvwcsgspqoqmsboaguwnnyqxnzlgdgwpbtrwblnsadeu...
output:
0 0 20883 51 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 4 1 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1...
result:
ok 156302 lines