于是在未来的某一天,小马智行在加州已经拥有了N辆自动驾驶车辆可以面向公众服务,这些车总共有26种颜色,颜色分别为小写字母a到z。现在已知在Pony的服务系统PonyPilot中,总共有M个乘客正在排队,其中每个乘客也有各自的车辆颜色偏好,颜色范围也是a到z。
现在运营小P突然有了一个奇怪的想法:小P想知道总共有多少个位置连续的子队列,能够满足现有的所有车辆可以在同一时刻把子队列中的乘客同时接上乘客喜爱的颜色的车。注意每个车辆只能接一个乘客,且车的颜色要恰好是乘客喜欢的颜色。
第一行输入两个数字N,M。N代表车辆数,M代表乘客人数。
第二行输入一个字符串A,长度为N,表示每辆车的颜色。
第三行输入一个字符串B,长度为M,表示当前排队的乘客分别喜欢的车的颜色。
其中,1<=N<=1000000, 1<=M<=1000000。
输出一个数,即总共满足要求的子队列数。
4 6 pony pponyy
12
满足的子队列分别为([]内为子队列对应的下标区间):
p, [0, 0]
p, [1, 1]
o, [2, 2]
po, [1, 2]
n, [3, 3]
on, [2, 3]
pon, [1, 3]
y, [4, 4]
ny, [3, 4]
ony, [2, 4]
pony, [1, 4]
y, [5, 5]
2 2 ab ba
3
满足的子队列分别为([]内为子队列对应的下标区间):
b, [0, 0]
ba, [0, 1]
a, [1, 1]
//滑动窗口 + Cascading import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String[] temp = sc.nextLine().split(" "); int numC = Integer.parseInt(temp[0]); int numP = Integer.parseInt(temp[1]); String cars = sc.nextLine(); String people = sc.nextLine(); int left = 0; int right = 0; int[] tableC = new int[26]; for(int i = 0; i<numC; i++){ tableC[cars.charAt(i)-'a']++; } int[] tableP = new int[26]; long res = 0; while(right<numP){ int index = people.charAt(right)-'a'; tableP[index]++; if(tableP[index]<=tableC[index]){ res+=right-left+1; } else{ while(left<=right&&tableP[index]>tableC[index]){ tableP[people.charAt(left)-'a']--; left++; } res+= right-left+1; } right++; } System.out.println(res); } }
#include<bits/stdc++.h> using namespace std; #define int long long int n,m; string s,t; int A[26]; bool B[26]; signed main(){ cin >> n >> m; cin >> s >> t; for(auto c: s){ A[c-'a'] += 1; B[c-'a'] = 1; } int j = 0; int ans = 0; for(int i = 0; i < t.size();){ j = max(i,j); while(j < t.size()&&A[t[j]-'a']){ A[t[j]-'a']--; j ++; } //cout << j << ' ' << i << '\n'; ans += (j - i); if(B[t[i] - 'a']){ A[t[i]-'a']++; } i++; } cout << ans << '\n'; }
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int n,m; int Car[30],Peo[30]; char C[1000010],P[1000010]; bool Check() { for(int i=0;i<26;i++) { if(Car[i]<Peo[i]) { return false; } } return true; } int main() { scanf("%d%d",&n,&m); scanf("%s%s",C,P); int Cs=strlen(C),Ps=strlen(P); for(int i=0;i<Cs;i++) { ++Car[C[i]-'a']; } for(int i=0;i<Ps;i++) { P[i]-='a'; } int lp=0,rp=0; long long ans=0; ++Peo[P[0]]; while(lp<Ps&&rp<Ps) { if(Check()) { ans+=rp-lp+1;//排序组合的要点 ++rp; ++Peo[P[rp]]; } else { --Peo[P[lp]]; ++lp; if(lp>rp) { ++rp; ++Peo[P[rp]]; } } } printf("%lld",ans); return 0; }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]); String a = br.readLine(); String b = br.readLine(); int[] have = new int[26]; int[] need = new int[26]; for(char c: a.toCharArray()) { have[c - 'a']++; } long res = 0; for(int l = 0, r = 0; r < m; r++) { int t = b.charAt(r) - 'a'; need[t]++; while(l <= r && !contains(need, have)) { need[b.charAt(l++) - 'a']--; // 当前窗口满足不了就收缩左边界 } res += r - l + 1; } System.out.println(res); } public static boolean contains(int[] need, int[] have) { for(int i = 0; i < 26; ++i) { if(need[i] > have[i]) { return false; } } return true; } }
#include<bits/stdc++.h> using namespace std; vector<int> sub(vector<int> &a,vector<int> &b){ vector<int> res(26); for(int i = 0;i<26;i++) res[i] = a[i] - b[i]; return res; } int Cnt(vector<int> &a){ int res = 0; for(auto x:a) res += x; return res; } int main(){ vector<int> c(26,0); int N,M; cin>>N>>M; char cc; for(int i = 0;i<N; i++){ cin>>cc; c[cc-'a']++; } vector<vector<int>> cnt;//每个位置每种车喜欢的乘客数 vector<vector<int>> ind(26);//记录每种字符索引 vector<int> tmp(26,0); vector<int> Zero(26,0); vector<int> curr(26,0); long long ans = 0; for(int i = 0; i < M; i++){ cin>>cc; int cur = cc - 'a'; tmp[cur]++; cnt.push_back(tmp); curr[cur]++; if(curr[cur] > c[cur]){ if(c[cur] == 0) curr = Zero; else { int s = ind[cur].size(); curr = sub(cnt[i],cnt[ind[cur][s-c[cur]]]); } } ind[cur].push_back(i); ans += Cnt(curr); } cout<<ans; return 0; }
//*****通过40%******超时****** #include <iostream> #include <unordered_map> #include <string> #include <string.h> using namespace std; int main(){ unordered_map<char, int> map; for (int i=0;i<26;i++) map['a'+i] = 0; int n,m; cin>>n>>m; //n:车辆数, m:乘客人数 string str_car, str_pas; cin>>str_car; cin>>str_pas; int result = 0; for(char i:str_car) map[i]++; unordered_map<char, int> map_copy = map; for(int i=0;i<m;i++){ map_copy = map; for(int j=0;j<n;j++){ if(--map_copy[str_pas[i+j]] < 0) break; result++; }//for car }//for passager cout<<result; return 0; }
//******通过100%******* //int->long long //暴搜+跳过某些情况 #include <iostream> #include <unordered_map> #include <string> #include <string.h> using namespace std; int main(){ unordered_map<char, int> map; for (int i=0;i<26;i++) map['a'+i] = 0; int n,m; cin>>n>>m; //n:车辆数, m:乘客人数 string str_car, str_pas; cin>>str_car; cin>>str_pas; long long result = 0; for(char i:str_car) map[i]++; unordered_map<char, int> map_copy = map; int temp=0; for(int i=0;i<m;i++){ // map_copy = map; for(int j=temp;j<n;j++){ map_copy[str_pas[i+j]]--; if(map_copy[str_pas[i+j]] < 0 && j-1>=0) {temp = j-1; map_copy[str_pas[i]]++ ; map_copy[str_pas[i+j]]++;result+=j-1; break;} // else if(map_copy[str_pas[i+j]] < 0 && j-1>=0) {temp = 0; map_copy[str_pas[i]]++ ; break;} else if(map_copy[str_pas[i+j]] < 0 && j >=0) {temp = 0; map_copy=map ; break;} else if(j==n-1) {temp=j;map_copy[str_pas[i]]++;result+=j;} result++; //cout<<i<<"to"<<i+j<<":"<<result<<endl; }//for car }//for passager cout<<result; return 0; }