AtCoder Beginner Contest 258 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abcd 跳了

[ABC258E] Packing Potatoes

题面

给定序列 $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
}

[ABC258F] Main Street

题面

你要在平面直角坐标系中行走，每一步可以上下左右四个方向任意移动 $1$$1$，耗时 $k$$k$ 秒。特别地，存在若干条快速通道，若该步起点和终点均满足 $x\equiv 0(\mathrm{mod}B)$$x \equiv 0 \pmod{B}$ 或 $y\equiv 0(\mathrm{mod}B)$$y \equiv 0 \pmod{B}$，则认为该步是在快速通道上进行，仅需耗时 $1$$1$ 秒。询问从 $(S_x,S_y)$$(S_x, S_y)$ 到 $(G_x,G_y)$$(G_x, G_y)$ 最少需要多少秒。存在多组数据。

Solution

显然可以选择直接走，或者走到起点附近的某个快速通道即终点附近的某个快速通道，共有 $4\times 4+1=17$$4 \times 4 + 1 = 17$ 中方案，枚举计算取一下最小值即可。

Code

xxxxxxxxxx
1
79
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 B, K;
26
int Sx, Sy, Tx, Ty;
27

28
int main(){
29
    int T = read();
30
    while(T--){
31
        B = read(), K = read();
32
        Sx = read(), Sy = read(), Tx = read(), Ty = read();
33
        pair < int, int > S[10] = {
34
            {0, 0},
35
            {Sx / B * B, Sy},
36
            {Sx, int(ceil((double)Sy / B)) * B},
37
            {int(ceil((double)Sx / B)) * B, Sy},
38
            {Sx, Sy / B * B}
39
        };
40
        pair < int, int > T[10] = {
41
            {0, 0},
42
            {Tx / B * B, Ty},
43
            {Tx, int(ceil((double)Ty / B)) * B},
44
            {int(ceil((double)Tx / B)) * B, Ty},
45
            {Tx, Ty / B * B}
46
        };
47
        ll ans = ll(abs(Sx - Tx) + abs(Sy - Ty)) * K;
48
        for(int s = 1; s <= 4; ++s)
49
            for(int t = 1; t <= 4; ++t)
50
                ans = min(
51
                    ans,
52
                    abs(S[s].first - T[t].first) + abs(S[s].second - T[t].second) +
53
                    (
54
                        (ll)(abs(S[s].first - Sx) + abs(S[s].second - Sy)) * K +
55
                        (ll)(abs(T[t].first - Tx) + abs(T[t].second - Ty)) * K
56
                    )
57
                );
58
        printf("%lld\n", ans);
59
    }
60

61
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
62
    return 0;
63
}
64

65
template < typename T >
66
inline T read(void){
67
    T ret(0);
68
    int flag(1);
69
    char c = getchar();
70
    while(c != '-' && !isdigit(c))c = getchar();
71
    if(c == '-')flag = -1, c = getchar();
72
    while(isdigit(c)){
73
        ret *= 10;
74
        ret += int(c - '0');
75
        c = getchar();
76
    }
77
    ret *= flag;
78
    return ret;
79
}

[ABC258G] Triangle

题面

给你一个简单的无向图，其中有 $N$$N$ 个顶点。用一个 的 $N\times N$$N\times N$ 邻接矩阵 $A$$A$ 来表示。如果 $A_{i,j}=1$$A_{i,j}=1$ ,则表示 $i$$i$ 到 $j$$j$ 有边相连，如果 $A_{i,j}=0$$A_{i,j}=0$ ,则表示 $i$$i$ 到 $j$$j$ 无边相连。

求三角形 $(i,j,k)$$(i,j,k)$ 的个数，满足 $1\le i<j<k\le n$$1\leq i < j < k\leq n$，且 $i$$i$ 与 $j$$j$ 有边相连，$i$$i$ 与 $k$$k$ 有边相连，$j$$j$ 与 $k$$k$ 有边相连。

Solution

枚举 $i,j$$i, j$，然后 $k$$k$ 可以通过 bitset 优化，最终复杂度 $O({\displaystyle \frac{n^3}{w}})$$O(\dfrac{n^3}{w})$。记得需要把邻接矩阵重复部分去掉。

Code

x
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;
26
ll ans(0);
27
bitset < 3100 > G[3100];
28

29
int main(){
30
    N = read();
31
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j){
32
        char c = getchar(); while(!isdigit(c))c = getchar();
33
        G[i][j] = c == '1' && j > i ? true : false;
34
    }
35
    for(int i = 1; i <= N; ++i)for(int j = i + 1; j <= N; ++j)
36
        if(G[i][j])ans += (G[i] & G[j]).count();
37
    printf("%lld\n", ans);
38
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
39
    return 0;
40
}
41

42
template < typename T >
43
inline T read(void){
44
    T ret(0);
45
    int flag(1);
46
    char c = getchar();
47
    while(c != '-' && !isdigit(c))c = getchar();
48
    if(c == '-')flag = -1, c = getchar();
49
    while(isdigit(c)){
50
        ret *= 10;
51
        ret += int(c - '0');
52
        c = getchar();
53
    }
54
    ret *= flag;
55
    return ret;
56
}

[ABC258Ex] Odd Steps

题面

给定 $n,S$$n, S$ 和序列 $A_n$$A_n$，求任意长度的满足以下条件的序列个数：

• 仅由奇数组成。
• 所有数之和为 $S$$S$。
• 序列的任意前缀和均不能为 $A_n$$A_n$ 中任意数。

答案对 $998244353$$998244353$ 取模。

Solution

首先不考虑最后一个限制，则不难想到 DP，即设 $dp(i)$$dp(i)$ 表示和为 $i$$i$ 的合法序列个数，显然有转移：

然后发现转移为 $O(S^2)$$O(S^2)$ 无法通过，但显然可以通过前缀和优化，即：

边界为 $dp(0)=1$$dp(0) = 1$。

然后复杂度是 $O(S)$$O(S)$ 的，无法通过，但显然可以通过矩阵优化：

矩阵快速幂优化即可。

然后对于第三个限制，我们只需要在维护的时候分段维护即可，每次维护到对应的 $A_i$$A_i$，然后令该次 $dp(A_i)=0$$dp(A_i) = 0$，再接着转移下去即可。

最终复杂度 $O(3^{3}n\log S)$$O(3^3 n \log S)$。

Code

xxxxxxxxxx
1
82
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
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N;
28
ll S;
29
ll P[110000];
30

31
class Matrix3{
32
private:
33
public:
34
    ll v[3][3];
35
    Matrix3(ll v11 = 0, ll v12 = 0, ll v13 = 0, ll v21 = 0, ll v22 = 0, ll v23 = 0, ll v31 = 0, ll v32 = 0, ll v33 = 0){
36
        v[0][0] = v11, v[0][1] = v12, v[0][2] = v13,
37
        v[1][0] = v21, v[1][1] = v22, v[1][2] = v23,
38
        v[2][0] = v31, v[2][1] = v32, v[2][2] = v33;
39
    }
40
    friend const Matrix3 operator * (const Matrix3 &a, const Matrix3 &b){
41
        Matrix3 ret;
42
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)for(int k = 0; k <= 2; ++k)
43
            (ret.v[i][j] += a.v[i][k] * b.v[k][j] % MOD) %= MOD;
44
        return ret;
45
    }
46
    friend const Matrix3 operator ^ (const Matrix3 &a, ll b){
47
        Matrix3 ret(1, 0, 0, 0, 1, 0, 0, 0, 1), mul(a);
48
        while(b){
49
            if(b & 1)ret = ret * mul;
50
            b >>= 1;
51
            mul = mul * mul;
52
        }return ret;
53
    }
54
};
55

56
int main(){
57
    N = read(), S = read < ll >();
58
    for(int i = 1; i <= N; ++i)P[i] = read < ll >();
59
    Matrix3 base(1, 1, 0, 0, 0, 1, 1, 1, 0);
60
    Matrix3 ans(1, 0, 0);
61
    for(int i = 1; i <= N; ++i)ans = ans * (base ^ (P[i] - P[i - 1])), ans.v[0][0] = 0;
62
    ans = ans * (base ^ (S - P[N]));
63
    printf("%lld\n", ans.v[0][0]);
64
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
65
    return 0;
66
}
67

68
template < typename T >
69
inline T read(void){
70
    T ret(0);
71
    int flag(1);
72
    char c = getchar();
73
    while(c != '-' && !isdigit(c))c = getchar();
74
    if(c == '-')flag = -1, c = getchar();
75
    while(isdigit(c)){
76
        ret *= 10;
77
        ret += int(c - '0');
78
        c = getchar();
79
    }
80
    ret *= flag;
81
    return ret;
82
}

UPD

update-2022_12_17 初稿