2022牛客杭电多校dp+字符串题目汇总

2022牛客杭电多校dp+字符串题目汇总

文章目录

• 牛客：
• 第一场 I.Chiitoitsu (期望dp)
• 第二场 K.Link with Bracket Sequence I(括号序列dp)
• 第二场 L.Link with Level Editor (线性dp)
• 第三场 H.Hacker (SAM+线段树）
• 第四场 A.Task Computing (背包)
• 第七场 J.Melborp Elcissalc(组合数学+思维dp)
• 第九场 G.Magic Spells (回文自动机or哈希)
• 第九场 B.Two Frogs(概率+后缀和优化dp)
• 第九场 I(单调栈orST表优化dp)
• 杭电
• 第一场A:string (border瞎搞)

牛客：

第一场 I.Chiitoitsu (期望dp)

题意：
打麻将，初始手中有13张牌，相同的牌最多有两张。
每轮从牌堆摸牌，若凑成七对子则赢，游戏结束；否则从手中选择一张牌并丢弃。
给定初始手牌，求最优策略下凑成七对子的期望轮数。

思路：

我们有一个很明显的最优策略，如果当前摸得牌凑不成对子，那么我们就将其丢弃。
我们考虑期望 d p dp dp:
d p [ i ] [ j ] dp[i][j] dp[i][j]表示当前手中已经凑够 i i i对，牌堆中还有 j j j张牌的情况下获胜的期望轮数。
考虑倒推：

    for(int i = 6; i >= 0; i--) {int x = (13 - i * 2) * 3;for(int j = x; j <= 123; j++) {f[i][j] = f[i + 1][j - 1] * x % mod * qpow(j, mod - 2, mod) % mod + f[i][j - 1] * (j - x) % mod * qpow(j, mod - 2, mod) % mod+ 1;f[i][j] %= mod;}}

第二场 K.Link with Bracket Sequence I(括号序列dp)

题意：
给定一个括号序列 a a a，长度为 n n n，它是长度为 m m m的合法括号序列 b b b的子序列。
求可能的 b b b的数量。
思路：
这题一眼线性 d p dp dp，同时也很显然，难点在于如何去设计一个合法且不重不漏的状态。
首先一个启发来自 a a a是 b b b的子序列，那么我们就定义:
f [ i ] [ j ] f[i][j] f[i][j]：当前构造到了第 i i i位，与 a a a的最长公共子序列的长度为 j j j的方案数。
这个不难想到，关键是如何去确定我们构造的是合法且不重不漏。
可以参考我这篇题解
那么我们最终的状态就是:
f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]：当前构造到了第 i i i位，与 a a a的 l c s lcs lcs为 j j j，且左括号比右括号多 k k k个的方案数。
初始状态 f [ 0 ] [ 0 ] [ 0 ] = 1 f[0][0][0]=1 f[0][0][0]=1。
目标状态 f [ m ] [ n ] [ 0 ] f[m][n][0] f[m][n][0]。
状态转移就没什么难度了，枚举每一位填左括号和右括号即可。

code:

		int n, m;cin >> n >> m; for(int i = 0; i <= m; i++)     for(int j = 0; j <= n; j++)for(int k = 0; k <= m + 1; k++) f[i][j][k] = 0;f[0][0][0] = 1;string s; cin >> s;s = ' ' + s;for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {for(int k = 0; k <= m; k++) {f[i][0][k] = (f[i - 1][0][k - 1] * (k >= 1)+ f[i - 1][0][k + 1]) % mod;if(s[j] == '(') {if(k >= 1)f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k - 1]) % mod;f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % mod;} else {if(k >= 1)f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % mod;f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k + 1]) % mod;}}}}cout << f[m][n][0] << 'n';

第二场 L.Link with Level Editor (线性dp)

题意：
有 n n n个世界，每个世界有 m m m个点， l l l条边。
在第 i i i个世界，你最多可以选择一条边 ( u , v ) (u,v) (u,v)，从 u − > v u->v u−>v，随后进入第 i + 1 i+1 i+1个世界的点 v v v，如果不选择移动，进入第 i + 1 i+1 i+1个世界的点 u u u。
求最小的区间长度(从1出发)，可以从点 1 − > m 1->m 1−>m。
思路：
一个很朴素的线性 d p dp dp。没什么好说的。
code:

int f[2][N]; //在第i个世界到达点j，最短的长度signed main() {
#ifdef JANGYIfreopen("input.in", "r", stdin);freopen("out.out", "w", stdout);
#endifint n, m;scanf("%d%d", &n, &m);memset(f, 0x3f, sizeof f);int now = 1;f[0][1] = 0;int ans = inf;for(int i = 1; i <= n; i++) {f[now][1] = 0;for(int j = 2; j <= m; j++) f[now][j] = f[now ^ 1][j] + 1;int l; scanf("%d", &l);while(l--) {int u, v; scanf("%d%d", &u, &v);f[now][v] = min(f[now][v], f[now ^ 1][u] + 1);}ans = min(ans, f[now][m]);now ^= 1;}if(ans == inf) puts("-1");else printf("%d", ans);return 0;
}

第三场 H.Hacker (SAM+线段树）

题意：
给定一个长度为 n n n的字符串 A A A和 k k k个长度为 m m m的字符串 B 1 , B 2 , . . . , B k B_1,B_2,...,B_k B1​,B2​,...,Bk​， B B B的每一个位置拥有统一的权值 v a l 1 , v a l 2 , . . . , v a l m val_1,val_2,...,val_m val1​,val2​,...,valm​。对于每一个 B i B_i Bi​求一个区间，使的该区间权值和最大且是 A A A的子串。 n , m , k ≤ 1 e 5 , m ∗ k ≤ 1 e 6. n,m,kleq1e5, m*kleq1e6. n,m,k≤1e5,m∗k≤1e6.
思路：
这个题的想法学过 S A M SAM SAM的话应该一眼就可以想到。
我们考虑对 A A A串建一个 S A M SAM SAM，然后每个串 B i B_i Bi​跑一遍匹配，求出每一个在 A A A中出现过的子串的区间 [ L , R ] [L,R] [L,R]，然后用线段树求出区间内最大的连续子段和即可。
code:

#pragma GCC optimize(3,"Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "n"
#define lowbit(x) ((x)&(-x))
#define inf INT_MAX
#define INF LONG_LONG_MAX
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const ll mod=1e9+7;
/**************************************************************************************/
const int N=1e5+10, M = 4 * N;
int n, m, k;
char s[N];
int val[N * 10];
struct SAM__ {int len[M], link[M];int ch[M][26];int siz, last;void init() {memset(link, 0, sizeof link);memset(len, 0, sizeof len);memset(ch, 0, sizeof ch);siz = last = 0;link[0] = -1;}void ectend(char *str) {int n = strlen(str);for(int i = 0; i < n; i++) {int cur = ++siz, p = last, c = str[i] - 'a';len[cur] = len[p] + 1;while(p != -1 && !ch[p][c]) {ch[p][c] = cur;p = link[p];}if(p == -1) link[cur] = 0;else {int q = ch[p][c];if(len[q] == len[p] + 1) link[cur] = q;else {int copy = ++siz;len[copy] = len[p] + 1;link[copy] = link[q];for(int j = 0; j < 26; j++) ch[copy][j] = ch[q][j];while(p != -1 && ch[p][c] == q)  {ch[p][c] = copy;p = link[p];}link[q] = link[cur] = copy;}}last = cur;}}
}SAM;
char str[N * 10];struct node{ll sum,dat,lmax,rmax;
}tr[N<<3];
#define ls (now<<1)
#define rs (now<<1|1)
void merge(int now){tr[now].sum=tr[ls].sum+tr[rs].sum;tr[now].lmax=max(tr[ls].lmax,tr[ls].sum+tr[rs].lmax);tr[now].rmax=max(tr[rs].rmax,tr[rs].sum+tr[ls].rmax);tr[now].dat=max({tr[ls].dat,tr[rs].dat,tr[ls].rmax+tr[rs].lmax});
}
void build(int now,int l,int r){if(l==r){tr[now]={val[l],val[l],val[l],val[l]};return ;}int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);merge(now);
}
node query(int now,int l,int r,int L,int R){if(L<=l&&r<=R) return tr[now];int mid=l+r>>1;node LL,RR,x;LL={-mod,-mod,-mod};RR={-mod,-mod,-mod};x.sum=0;if(L<=mid){LL=query(ls,l,mid,L,R);x.sum+=LL.sum;}if(R>mid){RR=query(rs,mid+1,r,L,R);x.sum+=RR.sum;}x.dat=max({LL.dat,RR.ax+RR.lmax});x.lmax=max(LL.lmax,RR.lmax+LL.sum);x.rmax=ax,RR.sum&#ax);return x;
}
void solve(char *str) {int p = 0;int len = 0;int W = strlen(str);ll ans = 0;for(int i = 0; i < W; i++) {int c = str[i] - 'a';if(SAM.ch[p][c]) {len++;p = SAM.ch[p][c];} else {while(p != -1 && !SAM.ch[p][c]) p = SAM.link[p];if(p != -1) len = SAM.len[p] + 1, p = SAM.ch[p][c];else p = 0, len = 0;}// cout << i << ' ' << len << ' ';int L = i + 1 - len + 1, R = i + 1;// ans = max(ans, query(L, R));// cout<<L<<' '<<R<<endl;if(L>R) continue;ans=max(ans,query(1,1,m,L,R).dat);}cout << ans << 'n';
}
int main()
{// IOS;scanf("%d%d%d", &n, &m, &k);scanf("%s", s);SAM.init();d(s);for(int i = 1; i <= m; i++) scanf("%d", &val[i]);build(1,1,m);while(k--) {scanf("%s", str);solve(str);}}

第四场 A.Task Computing (背包)

题意：
给定 n ≤ 1 e 5 nleq1e5 n≤1e5个物品，每个物品有 ( w i , p i ) (w_i,p_i) (wi​,pi​)两个值，选出 m ≤ 20 mleq20 m≤20个物品，使得 ∑ i = 1 m ( w i ∗ ∏ j = 1 i − 1 p j ) sum_{i=1}^{m}{(w_i*prod_{j=1}^{i-1}{p_j})} ∑i=1m​(wi​∗∏j=1i−1​pj​)最大。
思路：
假如现在选了3个物品：
v a l 1 = w 1 + w 2 ∗ p 1 + w 3 ∗ p 2 ∗ p 1 val_1=w_1+w_2*p1+w_3*p_2*p_1 val1​=w1​+w2​∗p1+w3​∗p2​∗p1​
又选了一个：
v a l 2 = v a l + w 4 ∗ p 1 ∗ p 2 ∗ p 3 val_2=val+w_4*p_1*p_2*p_3 val2​=val+w4​∗p1​∗p2​∗p3​
我们发现这样下去并没有什么用。
正难则反，我们考虑反向添加。
假设我们现在选的物品权值是 v a l val val，那么我们往前添加一个物品，我们会发现权值为 w i + v a l ∗ p i w_i+val*p_i wi​+val∗pi​。
那么现在就是我们以一个什么样的顺序从后往前添加物品。
如果物品 i i i放在 j j j前面所获得的权值要大的话需满足：
w i + p i ∗ ( w j + p j ∗ v a l ) > w j + p j ∗ ( w i + p i ∗ v a l ) w_i+p_i*(w_j+p_j*val)>w_j+p_j*(w_i+p_i*val) wi​+pi​∗(wj​+pj​∗val)>wj​+pj​∗(wi​+pi​∗val)
我们排个序即可。
code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
double f[100010][22];
int n, m;
struct Node {int w;double p;
}a[100100];
int main()
{#ifdef cbyyxfreopen(&#","r",stdin);freopen(&#","w",stdout);#endifscanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i].w);for(int i = 1; i <= n; i++) {int x; scanf("%d", &x);a[i].p = x * 1.0 / 10000;}sort(a + 1, a + 1 + n, [&](Node x, Node y) {return x.w * (y.p - 1) < y.w * (x.p - 1);});for(int i = n; i >= 1; i--) {for(int j = 0; j <= m; j++) {f[i][j] = f[i + 1][j];if(j)f[i][j] = max(f[i][j], a[i].p * 1.0 * f[i + 1][j - 1] + a[i].w);}}printf("%.12lf", f[1][m]);}

第七场 J.Melborp Elcissalc(组合数学+思维dp)

题意：
给定数字 k ≤ 64 kleq64 k≤64，问有多少种长度为 n ≤ 64 nleq64 n≤64的数组满足：
数的范围为 [ 0 , k − 1 ] [0,k-1] [0,k−1]；有 t t t个区间，满足其区间和为 k k k的整数倍。
思路：
假设我们现在已经知道前缀和数组 s u m [ n ] sum[n] sum[n]，也就是需满足 s u m [ l − 1 ] , s u m [ r ] sum[l-1],sum[r] sum[l−1],sum[r]在模 k k k的意义下相等。
其次非常非常重要的一点就是：数的范围 [ 0 , k − 1 ] [0,k-1] [0,k−1]，代表者如果我们现在确定了前缀和数组，那么就可以唯一确定原数组。
所以我们只需计算合法的前缀和数组的个数即可。
所以我们枚举 [ 0 , k − 1 ] [0,k-1] [0,k−1]在数组中出现了多少次。
我们定义 f [ i ] [ j ] [ s ] f[i][j][s] f[i][j][s]为前 i i i个数中，我们选择了 j j j个，贡献合法区间个数为 s s s个。
目标状态: f [ k ] [ n ] [ t ] f[k][n][t] f[k][n][t]。
我们可以写出以下非常暴力的代码。

int n, k, t; cin >> n >> k >> t;f[0][0][0] = 1;for(int i = 1; i <= k; i++) {for(int j = 0; j <= n; j++) {for(int q = 0; q <= t; q++) {if(f[i - 1][j][q] == 0) continue;for(int x = 0; x + j <= n; x++) {if(i == 1) {f[i][j + x][q + C(x + 1, 2)] = (f[i][j + x][q + C(x + 1, 2)] + f[i - 1][j][q] * C(j + x, x)) % mod;} else {f[i][j + x][q + C(x, 2)] = (f[i][j + x][q + C(x, 2)] + f[i - 1][j][q] * C(j + x, x)) % mod;}}}}}

我们枚举当前要填入的数 i i i，枚举填 x x x个，填完后数组长度为 x + j x+j x+j。
那么这个数产生的合法区间贡献就是 C ( x , 2 ) C(x,2) C(x,2)，同时我们这 x x x个数是可以随便放的，产生的方案就是 C ( x + j , x ) C(x+j,x) C(x+j,x)。同时需注意我们的前缀和数组是有一个 s u m [ 0 ] = 0 sum[0]=0 sum[0]=0的，所以 i = 1 i=1 i=1的时候特判。

第九场 G.Magic Spells (回文自动机or哈希)

给定最多5个字符串，求有多少个回文子串，同时是这 k k k个串的子串。
思路：
哈希可以做，但是（不想写。
果断选择回文自动机。最多才5个，我们对每个串建一个 P A M PAM PAM，然后跑 d f s dfs dfs，每次同时对所有串去进行扩展。
code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 6e5 + 10;
char s[N];
struct Node {int fail[N], len[N], ch[N][26], cnt;int res[N];void init() {fail[0] = 1; fail[1] = 1;len[1] = -1;cnt = 1;}int get_fail(int x, int i) {while(i - len[x] - 1 < 0 || s[i - len[x] - 1] != s[i]) x = fail[x];return x;}int last = 0;void insert(char c, int i) {int x = get_fail(last, i), w = c - 'a';if(!ch[x][w]) {len[++cnt] = len[x] + 2;int temp = get_fail(fail[x], i);fail[cnt] = ch[temp][w];ch[x][w] = cnt;}last = ch[x][w];}} tr[10];int k, res;void dfs(vector<int> p) {if(tr[0].len[p[0]] >= 1) res++;// cout << tr[0].len[p[0]] << endl;for(int i = 0; i < 26; i++) {bool f = 1;for(int j = 0; j < k; j++) {if(!tr[j].ch[p[j]][i]) {f = 0;break;}}if(f) {vector<int> now;for(int j = 0; j < k; j++) {now.push_back(tr[j].ch[p[j]][i]);}dfs(now);}}
}int main()
{scanf("%d", &k);for(int i = 0; i < k; i++) tr[i].init();for(int i = 0; i < k; i++) {scanf("%s", s + 1);int len = strlen(s + 1);for(int j = 1; j <= len; j++) tr[i].insert(s[j], j);// cout << tr[i]t << endl;}vector<int> a, b;for(int i = 1; i <= k; i++) {a.push_back(1);b.push_back(0);}dfs(a); dfs(b);cout << res << 'n';
}

第九场 B.Two Frogs(概率+后缀和优化dp)

题意：
河道里有 n ≤ 8000 nleq8000 n≤8000个荷叶排成一排，从第 i i i个荷叶出发可以跳到第 ( i , i + a [ i ] ] (i,i+a[i]] (i,i+a[i]]个荷叶上，有两只青蛙从第1个荷叶出发，每一步都独立地等概率随机地跳向后边的荷叶，求两只青蛙以相同步数到达第 n n n个荷叶的概率。
思路：
两只青蛙互不影响，所以我们单独对一只青蛙考虑；
定义 f [ i ] [ j ] f[i][j] f[i][j]:当前在第 i i i个荷叶上，用了 j j j步的概率。
初始化 f [ n ] [ 0 ] = 1 f[n][0]=1 f[n][0]=1。
考虑倒推：

     for(int i = n - 1; i >= 1; i--) for(int j = 1; j <= n; j++)for(int k = 1; k <= a[i]; k++){f[i][j] += f[i + k][j - 1] * inv(a[i]) % mod; //[i + 1, i + a[i]]f[i][j] %= mod;}

暴力枚举下一步跳到了哪个荷叶上。显然我们可以用后缀和优化。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 8e3 + 10, mod = 998244353;ll qpow(ll a, ll b) {ll ans = 1;while(b) {if(b & 1) ans = ans * a % mod;b >>= 1;a = a * a % mod;}return ans;
}
int inv[N];
int n, a[N];
int f[N][N], sum[N][N];int main()
{scanf("%d", &n);for(int i = 1; i < n; i++) scanf("%d", &a[i]),inv[i]=qpow(a[i],mod-2);f[n][0] = 1;// for(int i = n - 1; i >= 1; i--) //     for(int j = 1; j <= n; j++)//         for(int k = 1; k <= a[i]; k++){//             f[i][j] += f[i + k][j - 1] * inv(a[i]) % mod; //[i + 1, i + a[i]]//             f[i][j] %= mod;//         }sum[n][0] = 1;for(int i = n - 1; i >= 1; i--) {sum[i][0]=1;// for(int j = 0; j <= n; j++) sum[i][j] = sum[i + 1][j];for(int j = 1; j <= n; j++) {f[i][j] = (f[i][j] + 1ll*(sum[i + 1][j - 1] - sum[i + a[i] + 1][j - 1] + mod) % mod * inv[i] % mod) % mod;sum[i][j] = (sum[i][j]+((sum[i+1][j] + f[i][j]) % mod))%mod;}} ll ans = 0;for(int i = 1; i <= n; i++) ans = (ans + 1ll*f[1][i] * f[1][i] % mod) % mod;cout << ans << endl;
}

第九场 I(单调栈orST表优化dp)

题意：
给定长为 n ≤ 8000 nleq8000 n≤8000的整数序列，将其分为非空的 k k k段使得每一段的最大值之和最小，对 k = [ 1 , n ] k=[1,n] k=[1,n]分别求解。
思路：
我们可以定义 d p [ i ] [ j ] dp[i][j] dp[i][j]：前 i i i个数，划分了 j j j段的最小值。
显然我们需要枚举上一段。

for(int i = 1; i <= n; i++) {for(int j = 1; j <= i; j++) {for(int x = 0; x < j; x++) {f[i][j] = min(f[i][j], f[x][j - 1] + max_val(x + 1, j));}}}

杭电

第一场A:string (border瞎搞)

题意：
给定一个字符串s和k，求每个前缀子串满足 ( l e n ∗ 2 − i ) % k = = 0 (len*2-i)%k==0 (len∗2−i)%k==0的所有 b o r d e r border border的数量。
思路：
考虑建个board树，转换一下等式：len2=i (mod k)。我们开k个vector记录长度为len2%k的border的数量，每遍历一个点加进去。
对于当前结点，我们的答案显然是从根节点到当前结点的一条链上满足条件的个数（需满足len*2>u)
我们二分查找即可。
code:

const int N = 1e6 + 10, mod = 998244353;
char s[N];
int ne[N];
LL ans[N];
int k;
vi cnt[N];
vi edge[N];void dfs(int u) {int val = 2 * u % k;cnt[val].pb(2 * u);int x = u % k;if(cnt[x].size()) {ans[u] = cnt[x].size() - (upper_bound(all(cnt[x]), u) - cnt[x].begin());} else ans[u] = 0;for(auto t : edge[u]) dfs(t);cnt[val].pop_back();
}
void solve() {scanf("%s%d", s + 1, &k);int n = strlen(s + 1);for(int i = 0; i <= n; i++) ne[i] = 0, edge[i].clear();for(int i = 2, j = 0; i <= n; i++) {while(j > 0 && s[i] != s[j + 1]) j = ne[j];if(s[i] == s[j + 1]) j++;ne[i] = j;edge[j].pb(i);}edge[0].pb(1);dfs(0);LL res = 1;for(int i = 1; i <= n; i++) {res = (ans[i] + 1) * res % mod;ans[i] = 0;}cout << res << 'n';
}