第十五节 数论 - 2

AT_abc182_d 题解

洛谷链接&Atcoder 链接

本篇题解为此题较简单做法及较少码量，并且码风优良，请放心阅读。

题目简述

从数轴的原点开始向正方向走。

第一次向前走 \(a_1\) 步，第二次向前走 \(a_1+a_2\)，以此类推。

求走过的最大位置。

思路

首先直接模拟时间复杂度 \(O(n^2)\)，看一下数据范围 \((1 \le N \le 2 \times 10^5)\) 得知此方法会超时。

那么就需要一点优化，用前缀和即可解决此题，没学过前缀和的建议看这个。通过前缀和求出前 \(i\) 项的和就很容易解决此题了：

for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}

先预处理前缀和，在预处理的过程中同步求最大值，但因为此题的答案即最大值有可能在过程中产生，故需要 \(O(N)\) 遍历前缀和求最大，此时间复杂度可以接受。

经过以上分析和前缀和优化，很容易即可得出代码了：

#include<iostream>
using namespace std;

int n, a[200005];
long long pre[200005], maxn[200005]; // 前缀和数组及最大前缀和数组

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i]; // 预处理前缀和
		maxn[i] = max(maxn[i - 1], pre[i]); // 预处理前缀和最大值
	}
	long long temp, ans = -0x3f3f3f3f; // ans 要求最大值，所以建议赋值一个足够小的负数
	for(int i = 1; i <= n; i ++) {
		ans = max(ans, maxn[i] + temp); // 遍历求最大值
		temp += pre[i]; // 一点点模拟
	}
	cout << ans << endl; // 输出，换行好习惯
	return 0;
}

提交记录

AT_arc113_c 题解

洛谷链接&Atcoder 链接

本篇题解为此题较简单做法及较少码量，并且码风优良，请放心阅读。

题目简述

现在有一个字符串 \(S\)，每一次你可以选择一个 \(i(1 \le i \le | S |)\)，如果 \(S_i = S_{i + 1} \ne S_{i + 2}\)。就可以将 \(S_{i + 2}\) 设为 \(S_i\)

求最多能操作几次。

思路

本题比较贪心，让我们先来造一个样例解释一下：

如 abbfioidddssabsaa 最优的方案是：

• 先操作 \(4\) 次变为 abbfioidddsssssss。

• 再操作 \(7\) 次变为 abbfioidddddddddd。

• 最后操作 \(14\) 次变为 abbbbbbbbbbbbbbbb。

这样最大总操作次数为 \(25\) 次。

从这个样例中可以发现贪心思路，要想总操作次数最大化，就需要从后到前去操作，如果从前到后操作那么后面可操作的连续字母就会被覆盖，这样总操作次数就不是最大了。

对于每次操作，最优的是把后面的所有不相同的字母变为一样，这就涉及到一个问题，如果后面有相同字母如何判断？其实不必再从当前位置往后搜，只需要定义一个 \(num\) 一维数组用 \(num_i\) 表示当前位置的后面字母 \(i\) 的个数。

对于 \(num\) 数组需要在搜的过程中处理。如果遇到可以替换的情况就把当前位置后的字母全变为当前字母，同时需清空 \(num\) 数组的记录，把当前位置的字母数记录即可。

替换后，\(ans\) 需增加 \(n - i\)，考虑到后面的相同字母，所以就需要用到我们维护的 \(num\) 数组了，所以操作数需减去 \(num_{str_{i}-'a'}\)。

经过以上分析及优化后，很容易即可写出代码了：

#include<iostream>
using namespace std;

string str;
long long ans = 0, num[205];

int main() {
	cin >> str;
	int n = str.length(); // 记录 str 的长度
	num[str[n - 1] - 'a'] ++, num[str[n - 2] - 'a'] ++; // 初始化 num 数组
	for(int i = n - 3; i >= 0; i --) {
		num[str[i] - 'a'] ++; // 记录此位置的字母
   		// 满足替换的条件
		if(str[i + 1] != str[i + 2] && str[i] == str[i + 1]) {
			ans += n - i - num[str[i] - 'a'];
			for(int j = 0; j < 26; j ++) num[j] = 0; // 清空 num 数组
			num[str[i] - 'a'] = n - i; // 记录替换后的字母数
		}
	}
	cout << ans << endl; // 输出，换行好习惯
	return 0;
}

提交记录