题面
翻译
给出一个字符串, 问用以下方式构造出的字符串有多少种不同的选择(两种选择不同当且仅当两个字符串不相同), 输出答案 \(mod (1e9 + 7)\) 的结果:
- 在原序列选择一些位置, 并保证它们两两不相邻。
- 将未选择的位置删除。
- 得到新的字符串
题解
考虑每一个位置, 它如果接在一个字符串后面, 其实方案数与前一个字符的位置无关, 只与前面一个字符是啥相关。 所以我们可以用一个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)
//因为这份代码又臭又长, 所以大家大可不必管他