百度4.11 笔试AK代码

提前15分钟AK了。难度确实不低。

第一题

阅读理解题，就不说了。

/*
阅读理解题，简单
*/
/*
阅读理解题，简单
*/
#include <iostream>
#include <algorithm>

using namespace std;

constexpr int N = 1005;

int q[N];
int p[N];
int n, m;
int t;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i) cin >> p[i];
        for (int i = 0; i < m; ++i) cin >> q[i];
        sort(q, q + m);
        for (int i = 0; i < n; ++i) {
            int tmp = lower_bound(q, q + m, p[i]) - q;
            tmp = m - tmp;
            cout << tmp << ' ';
        }
        cout << '\n';
    }

    return 0;
}

第二题

并查集维护信息，有一定难度。

/*
n个人，编号为1， 2， 。。。， n
每个人一开始单独成一直队。
现在有m次操作，操作分为两类：
1. 将某一队的人保持原有的顺序放到另一队的后面
2. 查询两个人是否在一个队里，如果在的话，输出这两个人直接隔了多少人，如果不在的话，输出-1
n <= 1e5
m <= 1e6
时间：2s
思路：
用并查集维护各种信息，
记录每个人离其所在队伍的第一个人的距离。
*/
#include 
using namespace std;
int n, m;
constexpr int N = 1e5 + 5;
int fa[N];
int dis[N];
int sz[N];
int find(int a) {
    if (a == fa[a]) return a;
    else {
        find(fa[a]);
        dis[a] += dis[fa[a]];
        fa[a] = fa[fa[a]];
        return fa[a];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        sz[i] = 1;
    }
    char op;
    int a, b;
    while  (m --) {
        cin >> op >> a >> b;
        if (op == 'C') {
            fa[a] = b;
            dis[a] = sz[b];
            sz[b] += sz[a];
        } else {
            if (ffa  != ffb) cout << -1 << '\n';
            else {
                cout << max(abs(dis[a] - dis[b]) - 1, 0)<< '\n';
            }
        }
    }
    return 0;
}

第三题

动态规划，确实挺难的。

/*
给定字符串S和T，长度相同。一次操作的定义如下：
1. 将S划分为两个非空的子串xy
2. 将x, y 交换位置，组成新的S为yx.
给定操作次数k，问存在多少中方式使得对S做k次上述操作后，得到字符串T。
两个操作序列不同，当且仅当存在一个i >= 1 && i <= k,
第一个序列划分得到的子串为x1, y1, 第二个序列划分得到的子串为x2, y2. 且x1 != x2。
2 <= len(S) == len(T) <= 1000
1 <= k <= 100000
时间：2s.
样例：
输入：
    aaca
    caaa
    2
输出：
    2
输入：
    ac
    ca
    2
输出：
    0
解题思路：
这是个字符串循环移位的问题。
定义状态dp[i][j] 表示i次操作后，移动的总的位置对n取模为j的方法数。
然后就可以转移了。观察规律，维护上一时刻所有余数结果的和，那么就可以在O(1)进行转移。
*/
#include 
using namespace std;
string s, t;
int k;
constexpr int N = 1e3 + 5;
long long dp[2][N];
long long S[2];
constexpr int MOD = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> s >> t >> k;
    const int n = s.size();
    for (int i = 1; i <= n - 1; ++i) dp[1][i] = 1;
    S[1] = n - 1;
    for (int i = 2; i <= k; ++i) {
        S[i & 1] = 0;
        for (int j = 0; j < n; ++j) {
            dp[i & 1][j] = S[(i + 1) & 1] - dp[(i + 1) & 1][j];
            dp[i & 1][j] = ((dp[i & 1][j] % MOD) + MOD) % MOD;
            S[i & 1] += dp[i & 1][j];
            S[i & 1] %= MOD;
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        if (s.substr(i, n - i) + s.substr(0, i) == t) {
            ans += dp[k & 1][i];
            ans %= MOD;
        }
    }
    cout << ans;
    return 0;
}

#笔试题目##百度#