1.4 百度2024校招笔试真题

1.4.1 后缀变换

【题目描述】

牛牛定义一种字符串操作为: 对于任意字符串S,可以将其划分为两个非空子串x和y且满足S=xy，通过交换x和y子串的位置得到新字符串W且满足W=yx.例如对于字符串S="helloworld"，将其划分为两个部分x="hello"和y="world",经过操作后得到新字符串W="worldhello"。

在给定初始字符串S和结束字符串T以及进行操作次数k,问有多少种不同的操作方案使得将S转化成T？因为答案很大，所以需要模上1000000007后输出。

两种操作方案被视为不同当且仅当存在第i次操作时刻(1≤i≤k)，前者得到两部分子串为x1和y1，后者得到两部分子串为x2和y2时, x1≠x2成立。

输入描述：

第一行输入一个仅由小写字母构成的字符串S

第二行输入一个仅由小写字母构成的字符串T

第三行输入操作次数k

2≤|S|=|T|≤1000

1≤k≤100000

输出描述：

输出一个整数表示答案

输入样例：

aaca

caaa

2

输出样例：

2

说明：

"aaca" - "aaac" - "caaa"

"aaca" - "acaa" - "caaa"

【解题思路】

S串首尾相连转换成环的形式,那么对于每次操作的本质就是将下-轮起点转移到除当前的其他位置。考虑设dp[i[j]表示在第i次操作时处于环上第j个节点的方案，转移就是将dp[i-1][j]的值转移到除j以外的其他位置，直接修改复杂度是O(kn2),考虑到只有一个位置不被修改，将转移转化成全局修改以及单点修改两个部分，然后在O(nk)的复杂度内解决问题，进一步优化转移可以发现能将dp求解复杂度降为O(k)。对于最后答案的计算，将T串在S串上确定起点位置，然后将dp所得到对应起点的值求和即可。

【参考代码】

#include <bits/stdc++.h>

#define mp make_pair

#define pb push_back

#define pii pair<int, int>

#define link(x) for (edge *j = h[x]; j; j = j->next)

#define inc(i, l, r) for (int i = l; i <= r; i++)

#define dec(i, r, l) for (int i = r; i >= l; i--)

const int MAXN = 3e5 + 10;

const double eps = 1e-8;

const int mod = 1e9 + 7;

#define ll long long

using namespace std;

ll read() {

ll x = 0, f = 1;

char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-')

f = -1;

ch = getchar();

}

while (isdigit(ch))

x = x * 10 + ch - '0', ch = getchar();

return x * f;

}

int n, k;

char s1[MAXN];

char s2[MAXN];

int dp2[2][MAXN];

int dp1[2];

int main() {

scanf("%s", s1 + 1);

n = strlen(s1 + 1);

scanf("%s", s2 + 1);

k = read();

int now = 0;

dp1[now] = 1;

inc(i, 2, n) dp2[now][i] = 1;

inc(i, 1, k) {

inc(j, 1, n) {

int x = (dp1[now] - dp2[now][j] + mod) % mod;

dp1[now ^ 1] += x;

dp1[now ^ 1] %= mod;

dp2[now ^ 1][j] += x;

dp2[now ^ 1][j] %= mod;

}

dp1[now] = 0;

inc(j, 1, n) dp2[now][j] = 0;

now ^= 1;

}

inc(i, n + 1, 2 * n) s1[i] = s1[i - n];

ll ans = 0;

inc(i, 1, n) {

bool flag = 0;

inc(j, 1, n) if (s1[i + j - 1] != s2[j]) {

flag = 1;

break;

}

if (!flag)

ans += (dp1[now] - dp2[now][i] + mod) % mod, ans %= mod;

}

printf("%lld\n", ans);

return 0;

}

1.4.2 选角色

【题目描述】

牛牛任职于一家演艺公司