【luogu P7469】积木小赛
积木小赛
题目链接:luogu P7469
题目大意
有两排积木。
第一排积木可以从任意地方选任意块数去掉。
第二排积木可以从后面和前面分别选任意块数去掉。
问你有多少种情况剩下的两排积木相同。
两个情况不同当剩下的积木不同。
思路
这道题我们首先会看到第二排积木其实就是选一个区间。
那你要和第一排积木匹配。
那你想到,有这么一种搞法,就是 DP。
你设
f
i
,
j
f_{i,j}
fi,j 为在
i
i
i 的位置往前找第一个是
j
j
j 的字符,所找到的位置是哪里。
那你就先枚举第二排积木的右边界,然后左边界不断向左推,然后你就可以与第一排进行匹配。
(一开始指针在最右边)
然后在可以还可以匹配的时候,我们要去重。(因为两种情况不同是剩下积木不同)
那去重有很多中方法,SAM 是最稳的,哈希加排序去重也行。
但是我是直接三质数哈希匹配,具体可以看看代码。
(感谢 HKY 大爷提供的可用质数)
代码
#include<cstdio>
#include<cstring>
#define ll long long
#define ull unsigned long long
#define times 131
#define times1 233
#define times2 199
#define mo 100007
#define mo1 1333331
#define mo2 49999
using namespace std;
int hash1[100007][501];
int n, bef[3001][31];
char s[3001], t[3001];
ll ans;
bool yes;
void add3000(ull now, ull now1, ull now2) {//哈希插入
int pl = now % mo;
int pl1 = now1 % mo1;
int pl2 = now2 % mo2;
for (int i = 1; i <= 500; i += 2) {
if (hash1[pl][i] == 0) {
hash1[pl][i] = pl1;
hash1[pl][i + 1] = pl2;
ans++;//之前找不到相同的
return ;
}
if (hash1[pl][i] == pl1 && hash1[pl][i + 1] == pl2) return ;//弄了两个质数进行匹配
}
}
int main() {
// freopen("block.in", "r", stdin);
// freopen("block.out", "w", stdout);
scanf("%d", &n);
scanf("%s", &s);
scanf("%s", &t);
memset(bef[0], -1, sizeof(bef[1]));
for (int i = 1; i <= n; i++) {//求出在这一位往前找某个字符第一个找到的是在哪里(DP)
for (int j = 0; j < 26; j++)
bef[i][j] = bef[i - 1][j];
bef[i][s[i - 1] - 'a'] = i - 1;
}
for (int i = 0; i < n; i++) {
int l = i;
int now = n;
ull noww = 0;
ull noww1 = 0;
ull noww2 = 0;
while (l >= 0) {
noww = (noww * times + t[l]) % mo;
noww1 = (noww1 * times1 + t[l]) % mo1;
noww2 = (noww2 * times2 + t[l]) % mo2;
now = bef[now][t[l] - 'a'];//匹配
if (now == -1) break;//匹配不了了
add3000(noww, noww1, noww2);//判断是否重复
l--;
}
}
printf("%d", ans);
fclose(stdin);
fclose(stdout);
return 0;
}