2026 杭电春季联赛 3——1007-扑克牌（在环上跑这个滑动窗口）

题目大意

题目背景与目标
有 $n$ 张牌从上至下组成的牌堆，每张牌上有一个点数 $a_i$。共有 $m$ 名玩家按 $1, 2, \dots, m$ 的顺序依次循环摸牌。玩家 $k$ 作为游戏组织者，在所有人开始摸牌之前，可以进行至多一次切牌操作（即将牌堆从任意位置分为上下两部分，并交换这两部分的位置）。目标是求出玩家 $k$ 通过合理切牌，最终自己摸到的牌的点数总和的最大值。

输入格式
第一行包含一个整数 $T$，表示测试用例的数量。
每组数据包含两行：
第一行输入三个正整数 $n, m, k$，分别代表牌的总数、玩家的总数以及目标玩家的顺位。
第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，自顶向下给出牌堆中每张牌的点数。

输出格式
对于每组数据，输出一行一个整数，表示玩家 $k$ 可以获得的最大点数和。

样例输入

2
2 2 1
114514 1919810
3 1 1
1 -3 2

样例输出

1919810
0

样例解释第一组样例：牌堆共 $2$ 张牌，有 $2$ 名玩家，主角是第 $1$ 名玩家。初始牌堆点数为 114514, 1919810。主角可以通过切牌操作，将上面的第一张牌移到最下方，得到新牌堆 1919810, 114514。开始发牌后，主角作为第 $1$ 名玩家摸走第一张牌，获得最大点数 $1919810$。
第二组样例：牌堆共 $3$ 张牌，只有 $1$ 名玩家，主角是第 $1$ 名玩家。无论主角在开始前如何切牌，因为只有他一个人玩，他都会摸走所有的牌。因此他获得的总点数固定为 $1 - 3 + 2 = 0$。

思路讲解

gemini

题目描述

给定一个包含 $n$ 张牌的牌堆，每张牌有点数 $a_i$。有 $m$ 个玩家依次循环摸牌（即玩家 $1$ 摸第 $1$ 张，玩家 $2$ 摸第 $2$ 张，……，玩家 $m$ 摸第 $m$ 张，然后玩家 $1$ 再摸第 $m+1$ 张，以此类推），直到牌摸完。
玩家 $k$ 可以在摸牌前进行最多一次操作：将牌堆从任意位置切开，交换上下两部分。这等价于对数组进行任意次数的循环移位。
求玩家 $k$ 能摸到的牌的点数总和的最大值。

解题思路

首先分析玩家 $k$ 摸到的牌的数量和位置。
由于牌是按照 $1$ 到 $m$ 循环分发的，在洗牌（循环移位）后的新牌堆中，玩家 $k$ 必定摸走下标为 $k, k+m, k+2m, \dots$ 的牌（下标从 $1$ 开始）。
因为牌堆总数为 $n$，所以玩家 $k$ 摸到的牌的数量始终为定值 $C = \lfloor \frac{n-k}{m} \rfloor + 1$。
无论我们将原牌堆循环移位多少次，新牌堆中下标相邻为 $m$ 的位置，在原牌堆中它们的下标差值也必定是 $m \pmod n$。
因此，玩家 $k$ 摸到的 $C$ 张牌，在原数组中恰好对应了一条从某个起点开始、每次下标加上 $m \pmod n$、长度为 $C$ 的路径。
这提示我们将原数组的下标视为一个图，每个下标 $i$ 向 $(i+m) \bmod n$ 连边。
根据数论性质，这个图由 $g = \gcd(n, m)$ 个不相交的环构成，每个环的长度为 $L = \frac{n}{g}$。
由于循环移位的偏移量 $s$ 可以取 $0$ 到 $n-1$ 中的任意整数，路径的起点可以取遍所有 $n$ 个位置。
所以，问题转化为：在这 $g$ 个环中，寻找所有长度恰好为 $C$ 的连续子段，求出其中点数总和的最大值。
算法步骤如下：

1. 计算环的个数 $g = \gcd(n, m)$，环长 $L = \frac{n}{g}$，以及子段长度 $C = \lfloor \frac{n-k}{m} \rfloor + 1$。
2. 枚举 $i \in [0, g-1]$，遍历这 $g$ 个环。
3. 对于每个环，按 $i, (i+m) \bmod n, (i+2m) \bmod n, \dots$ 的顺序提取出环上的 $L$ 个元素。
4. 在提取出的环上，使用滑动窗口算法求出长度为 $C$ 的最大连续子段和。注意环的连续性，滑动窗口在末尾时需要绕回开头。
5. 在所有环的所有长度为 $C$ 的子段和中取最大值即为答案。
   经过证明可以发现，窗口长度 $C$ 始终满足 $C \le L$，因此滑动窗口的长度绝不会超出环的单圈长度。

代码实现

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 求最大公约数
long long get_gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

void solve() {
    long long n, m, k;
    if (!(cin >> n >> m >> k)) return;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    long long g = get_gcd(n, m);
    long long L = n / g;
    long long C = (n - k) / m + 1;

    long long ans = -2e18; // 初始化为极小值

    // 枚举每一个环的起点
    for (int i = 0; i < g; ++i) {
        vector<long long> cycle;
        cycle.reserve(L);
        long long curr = i;

        // 提取当前环上的所有元素
        do {
            cycle.push_back(a[curr]);
            curr = (curr + m) % n;
        } while (curr != i);

        // 使用滑动窗口计算该环上长度为 C 的最大连续子段和
        long long current_sum = 0;
        for (int j = 0; j < C; ++j) {
            current_sum += cycle[j];
        }

        long long max_sum = current_sum;
        for (int j = 1; j < L; ++j) {
            current_sum -= cycle[j - 1];
            current_sum += cycle[(j + C - 1) % L]; // 环形绕回
            if (current_sum > max_sum) {
                max_sum = current_sum;
            }
        }

        if (max_sum > ans) {
            ans = max_sum;
        }
    }

    cout << ans << "\\n";
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：求最大公约数的时间复杂度为 $\mathcal{O}(\log n)$。提取所有的环共需遍历所有元素一遍，耗时 $\mathcal{O}(n)$。在长度为 $L$ 的环上运行滑动窗口也需要 $\mathcal{O}(L)$ 的时间，所有环总计耗时 $\mathcal{O}(n)$。因此单组测试用例的时间复杂度为 $\mathcal{O}(n)$。由于题目保证 $\sum n \le 2 \times 10^5$，整体时间复杂度为 $\mathcal{O}(\sum n)$，能够非常轻松地通过时间限制。
• 空间复杂度：存储数组以及构造环形结构使用的额外 vector 所占空间均为 $\mathcal{O}(n)$，空间复杂度为 $\mathcal{O}(n)$，完全符合 $256 \text{ MB}$ 的限制。
• 边界情况：
  • $k=n$ 等玩家抽牌数极少的情况已由 $C$ 的计算式自然涵盖，此时 $C=1$。
  • 当 $m=1$ 时，$g=1$，此时退化为只有一条长为 $n$ 的大环，算法依然正确。
  • 数组中存在大量负数时，初始化 ans = -2e18 防止了将负答案误判为 $0$ 的漏洞。

其实这道题目的思路说起来也很简单，就是在一个环上跑这个滑动窗口。

这个切牌其实可以看作循环位移操作。

然后，需要注意到的就是，无论你怎么切牌，第 k 个玩家所能吃到的牌的数量是不变的（也就是代码中的 cnt_k ）

因此，我们是用 2N 技巧，在这个 2N 上模拟环，进行一个滑动窗口，就好了。

for (ll i = K - 1; i < N; i += M) {
    cnt_k++;
    ans += A[i];
}
for (int i = 0; i < M; ++i) {
    ll lans = 0;
    ll cnt_i = 0;
    queue<ll> q;
    for (ll j = i; j < 2 * N; j += M) {
        lans += A[j];
        q.push(A[j]);
        if (SZ(q) == cnt_k) {
            ans = max(ans, lans);
        }
        if (SZ(q) > cnt_k) {
            lans -= q.front();
            q.pop();
            ans = max(ans, lans);
        }
    }
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=8833

源代码

// teamname: Gospel_rock
/**
 * Problem: 扑克牌
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1199&pid=1007
 * Created: 2026-04-03 19:25:47
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
    ll N, M, K;
    vector<ll> A;
    // vector<ll> dp;

    Solve() {
        cin >> N >> M >> K;
        A.resize(2 * N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }
        for (int i = 0; i < N; ++i) {
            A[i + N] = A[i];
        }
        ll cnt_k = 0;
        ll ans = 0;
        for (ll i = K - 1; i < N; i += M) {
            cnt_k++;
            ans += A[i];
        }
        for (int i = 0; i < M; ++i) {
            ll lans = 0;
            ll cnt_i = 0;
            queue<ll> q;
            for (ll j = i; j < 2 * N; j += M) {
                lans += A[j];
                // #ifdef LOCAL
                //                 debug(j);
                //                 debug(A[j]);
                // #endif
                q.push(A[j]);
                if (SZ(q) == cnt_k) {
                    ans = max(ans, lans);
                }
                if (SZ(q) > cnt_k) {
                    lans -= q.front();
                    q.pop();
                    ans = max(ans, lans);
                }
            }
        }

        cout << ans << "\n";
        // A.resize(2 * N + 2);
        // for (int i = 1; i <= N; ++i) {
        //     cin >> A[i];
        // }
        // for (int i = N + 1; i <= 2 * N; ++i) {
        //     A[i] = A[i - N];
        // }
        // dp.resize();
        // for (int i = 1; i <= N; ++i) {
        //
        // }
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve solve;
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=8833

*/

心路历程（WA，TLE，MLE……）