8.13科大讯飞研发卷2

3道编程50分加50分的选择。

1、a[a[i]] = n - a[i] + 1，i和a[i]范围都是1~n。求字典序最大的数组a。直接输出倒序即可。

2、一个字符串str，从str[i]走到str[i+1]需要str[i+1]-str[i]的体力，若为负数则会加体力。现在初始体力为k，求是否能从str[0]走到str[n]，若能输出剩余体力，若不能输出-1。

简单模拟即可。

int main(void){
  	int n, k;
  	cin >> n >> k;
  	getchar();
  	string str;
  	cin >> str;
  	for (int i = 0; i < n - 1; i++){
	  	k -= str[i+1] - str[i];
	  	if (k < 0){
		  	cout << -1 << endl;
		  	return 0;
		}
	}
  	cout << k << endl;
  	return 0;
}

3、有两个长度为n的数组nums1和nums2，都是由1~n的元素组成，且元素各不相同。现在要存储它们的子数组，相同的子数组可以只存储一次，求最少需要存储多少个子数组。

如[1,2,3]和[3,1,2]只需存储[1],[2],[3],[1,2],[2,3],[3,1],[1,2,3],[3,2,1]等8个子数组。

求出不相同的子数组个数即可，设dp[i]为nums1中以nums1[i]为结尾且不在nums2中的子数组数目，dp2[i]为nums1中以nums1[i]为结尾的所有子数组数目。则有：

1. 若序列{nums1[i-1], nums1[i]}不在nums2中：dp[i+1] = dp2[i]
2. 否则：dp[i+1] = dp[i]

因为两个数组的不同子数组个数和相同子数组个数都相同，则结果即为all+differentNum，all为所有子数组个数为n*(n+1)/2。

int main(void){
  	int n;
  	cin >> n;
  	vector<int> nums1(n);
  	for (int i = 0; i < n; i++)
	  	cin >> nums1[i];
  	set<pair<int, int>> st;
  	int pre = -1, tmp;
  	for (int i = 0; i < n; i++){
	  	cin >> tmp;
	  	st.insert({pre, tmp});
	  	pre = tmp;
	}
  	
  	long long dp = 0, dp2 = 1;
  	long long differentNum = 0;
  	for (int i = 1; i < n; i++){
	  	if (!st.count({nums1[i-1], nums1[i]}))
		  	dp = dp2;
	  	dp2++;
	  	differentNum += dp;
	}
  	long long all = 1LL * n * (n+1) / 2;
  	cout << all + differentNum << endl;
  	return 0;
}