Zerojudge e288
題敘
https://zerojudge.tw/ShowProblem?problemid=e288
定義兩字串互為CP必須符合
- 無任何字母相同
- 須包含所有範圍內的字母
給 $n$ 個字串，求CP對數總和
想法
暴力搜尋，複雜度 $O(m^2)$，只有25分
我們可以嘗試把一個字串所包含的字元以bit表示
而全部有 A~Z a~i 共38個字母，可以分別以1bit表示各個字母
而搜尋每次只需要利用xor的特性，很快就可以獲得差集
但是在搜尋的部分如果用 $O(m^2)$ 還是一樣差
嘗試將搜尋的內容塞入map中，使得查詢時間複雜度降至 $O(logm)$
為了方便塞入map，可以用long long，具有64個bit可以充分運用
補充
其實也不一定需要用到map
我們需要實現的只有能快速搜尋
可以先排序($O(logn)$)再二分搜($O(logn)$)
也可以達到map相同的效果
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,m,ans=0;
long long mask,tmp;
string s;
map<long long, int> mp;
int char_to_num(char c){
if(c>='A' && c<='Z'){
return c-'A';
}
else{
return 26+c-'a';
}
}
int main(){
IOS
cin>>n>>m;
for(int i=0 ; i<n ; i++){
mask |= (1LL << i);
}
for(int i=0 ; i<m ; i++){
cin>>s;
tmp=0;
for(int j=0 ; j<s.size() ; j++){
tmp |= (1LL<<(char_to_num(s[j])));
}
if(mp.count(tmp ^ mask)) ans+= mp[tmp ^ mask];
if(mp.count(tmp)) mp[tmp]++;
else mp[tmp]=1;
}
cout<<ans<<'\n';
return 0;
}
|
複雜度
輸入時間複雜度為 $O(m)$
查詢時間複雜度約為 $O(logm)$
總時間複雜度 $O(m+logm)$