AtCoder Beginner Contest 270 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abc不说了（该说不说这一场前三题分类讨论是真麻

[ABC270D] Stones

题面

Takahashi 和 Aoki 在玩一个取石子的游戏。

刚开始，有 $N$$N$ 个石子，还有一个长度为 $K$$K$ 的序列 $A=\{A_1,A_2,\cdots ,A_K\}$$A = \{A_1,A_2,\cdots,A_K\}$。

现在，他们要按照以下规则轮流取石子：

• 对于每次操作，他可以选择一个 $i$$i$（$1\le i\le K$$1 \leq i \leq K$），这时他会取走 $A_i$$A_i$ 块石子。
• 当一个人没法取石子时，游戏结束。

现在，Takahashi 先取石子，Aoki 后取石子。 他们都想尽可能的最大化他们自己取走的石子数量。

若他们都以最优策略取石子，最后 Takahashi 会取走多少块石子？

Solution

开始以为是无脑贪心（主要是 D 题我以为会是很水那种

然后发现贪心是假的，就类似背包不能无脑装最大一样。所以考虑 DP，最开始想到 $dp(i,j,0/1)$$dp(i, j, 0/1)$ 表示考虑前 $i$$i$ 个石子，考虑前 $j$$j$ 个序列 $A$$A$ 考虑先手还是后手，然后一直没调出来。后来发现直接去掉 $j$$j$ 这一维然后取个 $max$$\max$ 就可以了。当然似乎直接去掉 $0/1$$0/1$ 这一维转移也是可以的。

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 void* Edge::operator new(size_t){static Edge* P = ed; 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

23

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

27
int N, K;
28
int A[110];
29
int dp[11000][2];
30
// int ans(0); bool flag(true);
31
// basic_string < int > rem;
32

33
int main(){
34
    N = read(), K = read();
35
    for(int i = 1; i <= K; ++i)A[i] = read();
36
    for(int i = 1; i <= N; ++i){
37
        for(int j = K; j >= 1; --j){
38
            if(i >= A[j])
39
                dp[i][0] = max(dp[i][0], dp[i - A[j]][1] + A[j]),
40
                dp[i][1] = i - dp[i][0];
41
            // else
42
            //     dp[i][j][0] = dp[i][1], dp[i][1] = dp[i][0];
43
        }
44
    }//int ans(0);
45
    // for(int i = 1; i <= K; ++i)ans = max(ans, dp[N][i][0]);
46
    printf("%d\n", dp[N][0]);
47
    // for(int i = 1; i <= K; ++i)rem += read();
48
    // while(!rem.empty() && N){
49
    //     while(!rem.empty() && rem.back() > N)rem.pop_back();
50
    //     if(rem.empty())break;
51
    //     ans += rem.back() * flag, flag ^= true, N -= rem.back();
52
    // }printf("%d\n", ans);
53

54

55
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
56
    return 0;
57
}
58

59
template < typename T >
60
inline T read(void){
61
    T ret(0);
62
    int flag(1);
63
    char c = getchar();
64
    while(c != '-' && !isdigit(c))c = getchar();
65
    if(c == '-')flag = -1, c = getchar();
66
    while(isdigit(c)){
67
        ret *= 10;
68
        ret += int(c - '0');
69
        c = getchar();
70
    }
71
    ret *= flag;
72
    return ret;
73
}

[ABC270E] Apple Baskets on Circle

题面

存在 $n$$n$ 个筐围成一圈，第 $i$$i$ 个有 $A_i$$A_i$ 个苹果。你需要从第 $1$$1$ 个筐开始依次拿掉一个苹果，直到拿了 $k$$k$ 个。如果筐内没有苹果那么直接拿下一个筐。求最终每个筐里还剩多少个苹果。

Solution

题解区怎么都是二分答案的做法，来一发 VP 时糊出来的更加无脑的模拟做法。

首先假设一圈里有 $k$$k$ 个篮子里有苹果，那么转一圈一定会拿走 $k$$k$ 个苹果，然后当拿空了一个篮子之后就会 $k\leftarrow k-1$$k \leftarrow k - 1$。所以我们考虑维护一下当前一共还有多少个篮子里有苹果，然后给所有 $A_i$$A_i$ 排个序，每次取最小的然后判断是否能拿空，如果可以的话那么直接拿空，否则尽量拿多圈，此时剩下的所有显然不足一圈，此时再次遍历一遍即可。

然后注意其中有一步 $cur\times v$$cur \times v$，这个东西我感觉似乎是 ${10}^{24}$$10^{24}$ 级别的，于是开了个 __int128_t。

Code

xxxxxxxxxx
60
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 void* Edge::operator new(size_t){static Edge* P = ed; 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; ll K;
26
ll A[210000];
27
priority_queue < ll, vector < ll >, greater < ll > > buc;
28

29
int main(){
30
    N = read(), K = read < ll >();
31
    ll cur(0);
32
    for(int i = 1; i <= N; ++i)if((A[i] = read < ll >()))buc.push(A[i]), ++cur;
33
    ll minus(0);
34
    while(!buc.empty()){
35
        ll v = buc.top() - minus; buc.pop();
36
        if((__int128_t)cur * v <= K)K -= cur * v, minus += v, --cur;
37
        else{minus += K / cur, K -= K / cur * cur; break;}
38
    }
39
    for(int i = 1; i <= N; ++i)A[i] = max(0ll, A[i] - minus);
40
    for(int i = 1; i <= N && K; ++i)if(A[i])--A[i], --K;
41
    for(int i = 1; i <= N; ++i)printf("%lld%c", A[i], i == N ? '\n' : ' ');
42
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
43
    return 0;
44
}
45

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

[ABC270F] Transportation

题面

有 $n$$n$ 个点，如下操作：

• 对于 $1\le i\le n$$1\le i\le n$，可以花 $x_i$$x_i$ 的贡 $i$$i$ 号点建一个机场 .
• 对于 $1\le i\le n$$1\le i\le n$，可以花 $y_i$$y_i$ 的贡献在 $i$$i$ 号点建一个港口 .
• 对于 $1\le i\le n$$1\le i\le n$，可以花 $z_i$$z_i$ 的贡献在 $a_i$$a_i$ 号点到 $b_i$$b_i$ 号点连一条无向边 .

如果两个点 $u,v$$u,v$ 满足下列条件之一，则 $u,v$$u,v$ 可以互相到达：

• $u,v$$u,v$ 都有机场 .
• $u,v$$u,v$ 都有港口 .
• $u$$u$ 到 $v$$v$ 有边 .

问至少花多少代价才能让所有点连通 .

$1\le n,m\le 2\times {10}^5$$1\le n,m\le 2\times 10^5$，$1\le x_i,y_i,z_i\le {10}^9$$1\le x_i,y_i,z_i\le 10^9$ .

Solution

考虑新建两个点，对 $n$$n$ 个点连边，边权分别为 $X_i,Y_i$$X_i, Y_i$，然后 $2^2$$2^2$ 次枚举并跑 MST 取最优即可。

Code

xxxxxxxxxx
111
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 void* Edge::operator new(size_t){static Edge* P = ed; 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

23

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

27
// struct Edge{
28
//     Edge* nxt;
29
//     int to;
30
//     ll val;
31
//     OPNEW;
32
// }ed[410000];
33
// ROPNEW;
34
// Edge* head[210000];
35

36
ll X[210000], Y[210000];
37
int N, M;
38
ll ans(LONG_LONG_MAX);
39

40
struct Edge{
41
    int s, t; ll val;
42
    friend const bool operator < (const Edge &a, const Edge &b){
43
        return a.val < b.val;
44
    }
45
};
46
basic_string < Edge > edgs, basic_edgs;
47

48
class UnionFind{
49
private:
50
    int fa[210000];
51
public:
52
    void Clear(void){for(int i = 1; i <= 201000; ++i)fa[i] = i;}
53
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
54
    void Union(int s, int t){fa[Find(s)] = fa[Find(t)];}
55
}uf;
56

57
ll MST(void){
58
    uf.Clear();
59
    ll ret(0);
60
    sort(edgs.begin(), edgs.end());
61
    for(auto e : edgs)
62
        if(uf.Find(e.s) != uf.Find(e.t))
63
            uf.Union(e.s, e.t), ret += e.val;
64
    for(int i = 1; i <= N - 1; ++i)if(uf.Find(i) != uf.Find(i + 1))return LONG_LONG_MAX;
65
    return ret;
66
}
67

68
int main(){
69
    N = read(), M = read();
70
    for(int i = 1; i <= N; ++i)X[i] = read();
71
    for(int i = 1; i <= N; ++i)Y[i] = read();
72
    for(int i = 1; i <= M; ++i){
73
        int s = read(), t = read(), v = read();
74
        // head[s] = new Edge{head[s], t, v};
75
        // head[t] = new Edge{head[t], s, v};
76
        basic_edgs += Edge{s, t, v};
77
    }edgs += basic_edgs;
78
    ans = min(ans, MST());
79
    // printf("%lld\n", ans);
80
    for(int i = 1; i <= N; ++i)edgs += Edge{i, N + 1, X[i]};
81
    ++N;
82
    ans = min(ans, MST());
83
    // printf("%lld\n", ans);
84
    edgs.clear();
85
    edgs += basic_edgs;
86
    for(int i = 1; i <= N - 1; ++i)edgs += Edge{i, N, Y[i]};
87
    ans = min(ans, MST());
88
    // printf("%lld\n", ans);
89
    for(int i = 1; i <= N - 1; ++i)edgs += Edge{i, N + 1, X[i]};
90
    ++N;
91
    ans = min(ans, MST());
92
    printf("%lld\n", ans);
93
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
94
    return 0;
95
}
96

97
template < typename T >
98
inline T read(void){
99
    T ret(0);
100
    int flag(1);
101
    char c = getchar();
102
    while(c != '-' && !isdigit(c))c = getchar();
103
    if(c == '-')flag = -1, c = getchar();
104
    while(isdigit(c)){
105
        ret *= 10;
106
        ret += int(c - '0');
107
        c = getchar();
108
    }
109
    ret *= flag;
110
    return ret;
111
}

[ABC270G] Sequence in mod P

题面

对于某个无穷序列 $\{X\}$$\{X\}$，构造如下：

求最小的 $i$$i$ 满足 $X_i=G$$X_i=G$，没有输出 -1。

多组数据，记 $T$$T$ 为数据组数，则有 $1\le T\le 100$$1\le T\le100$。

保证 $P$$P$ 是质数，$2\le P\le {10}^9$$2\le P\le10^9$。

保证 $0\le A,B,S,G<P$$0\le A,B,S,G< P$。

Solution

大概就是递推转通向，然后发现可以直接 BSGS 解决。

然后就是有一大堆特判的细节需要考虑一下。

Code

xxxxxxxxxx
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 void* Edge::operator new(size_t){static Edge* P = ed; 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
ll MOD, A, B, S, G;
26
unordered_map < ll, int > mp;
27

28
ll qpow(ll a, ll b){
29
    ll ret(1), mul(a);
30
    while(b){
31
        if(b & 1)ret = ret * mul % MOD;
32
        b >>= 1;
33
        mul = mul * mul % MOD;
34
    }return ret;
35
}
36
ll inv(ll v){return qpow(v, MOD - 2);}
37
ll BSGS(ll A, ll B){
38
    mp.clear();
39
    int lim = ceil(sqrt(MOD));
40
    ll base(1), mul(1);
41
    for(ll i = 1; i <= lim; ++i)(base *= A) %= MOD, mp[B * base % MOD] = i;
42
    for(ll i = 1; i <= lim; ++i){
43
        (mul *= base) %= MOD;
44
        if(mp.find(mul) != mp.end())return i * lim - mp[mul];
45
    }return -1;
46
}
47

48
int main(){
49
    // freopen("in.txt", "r", stdin);
50
    int T = read();
51
    while(T--){
52
        MOD = read(), A = read(), B = read(), S = read(), G = read();
53
        ll V = (G + B * inv(A - 1) % MOD) % MOD * inv((S + B * inv(A - 1) % MOD) % MOD) % MOD;
54
        if(S == G)printf("0\n");
55
        else if(!A)printf("%d\n", B == G ? 1 : -1);
56
        else if(A == 1){
57
            if(!B)printf("-1\n");
58
            else printf("%lld\n", ((G - S) * inv(B) % MOD + MOD) % MOD);
59
        }else printf("%lld\n", BSGS(A, V));
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
}

[ABC270Ex] add 1

题面

给定序列 $A_n$$A_n$，存在 $n$$n$ 个初始为 $0$$0$ 的计数器，每次可以进行如下操作：选定一个计数器使其变为 $0$$0$ 并使得其它所有计数器 $+1$$+1$。求期望的使对于每个 $i$$i$ 满足第 $i$$i$ 个计数器的数值不小于 $A_i$$A_i$ 的操作次数。对 $998244353$$998244353$ 取模。

Solution

大概是一道没有什么高端的算法，仅靠推式子的难度评黑的题。

首先我们不难想到，如果设当前计数器的值为 $C_i$$C_i$，那么我们的目的就是要满足所有 $A_i-C_i\le 0$$A_i - C_i \le 0$。

然后不太严谨地思考一下不难发现，我们每次是使除了选择的其它的计数器都加一，所以拖后腿的一定是 $max\{A_i-C_i\}$$\max\{A_i - C_i\}$，令 $k=max\{A_i-C_i\}$$k = \max\{A_i - C_i\}$ 则状态将仅与 $k$$k$ 相关。

于是此时不难想到一个较为简单的状态：令 $F(k)$$F(k)$ 表示状态为 $k$$k$ 时的期望操作次数。

显然 $F(0)=0$$F(0) = 0$，考虑转移，不难发现状态 $k$$k$ 肯定对应这一个或者一段 $A$$A$，因为序列 $A$$A$ 是不降的，所以我们假设第一个对应的前一个为 $A_{idx}$$A_{idx}$，显然对于前 $idx$$idx$ 个的操作都会使 $k\leftarrow k-1$$k \leftarrow k - 1$，对于 $idx$$idx$ 之后的操作都会使当前的 $k$$k$ 变为新的 $A_i$$A_i$，所以转移显然为：

转化一下：

现在不难发现即较小的都在左侧，较大的都在右侧，不过这个转移仍然不行，也就是我们是已知 $F(0)$$F(0)$ 然后想要求 $F(A_n)$$F(A_n)$，但是这个式子却是需要反过来转移的，所以需要优化。

考虑令 $G(k)$$G(k)$ 表示从状态 $0$$0$ 转移到状态 $k$$k$ 的期望次数，所以显然有 $G(k)+F(k)=F(A_n)$$G(k) + F(k) = F(A_n)$。移个项然后带进去 $F$$F$，显然有：

显然 $F(A_n)$$F(A_n)$ 抵消了，则：

类比一下之前的推出来：

显然：$G(A_n)=0$$G(A_n) = 0$，我们要求 $G(0)$$G(0)$，符合转移。

不难发现对于固定的 $k$$k$ 一定对应着固定的 $idx$$idx$，也就是 ${\displaystyle \frac{N-\sum _{i=idx+1}^{N}G(A_i)}{idx}}$$\dfrac{N - \sum_{i = idx + 1}^N G(A_i)}{idx}$ 可以认为是一个常数，令其为 $C$$C$，若再令 $B={\displaystyle \frac{N}{idx}}$$B = \dfrac{N}{idx}$，所以有 $G(k-1)=B\times G(k)+C$$G(k - 1) = B \times G(k) + C$，属于较为简单的转移，考虑矩乘优化，构造矩阵的过程也是平凡的，得到：

对于 $[A_i,A_{i+1}]$$[A_i, A_{i + 1}]$ 之间的部分的所有 $k$$k$ 显然 $B$$B$ 和 $C$$C$ 是相同的，这一部分用矩阵快速幂优化一下即可，最后复杂度应为 $O(2^{3}n\log A_i)$$O(2^3 n \log A_i)$。

Code

xxxxxxxxxx
89
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 void* Edge::operator new(size_t){static Edge* P = ed; 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
struct Matrix2{
28
    ll v00, v01, v10, v11;
29
    friend Matrix2 operator * (const Matrix2 &a, const Matrix2 &b){
30
        return Matrix2{
31
            (a.v00 * b.v00 % MOD + a.v01 * b.v10 % MOD) % MOD,
32
            (a.v00 * b.v01 % MOD + a.v01 * b.v11 % MOD) % MOD,
33
            (a.v10 * b.v00 % MOD + a.v11 * b.v10 % MOD) % MOD,
34
            (a.v10 * b.v01 % MOD + a.v11 * b.v11 % MOD) % MOD
35
        };
36
    }
37
};
38
Matrix2 base{1, 0, 0, 1};
39

40
ll qpow(ll a, ll b){
41
    ll ret(1), mul(a);
42
    while(b){
43
        if(b & 1)ret = ret * mul % MOD;
44
        b >>= 1;
45
        mul = mul * mul % MOD;
46
    }return ret;
47
}
48
ll inv(ll v){return qpow(v, MOD - 2);}
49
Matrix2 qpow(Matrix2 a, ll b){
50
    Matrix2 ret(base), mul(a);
51
    while(b){
52
        if(b & 1)ret = ret * mul;
53
        b >>= 1;
54
        mul = mul * mul;
55
    }return ret;
56
}
57

58
int N;
59
ll A[210000];
60

61
int main(){
62
    N = read();
63
    for(int i = 1; i <= N; ++i)A[i] = read < ll >();
64
    Matrix2 ans{0, 1, 0, 0};
65
    ll cur(0);
66
    for(int i = N - 1; i >= 1; --i){
67
        ll B = N * inv(i) % MOD, C = (N - cur) * inv(i) % MOD;
68
        ans = ans * qpow(Matrix2{B, 0, C, 1}, A[i + 1] - A[i]);
69
        (cur += ans.v00) %= MOD;
70
    }printf("%lld\n", (ans.v00 % MOD + MOD) % MOD);
71
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
72
    return 0;
73
}
74

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

UPD

update-2023_01_27 初稿