HDU6444 Neko’s loop

前言

老师的速度训练原来都是大学生网络选拔赛的题目,比多校良心好多啊…

题目描述

分析

显然从某个给定点出发,走到的点都是确定的。设走到的所以点的集合为S,显然,S_iS_j两个集合,要么S_i=S_j,要么S_i \cap S_j=\varnothing。那么我们可以把这些集合一个一个剥离出来,然后分开处理。对于每个集合,我们最多能走m步,我们先考虑集合中走到的点\sum A_i>0的时候,这样由两种情况:

  • \frac {m} {|S|}个循环,剩下还可以再走m\space mod\space |S|
  • \frac {m} {|S|} – 1个循环,剩下还可以走至少|S|

为什么会有第二种情况呢?仔细想一下,可能会由一个很大的负数,使得一个循环的和变得很小;但是如果我们执意要走到\frac {m} {|S|}个循环,后面可能还能走的步数很少,得到的和不多,我们不妨退一个循环,这样我们剩下可以走的步数就多,当然,我们只需要知道我们至少能走|S|步,就没有任何问题了。
对于后面剩下的步数,就相当于在环上做有长度限制的最大连续子段和,类似于“滑动窗口”,我们用一个单调队列维护即可。
那么当\sum A_i\le 0时,我们就像上面一样维护最大长度为|S|的最大连续子段和即可。

参考程序

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long LL;
const int MAXN = 1e4 + 5;

LL S, P[MAXN << 1];
int T, N, M, K, A[MAXN];
bool vis[MAXN];

void solve();
LL max_sum(int lim, int len);

int main() {
    scanf("%d", &T);
    for (int k = 1; k <= T; k++) {
        printf("Case #%d: ", k);
        solve();
    }
    return 0;
}

void solve() {
    scanf("%d%lld%d%d", &N, &S, &M, &K);
    int i, j, len;
    LL sum, ans;
    for (i = 0; i < N; i++) scanf("%d", &A[i]);
    memset(vis, 0, sizeof vis);
    for (P[0] = ans = i = 0; i < N; i++)
        if (!vis[i]) {
            for (j = i, len = 0; !vis[j]; j = (j + K) % N) vis[j] = true, P[++len] = A[j];
            for (j = 1, sum = 0; j <= len; j++) sum += (P[j + len] = P[j]);     // 对于环上问题经典的手段就是复制一份在后面
            for (j = 1; j <= len * 2; j++) P[j] += P[j - 1];    // 求前缀和
            if (sum <= 0) ans = std::max(ans, max_sum(len, len << 1));
            else ans = std::max(ans, std::max(M / len * sum + max_sum(M % len, len << 1), std::max(0, M / len - 1) * sum + max_sum(len, len << 1)));
        }
    printf("%lld\n", std::max(0LL, S - ans));
}

LL max_sum(int lim, int len) {  // 求长度为len的序列P中,最大长为lim的最大连续子段和
    if (!lim) return 0;
    LL res = 0;
    std::deque<int> Que;    // 双端队列
    Que.push_back(0);
    for (int i = 1; i <= len; i++) {
        while (!Que.empty() && i - Que.front() > lim) Que.pop_front();
        while (!Que.empty() && P[Que.back()] > P[i]) Que.pop_back();
        Que.push_back(i);
        res = std::max(res, P[i] - P[Que.front()]); // 注意这里维护的front()实际上是子段最前面一个点的再前面一个位置,而不是像计算前缀和一样front()-1!这样就与维护的信息不相符,显然会出错。(感谢GJC大佬指出)
    }
    return res;
}

总结

这题最终的复杂度很低,因此会给人一种错觉。主要就是发现性质之后,如何在给定步数内走出最大的价值这个决策的推理。当然,后面求环上最大连续子段和容易想我这样脑抽…算是一些细节问题吧。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注