1.4 百度求职攻略-理工科版本

1.4.1 校园招聘时间流程

网申	机考	面试	offer
7月-8月	8月-9月	9月-10月	10月-12月

1.4.2 薪资爆料

岗位	地点	学历	薪资范围（年薪）
计算机图形算法研发工程师	北京	硕士	薪资面议
嵌入式Linux软件研发工程师	北京	本科	薪资面议
基础平台研发工程师	北京	本科	薪资面议
Java研发工程师	北京	本科	薪资面议
Web前端研发工程师	北京	本科	薪资面议
安全工程师	北京	本科	薪资面议

*数据来源牛客用户，更多详细信息可到牛客查询

1.4.3 面试真题

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

输出样例：

说明：

"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)

an