第十一届蓝桥杯省赛A组C/C++第二场(个人部分题解)

标题H题 字符标题串分值

思路：先遍历一遍所有字符，记录a b c…各有多少个，在整个串中只有一个字母的有多少种，然后再依次的减去最前面一个，同时更新减去的字符对这个串的影响，即减少了多少个或者增加了多少。

#include<iostream>
using namespace std;
#include<stdio.h>
#define N 100000
#include<string.h>
int main() {
	char s[N];
	int next[N], count[26], head[26];
	int n, sum = 0, res = 0, tmp = 0;
	gets(s);
	n = strlen(s);
	fill(count, count + 26, 0);
	fill(head, head + 26, -1);
	for (int i = n - 1; i >= 0; i--) {
		int t = s[i] - 'a';
		next[i] = head[t];
		head[t] = i;
	}
	for (int i = 0; i < n; i++) {
		int t = s[i] - 'a';
		count[t]++;
		if (count[t] == 1)tmp++;
		else if (count[t] == 2)tmp--;
		sum += tmp;
	}
	res += sum;
	for (int i = 0; i < n - 1; i++) {
		int t = s[i] - 'a';
		head[t]=next[head[t]];
		if (count[t] > 2) {
			sum += next[head[t]] + i - (head[t] << 1);
		}
		else if (count[t] == 2) {
			sum += n + i - (head[t] << 1);
		}
		else sum -= n - i;
		count[t]--;
		res += sum;
	}
	printf("%d", res);
	return 0;
}

标题J题字符串排序

找规律，在所有字符不同情况下最大有多少次交换，增加一个相同的减少几次交换，依次类推

#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
inline int f(int n) {
	return n * (n - 1) / 2;
}
bool check(int n,int k) {
	int sum, t;
	t = n / 26;
	sum = n * (n - 1) / 2 - f(t) * 26 - (n % 26)*t;
	return sum >= k;
}
int main() {
	int k,t,sum;
	int arr[26] = { 0 };
	char s[2000];
	scanf("%d", &k);
	int l = 1, n = 145;
	while (l < n) {
		int mid = (l + n) >> 1;
		if (check(mid, k))n = mid;
		else l = mid + 1;
	}//寻找凑成该幸运数的最小长度
	t = n / 26;//每个字母共同个数
	sum = n * (n - 1) / 2 - f(t) * 26 - (n % 26)*t;//该长度的最大幸运数
	if(t)
	for (int i = 0; i < 26; i++) {
		arr[i] += t;
	}
	n %= 26;
	for (int i = 0; i <n ; i++) {//公共字母个数多余的部分
		arr[i] += 1;
	}
	int i = 25, j = 0;
	if (t) {
		if (arr[0] != arr[25])
			while (arr[j] != t)j++;//求从0开始第一个拥有公共个数字母的下标
	}
	while (arr[i] == 0)i--;//出去不存在的字母
	while (sum != k) {
		if (arr[i] == 0)i--;
		if (j >=i)j = 0;
		t = arr[j] - arr[i]+1;//高下标少一个低下标多一个相应交换次数减少的个数
		if (sum - t >= k) {
			sum -= t; arr[j]++; j++; arr[i]--;
		}
		else i--;//如果sum-t<k则高下标降标
	}
	i = 25; j = 0;
	while(arr[i]==0)i--; 
	while (i>=0) {
		while (arr[i]) {
			s[j++] = i+'a';arr[i]--;
		}
		i--;
	}
	s[j] = '\0';
	printf("%s", s);
	return 0;
}

本文地址：https://blog.csdn.net/SpaceAndTimeComp/article/details/109241003