美团春招第一轮笔试题，只通过3.45，好难。。。

只通过了3.45.。。。。搞不懂啊。。。希望大佬们可以补充，指点下。。

美团 0312 笔试

1. 两行长度均为 n 字符串，仅包含字符'X`(代表障碍物)和'.'(可以通行)，初始在左上角(1, 1)，想到右下角(2, n)去，求方案数，如果不能到(2, n) 输出-1。数据范围：。

通过 45%，搞不懂。

#include <bits/stdc++.h>
using namespace std;

int n;
long long dp[2][5500];
string str[2];

int main() {
    cin >> n;
    cin >> str[0] >> str[1];
    if (str[0][0] == 'X') {
        cout << -1 << endl;
        return 0;
    }
    dp[0][0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 2; ++j)if (str[j][i] == '.') {
            dp[j][i] = dp[j][i-1] + dp[j^1][i-1];
        }
    }
    if (dp[1][n-1] == 0) dp[1][n-1] = -1;
    cout << dp[1][n-1] << endl;
    return 0;
}

2. 一个包含 n 个元素的数组，每个元素值是[L, R]的范围内的，求满足 n 个元素之和是 k 的倍数的数组个数。数据范围：。

用 dp[i][j] 表示和模 k 后是 j 的长度为 i 的数组个数。需要先算下[L, R] 中 模 k 后是 j 的数字个数：num[j] = (R-j)/k - (L-1-j)/k。时间复杂度：。

代码没保存。100%通过。

3. 长度为 n 的数组和一个 x，可以让 x 和数组中任意数字或操作替代原来的数字，这个操作可以进行任意次。求最终数组众数的最大值。数据范围：

用 cnt[p]表示最终数组中数字 p 的数字个数。首先 cnt[data[i]]++，如果 data[i] != x，则 cnt[x | data[i]]++，最后遍历一遍 cnt 数组即可。

100%通过。

4. 一个 n 个节点 m 条无向边的图，保证图连通，第 i 个节点的标记是 id[i]，想要从每个节点出发收集 k 种不同的 id，求每个节点需要的最短路径和。数据范围。

思路：从 1 到 k 枚举每个 id，计算每个节点需要的路径长度。假设当前计算的 id 是 p，则把所有标记是 p 的节点放进队列里，然后 bfs 计算。时间复杂度：。

只通过 55%，搞不懂。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, KK = 110;

int n, m, K;
int dp[N][KK], idx[N];
vector<int> G[N];

void solve(int k) {
    queue<int> Q;
    for (int i = 1; i <= n; ++i) if (idx[i] == k) {
        Q.push(i);
    }
    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (auto v: G[cur]) if (dp[v][k] == 0x3f3f3f3f) {
            dp[v][k] = dp[cur][k] + 1;
            Q.push(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> K;
    for (int i = 1; i <= n; ++i) cin >> idx[i];
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    memset(dp, 0x3f, sizeof (dp));
    for (int i = 1; i <= n; ++i) dp[i][idx[i]] = 0;

    for (int k = 1; k <= K; ++k) {
        solve(k);
    }
    for (int i = 1; i <= n; ++i) {
        int sum = 0;
        for (int k = 1; k <= K; ++k) sum += dp[i][k];
        cout << sum << " \n"[i == n];
    }
    return 0;
}

5. 射击 n 次靶子，第 i 次命中靶心的概率是，求 n 次后只脱离靶心 0 次、1 次、2 次的概率分别是多少？把最终的概率写成最简分数形式，然后对 998244353 取模。数据范围

先算逆元，然后 dp 算一下。只通过了 45%，搞不懂。请赐教。

比较尴尬的是如果把下面的代码中double st = clock();和double ed = clock() - st;不注释掉，那么会报 RE，通过率 0%，这就很尴尬了啊。。。平台有点搞不懂。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
using ll = long long;
const ll mod = 998244353;

int n;
ll data[N], inv[N], inv2[N], dp[N][3];

ll Qpow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    // double st = clock();
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> data[i];
        inv[i] = Qpow(data[i], mod-2);
        inv2[i] = (data[i] - 1) * inv[i] % mod;
    }
    dp[1][0] = inv[1];
    dp[1][1] = inv2[1];
    for (int i = 2; i <= n; ++i) {
        dp[i][0] = dp[i-1][0] * inv[i] % mod;
        dp[i][1] = (dp[i-1][0] * inv2[i] % mod + dp[i-1][1] * inv[i] % mod) % mod;
        dp[i][2] = (dp[i-1][1] * inv2[i] % mod + dp[i-1][2] * inv[i] % mod) % mod;
    }
    cout << dp[n][0] << " " << dp[n][1] << " " << dp[n][2] << endl;
    // double ed = clock() - st;
   // printf("time=%.3f\n", ed / CLOCKS_PER_SEC);
    return 0;
}