Zerojudge e289
題敘
https://zerojudge.tw/ShowProblem?problemid=e289
定義一個字串是美麗的為長度 $m$ 且有 $m$ 種不同顏色存在
給一個字串及長度 $m$ ，求美麗的字串個數
想法
題目中的輸入可到 $10^{150}$，所以選擇用字串儲存
可以先將字串 $0$ ~ $m-1$先塞入map，則後面每次只需
- 將 $s[i]$ 塞入map
- 檢查size是否為 $m$，若是就將答案加1
- 將頭去掉
補充
其實也不一定需要用到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
|
#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 m,n,ans=0,cnt=0;
string tmp[200005];
map<string, int> mp;
int main(){
IOS
mp.clear();
cin>>m>>n;
for(int i=0,head=0 ; i<n ; i++){
cin>>tmp[i];
if(i<m-1){
if(mp.count(tmp[i])) mp[tmp[i]]++;
else mp[tmp[i]]=1,cnt++;
}
else{
if(mp[tmp[i]]) mp[tmp[i]]++;
else mp[tmp[i]]=1,cnt++;
if(cnt == m) ans++;
if(mp[tmp[head]]-1) mp[tmp[head]]--;
else mp.erase(tmp[head]),cnt--;
head++;
}
}
cout<<ans<<'\n';
return 0;
}
|
複雜度
輸入時間複雜度為 $O(n)$
查詢時間複雜度約為 $O(logm)$
總時間複雜度 $O(n+logm)$