【蓝桥·算法双周赛 第 9 场 小白入门赛】字符迁移【算法赛】题解（字符串+模运算+差分）

思路

差分数组是一种特殊的数组，它的第 i i i 个数定义为原数组的第 i i i 个元素和第 i − 1 i-1 i−1 个元素的差值。差分数组的主要用途是高效地处理区间增减操作。

首先从输入中读取字符串长度 n 和操作次数 q，以及字符串 s。然后将字符串 s 中的每个字符转换为对应的 ASCII 值减去 ‘a’ 的值，存储在数组 a 中，这样做的目的是为了方便后续的操作。接下来计算数组 a 中相邻元素的差值，存储在数组 diff 中。

然后进行 q 次操作，每次操作读取三个整数 l，r 和 k，将 k 对 26 取模，然后在 diff 数组的 l 位置上加上 k，在 r+1 位置上减去 k。这一步操作利用了差分数组的性质，即修改差分数组的某个范围内的值，相当于原数组中对应范围内的所有元素都加上了同一个值。

在所有操作完成后，通过差分数组 diff 还原数组 a，然后将数组 a 中的每个元素对 26 取模并加上 ‘a’ 的 ASCII 值，转换为对应的字符，存储回字符串 s 中。

最后输出字符串 s。

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;

int n, q;
int a[N];
char s[N];
int diff[N];

int main() {
	memset(diff, 0, sizeof(diff));

	scanf("%d %d %s", &n, &q, s + 1);
	for (int i = 1; i <= n; i++) {
		a[i] = (int)(s[i] - 'a');
	}
	for (int i = 1; i <= n; i++) {
		diff[i] = a[i] - a[i - 1];
	}
	while (q--) {
		int l, r, k;
		scanf("%d %d %d", &l, &r, &k);
		k %= 26;
		diff[l] += k;
		diff[r + 1] -= k;
	}
	for (int i = 1; i <= n; i++) {
		int t = a[i] = diff[i] + a[i - 1];
		t %= 26;
		s[i] = (char)(t + 'a');
	}
	printf("%s", s + 1);
	return 0;
}