[ABC258E] Packing Potatoes Solution

更好的阅读体验戳此进入

题面

给定序列 $W$$W$，下标范围为 $[0,n-1]$$[0, n - 1]$。存在一个长度为 ${10}^{100}$$10^{100}$ 的土豆序列，循环节为 $n$$n$，第 $i$$i$ 个土豆的重量为 $W_{(i-1)modn}$$W_{(i - 1) \bmod{n}}$。现在你需要用箱子装土豆，每个箱子装满则停止，即土豆重量恰好大于等于 $X$$X$ 时则停止。$Q$$Q$ 组询问求第 $k_i$$k_i$ 个箱子装了多少个土豆。

Solution

一道细节不少的找规律题。

首先不难发现，对于这个箱子，当你确定了从哪里开始装后，其最远能装到的位置也就确定了。我们考虑如何确定这个东西，不难想到做个前缀和然后二分，找到对应点开始的最长能取的长度，细节较多，如需要注意若长度仅为一初值需要判断。因为可能转回去所以可以将序列复制一份然后在这上面跑即可。

此时仍需要注意 $X$$X$ 可能很大以至于横跨多段，此处需要记录。此时我们即有 $nxt$$nxt$ 数组表示从该点开始取完土豆之后下一次需要从哪开始取。不难发现每个点有且仅有一条出边，则一定会成环，我们找到从 $1$$1$ 开始多少步后进入环，以及环长和每个位置的元素，最后对于每个询问判断一下是否进入环，未进入则直接调用，进入了则模一下找对应位置。中间细节很多，这道题本身的难度也就在细节上了，具体可以看代码。

复杂度卡在预处理上，最终复杂度 $O(n\log n)$$O(n \log n)$。

Code

xxxxxxxxxx
91
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, Q, X;
26
int W[410000];
27
ll sum[410000];
28
int nxt[210000];
29
ll siz[210000];
30
ll lftans(0);
31
bitset < 210000 > vis;
32
int pos[210000];
33
int mark[210000];
34
int pre[210000];
35

36
int main(){
37
    // freopen("in.txt", "r", stdin);
38
    N = read(), Q = read(), X = read();
39
    for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + (W[i] = read());
40
    copy(W + 1, W + N + 1, W + N + 1);
41
    for(int i = N + 1; i <= N << 1; ++i)sum[i] = sum[i - 1] + W[i];
42
    ll tot = sum[N];
43
    lftans += ll(X / tot) * N;
44
    X %= tot;
45
    if(!X)lftans -= N, X += tot;
46
    for(int i = 1; i <= N; ++i){
47
        int l = i, r = N << 1, ans(i - 1);
48
        while(l <= r){
49
            int mid = (l + r) >> 1;
50
            if(sum[mid] - sum[i - 1] < X)ans = mid, l = mid + 1;
51
            else r = mid - 1;
52
        }nxt[i] = ans += 2;
53
        siz[i] = lftans + (nxt[i] - i);
54
        if(nxt[i] > N)nxt[i] -= N;
55
    }
56
    queue < int > path;
57
    int cur = 1, len = 0;
58
    while(!vis[cur]){
59
        path.push(cur);
60
        vis[cur] = true;
61
        mark[++len] = cur;
62
        cur = nxt[cur];
63
    }int cnt(0);
64
    while(path.front() != cur)pre[++cnt] = path.front(), path.pop();
65
    len = 0;
66
    while(!path.empty())pos[++len] = path.front(), path.pop();
67
    pos[0] = pos[len];
68
    while(Q--){
69
        ll K = read < ll >();
70
        if(K <= cnt)printf("%lld\n", siz[pre[K]]);
71
        else printf("%lld\n", siz[pos[(K - cnt) % len]]);
72
    }
73
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
74
    return 0;
75
}
76

77
template < typename T >
78
inline T read(void){
79
    T ret(0);
80
    int flag(1);
81
    char c = getchar();
82
    while(c != '-' && !isdigit(c))c = getchar();
83
    if(c == '-')flag = -1, c = getchar();
84
    while(isdigit(c)){
85
        ret *= 10;
86
        ret += int(c - '0');
87
        c = getchar();
88
    }
89
    ret *= flag;
90
    return ret;
91
}

UPD

update-2022_12_13 初稿