阿里笔试3.27场（附两题代码和前三场代码链接）

/*
参考了讨论区大佬的思路，这道题实质上是求s1中能匹配s2的最长前缀，
剩下未匹配的字符只需要按照s2的顺序依次移动即可
时间复杂度：O(n)
*/

#include<iostream>
#include<string>
using namespace std;

//检查s1是否可以变为s2
bool check(string s1, string s2) {
    if(s1.length() != s2.length()) {
        return 0;
    }
    long long rec[26] = {0};
    long long i;
    for(i = 0; i < s1.length(); i++) {
        rec[s1[i] - 'a']++;
    }
    for(i = 0; i < s2.length(); i++) {
        rec[s2[i] - 'a']--;
        if(rec[s2[i] - 'a'] < 0) {
            return 0;
        }
    }
    return 1;
}

long long minchange(string s1, string s2) {
    if(check(s1,s2) == 0) {
        return -1;
    }
    long long i, cc = 0;
    for(i = 0; i < s1.length(); i++) {
        if(s1[i] == s2[cc]) {
            cc++;
        }
    }
    return s2.length() - cc;
}

int main() {
    string sori, star;
    cin>>sori;
    cin>>star;
    cout<<minchange(sori, star)<<endl;
    return 0;
}

#include<iostream>
#include<iomanip>
#include<vector>
#include<math.h>
using namespace std;

struct prs {
    int l;
    int r;
};

void range(vector<prs> &v, int &rangel, int &ranger) {
    int i;
    rangel = 2000;
    ranger = 2000;
    for(i = 0; i < v.size(); i++) {
        ranger = min(ranger, v[i].r);
    }
    
    i = 0;
    while(i < v.size()) {
        if(v[i].l > ranger) {
            v.erase(v.begin()+i, v.begin()+i+1);
        }
        else {
            rangel = min(rangel, v[i].l);
            i++;
        }
    }
    return;
}

vector<double> ps(vector<prs> &v, int rangel, int ranger) {
    vector<double> p;
    int i, j;
    double tmp = 1;
    
    vector<double> vlen;
    for(j = 0; j < v.size(); j++) {
        vlen.push_back(double(v[j].r - v[j].l + 1));
    }
    
    for(i = ranger; i >= rangel; i--) {
        for(j = 0; j < v.size(); j++) {
            if(v[j].l < i) {
                tmp = tmp * double((v[j].r - i + 1))/vlen[j];
            }
        }
        p.push_back(tmp);
        tmp = 1;
    }
    
    for(i = int(p.size()-1); i > 0; i--){
        p[i] = p[i] - p[i-1];
    }
    return p;
}

double calE(vector<double> &p, int rangel, int ranger) {
    int i;
    double E = 0;
    for(i = 0; i < p.size(); i++) {
        E = E + (ranger - i)*p[i];
    }
    return E;
}

int main() {
    int N;
    cin>>N;
    
    prs tmp;
    vector<prs> v;
    int rangel, ranger;
    int i;
    vector<double> p;
    
    //按照实际题目的要求，更新了一下
    /*
     for(i = 0; i < N; i++) {
     cin>>tmp.l>>tmp.r;
     v.push_back(tmp);
     }
     */
    
    for(i = 0; i < N; i++) {
        cin>>tmp.l;
        v.push_back(tmp);
    }
    for(i = 0; i < N; i++) {
        cin>>v[i].r;
    }
    
    range(v, rangel, ranger);
    p = ps(v, rangel, ranger);
    cout.setf(ios::fixed);
    cout<<fixed<<setprecision(6)<<calE(p, rangel, ranger)<<endl;
    return 0;
}