c++ T318744 石头剪子布

Question

石头剪子布

题目描述

Alice 和 Bob 在玩石头剪刀布，他们每个人写出一个序列。
Alice 写出了 $n$ 个数，Bob 写出了 $n$ 个数。

其中 $0$ 代表石头，$1$ 代表剪刀，$2$ 代表布，$0$ 胜 $1$，$1$ 赢 $2$，$2$ 胜 $0$。

他们总共进行 $k$ 轮游戏，第一轮选择第一个数字，后面每一轮两个人都选择序列的下一个数进行比赛（序列结尾的下一个位置在序列开头）。

一个人的积分为其赢的次数加上额外积分。

额外积分：对于每一个 $[1,k-x+1]$ 内的正整数 $i$，满足某人从第 $i$ 轮到第 $i+x-1$ 轮都赢，都会让这个人获得 $1$ 的额外积分。

问 Alice 和 Bob 每人积分是多少。

输入格式

第一行三个数 $n,k,x$。

第二行 $n$ 个不大于 $2$ 的非负整数。

第三行 $n$ 个不大于 $2$ 的非负整数。

输出格式

一行两个整数表示 Alice 和 Bob 每人积分。

样例 #1

样例输入 #1

5 10 2
1 1 0 2 0
1 0 2 2 0

样例输出 #1

0 6

提示

对于其中 $20%$ 的数据，$n,k\le1000,x=n+1$。

对于另外 $20%$ 的数据，$x=n+1$。

对于另外 $20%$ 的数据，$k\le500000$。

对于全部数据：$1\le n\le500000，1\le k,x\le1000000000000000000$。

#include <iostream>

using namespace std;

int main() {
    return 0;
}

Answer 1

这是一道复杂的算法问题，需要使用动态规划和前缀和技术来解决。以下是一个可能的解决方案：

首先，我们需要创建一个数组来存储 Alice 和 Bob 的序列，并且将这两个序列扩展到 k 个元素，以便我们可以方便地进行比较。

然后，我们需要创建一个二维数组 dp，其中 dp[i][j] 表示在前 i 轮中，Alice 获得 j 分的情况数量。我们可以通过比较 Alice 和 Bob 在每一轮中的选择来更新这个数组。

接着，我们需要创建一个前缀和数组 prefix，其中 prefix[i] 表示 dp 数组中前 i 个元素的和。我们可以通过遍历 dp 数组来计算这个数组。

最后，我们可以通过遍历 dp 数组和 prefix 数组，计算出 Alice 和 Bob 在每一轮中的得分，并将这些得分累加起来，得到最后的结果。

以下是一个可能的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10, mod = 1e9 + 7;
int n, k, x, a[N], b[N], c[N], d[N], e[N], f[N], g[N], h[N], dp[2][N], s[N];
int main() {
    cin >> n >> k >> x;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= k; i++) c[i] = a[(i - 1) % n + 1], d[i] = b[(i - 1) % n + 1];
    for(int i = 1; i <= k; i++) {
        e[i] = e[i - 1] + (c[i] - d[i] + 3) % 3 - 1;
        f[i] = f[i - 1] + (d[i] - c[i] + 3) % 3 - 1;
    }
    for(int i = 1; i <= k; i++) g[i] = g[i - 1] + ((c[i] - d[i] + 3) % 3 == 1), h[i] = h[i - 1] + ((d[i] - c[i] + 3) % 3 == 1);
    dp[0][0] = 1;
    for(int i = 1; i <= k; i++) {
        int t = i & 1;
        for(int j = 0; j <= i; j++) {
            dp[t][j] = s[j];
            if(j >= e[i] + 1) dp[t][j] = (dp[t][j] - s[j - e[i] - 1] + mod) % mod;
        }
        for(int j = 0; j <= i; j++) s[j] = (s[j - 1] + dp[t ^ 1][j]) % mod;
    }
    ll ans1 = 0, ans2 = 0;
    for(int i = 0; i <= k; i++) ans1 = (ans1 + 1ll * dp[k & 1][i] * max(0, g[k] - max(i - x + 1, 0))) % mod;
    fill(s, s + N, 0);
    dp[0][0] = 1;
    for(int i = 1; i <= k; i++) {
        int t = i & 1;
        for(int j = 0; j <= i; j++) {
            dp[t][j] = s[j];
            if(j >= f[i] + 1) dp[t][j] = (dp[t][j] - s[j - f[i] - 1] + mod) % mod;
        }
        for(int j = 0; j <= i; j++) s[j] = (s[j - 1] + dp[t ^ 1][j]) % mod;
    }
    for(int i = 0; i <= k; i++) ans2 = (ans2 + 1ll * dp[k & 1][i] * max(0, h[k] - max(i - x + 1, 0))) % mod;
    cout << ans1 << ' ' << ans2 << endl;
    return 0;
}

这个代码的时间复杂度是 O(k*n)，空间复杂度是 O(n)。