abc 214G Three Permutations

题面

abc 214G Three Permutations

翻译

给出一个字符串, 问用以下方式构造出的字符串有多少种不同的选择(两种选择不同当且仅当两个字符串不相同), 输出答案 \(mod (1e9 + 7)\) 的结果:

  1. 在原序列选择一些位置, 并保证它们两两不相邻。
  2. 将未选择的位置删除。
  3. 得到新的字符串

题解

考虑每一个位置, 它如果接在一个字符串后面, 其实方案数与前一个字符的位置无关, 只与前面一个字符是啥相关。 所以我们可以用一个DP来记录来记录在这个位置前一个(因为不能相邻)之前以第 \(i\) 种字符结尾的方案总数。 而当前位置更新答案时候只需要用 \(1 + \sum_i^26 dp[i]\) 就可以了, 不过这里要注意, 算出来了不能立刻更新, 要等算完下一个位置再更新(不能相邻)。 有些人可能会觉得这样做会有重复, 但其实不会, 因为对于 \(l\) 位置的第 \(i\) 种字符, 上一个第 \(i\) 种字符的位置上的值经过更新会直接被丢掉, 也就是说它不会再直接影响答案了。

代码

实现方法1:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 200000
#define INF 1000000007

char s[MAXN + 5];
long long dp[26 + 5];

int main () {
	int n;
	long long sum = 0;//用于更新和记录答案
	long long last = 0;//用于记录要延迟更新的值
	int t = 0;//用于标记延迟更新的位置, (其实主要是第一个位置不用的话需要特判, 说白了就是懒)
	
	scanf ("%s", s + 1);
	n = strlen (s + 1);
	for (int i = 1; i <= n; i ++) {
		long long x = sum + 1;
		
		x %= INF;
		sum += (last - dp[t]);
		sum %= INF;
		sum += INF;
		sum %= INF;
		dp[t] = last;
		last = x;
		t = s[i] - 'a' + 1;
	}
	printf ("%lld", (sum + last - dp[t] + INF) % INF);//因为最后一次还没更新进去, 所以这里还要用一次更新
}
//时间复杂度:O(n)

实现方法2:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 200000
#define INF 1000000007

char s[MAXN + 5];
long long dp[26 + 5][2];
int sl[26 + 5];

int main () {
	int n;
	
	scanf ("%s", s + 1);
	n = strlen (s + 1);
	for (int i = 1; i <= n; i ++) {
		long long sum = 1;
		
		for (int j = 1; j <= 26; j ++) {
			if (sl[j] == i - 1) {
				sum += dp[j][1];
				sum %= INF;
			}
			else {
				sum += dp[j][0];
				sum %= INF;
			}
		}
		dp[s[i] - 'a' + 1][1] = dp[s[i] - 'a' + 1][0];
		dp[s[i] - 'a' + 1][0] = sum;
		sl[s[i] - 'a' + 1] = i;
	}
	
	long long ans = 0;
	
	for (int i = 1; i <= 26; i ++) {
		ans += dp[i][0];
		ans %= INF;
	}
	printf ("%lld", ans);
}
//时间复杂度:O(26n)
//因为这份代码又臭又长, 所以大家大可不必管他
上一篇:悟空CRM系统学习心得


下一篇:CRM如何进行销售区域管理?