阿里巴巴笔试3.27场

问题1：给两个等长字符串，长度范围1e5，你可以选择第一个字符串的一个字符移动到字符串尾部，目的是让两个字符串相等，求最小的移动次数。

思路：问题可转化为求第一个字符串的子序列和第二个字符串前缀的最长匹配长度，答案为字符串长度减去这个匹配长度。

注意特殊判断无解的情况，即两个字符串存在一种字符的数量不一致。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

char s1[N], s2[N];
int cnt1[30], cnt2[30], ans = 0;
int main() {
	scanf("%s%s", s1, s2);
	int n = strlen(s1);
	for(int i = 0; i < n; i++)cnt1[s1[i] - 'a']++, cnt2[s2[i] - 'a']++;
	for(int i = 0; i < 30; i++)if(cnt1[i] != cnt2[i]) {
		puts("-1");
		return 0;
	}
	for(int i = 0; i < n; i++)if(s1[i] == s2[ans])ans++;
	printf("%d\n", n - ans);
	return 0;
}

问题2：给定n(n <= 2000)个区间[L,R](1 <= L <= R <= 2000)，从这n个区间中分别等概率取一个整数，一共n个数，求这些数最小值的期望。

思路：求出每个数作为最小值的概率即可，数x为最小值的概率为（所有数大等于x的概率 - 所有数大等于x + 1的概率）

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 7;
int L[N], R[N];
double p[N];
int main() {
	int n; scanf("%d", &n);
	for(int i = 0; i < n; i++)scanf("%d", &L[i]);
	for(int i = 0; i < n; i++)scanf("%d", &R[i]);
	p[1] = 1;
	for(int i = 2; i <= 2000; i++) {
		double sum = 1;
		for(int j = 0; j < n; j++) {
			if(i <= L[j]);
			else if(i > R[j])sum = 0;
			else sum *= 1.0 * (R[j] - i + 1) / (R[j] - L[j] + 1);
		}
		p[i] = sum;
	}
	double ans = 0;
	for(int i = 1; i <= 2000; i++)ans += i * (p[i] - p[i + 1]);
	printf("%.10lf\n", ans);
}