车辆安排

#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';
}

滑动窗口

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;
}