AtCoder Beginner Contest 255 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abcd 跳了

[ABC255E] Lucky Numbers

题面

给定长度为 $n-1$$n - 1$ 的序列 $S$$S$，存在序列 $a_n$$a_n$ 满足 $a_i+a_{i+1}=S_i$$a_i + a_{i + 1} = S_i$，给定 $m$$m$ 个幸运数字 $x_1,x_2,\cdots ,x_m$$x_1, x_2, \cdots, x_m$。你需要确定一个合法序列 $a$$a$ 使其中有最多的数字为幸运数字，求最大值。

Solution

首先不难发现，对于序列 $a_n$$a_n$ 存在 $n-1$$n - 1$ 个等式，故仅需确定一个数就可确定其它的数，则 $O(n^{2}m)$$O(n^2m)$ 的做法显然。考虑优化，以 $a_1$$a_1$ 为指标，$O(nm)$$O(nm)$ 枚举之后计算 $a_1$$a_1$ 然后把对应贡献加上最后统计一下最大值即可。

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(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, M;
26
int S[110000];
27
int lucky[20];
28
ll sum[110000];
29
int ans(-1);
30
unordered_map < ll, int > mp;
31

32
int main(){
33
    N = read(), M = read();
34
    for(int i = 1; i <= N - 1; ++i)
35
        S[i] = read(), sum[i] = sum[i - 1] + (i & 1 ? 1 : -1) * S[i];
36
    for(int i = 1; i <= M; ++i)lucky[i] = read();
37
    for(int i = 1; i <= N; ++i)
38
        for(int j = 1; j <= M; ++j)
39
            mp[(i & 1 ? 1 : -1) * lucky[j] + sum[i - 1]]++;
40
    for(auto v : mp)ans = max(ans, v.second);
41
    printf("%d\n", ans);
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
}

[ABC255F] Pre-order and In-order

题面

给定一棵二叉树的先序遍历和中序遍历，请构造一棵以 $1$$1$ 节点为根的二叉树。第 $i$$i$ 行输出节点 $i$$i$ 的左右儿子，儿子为空则输出 $0$$0$。无解输出 -1。

Solution

也是一道水题，考虑先序和中序的意义即可。

众所周知，先序遍历的顺序是根、左子树、右子树。中序遍历是左子树、根、右子树。

于是不难发现，在当前的先序遍历中取第一个数即为当前的根，然后在中序遍历中找到根的位置，其左侧即为整个左子树，右侧为整个右子树。于是不难想到 dfs 即可，参数维护当前的整个子树属于先序遍历的 $[lp,rp]$$[lp, rp]$，属于中序遍历的 $[li,ri]$$[li, ri]$，然后需要记录每个数的位置，通过中序遍历根和左右之间的数的个数，可计算左右子树的大小，以此即可确定先序遍历左右子树的下一个区间，以此递归下去即可。

考虑无解的情况，要么先序遍历的第一个值不为 $1$$1$，说明二叉树根不为 $1$$1$。要么就是在递归过程中，确定先序的第一位为根之后，根在中序中的位置超出了当前的限制位置，在这两种特殊情况记录一下无解即可。

Code

xxxxxxxxxx
67
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
int Pre[210000], In[210000];
27
int posP[210000], posI[210000];
28
pair < int, int > son[210000];
29

30
int dfs(int lp = 1, int rp = N, int li = 1, int ri = N){
31
    // printf("In dfs(%d ~ %d, %d ~ %d)\n", lp, rp, li, ri);
32
    if(lp > rp)return 0;
33
    int rt = Pre[lp];
34
    if(posI[rt] < li || posI[rt] > ri)puts("-1"), exit(0);
35
    if(lp == rp)return rt;
36
    int lsiz = (posI[rt] - 1) - li + 1;
37
    son[rt].first = dfs(lp + 1, lp + lsiz, li, posI[rt] - 1);
38
    son[rt].second = dfs(lp + lsiz + 1, rp, posI[rt] + 1, ri);
39
    return rt;
40
}
41

42
int main(){
43
    N = read();
44
    for(int i = 1; i <= N; ++i)posP[Pre[i] = read()] = i;
45
    for(int i = 1; i <= N; ++i)posI[In[i] = read()] = i;
46
    if(Pre[1] != 1)puts("-1"), exit(0);
47
    dfs();
48
    for(int i = 1; i <= N; ++i)printf("%d %d\n", son[i].first, son[i].second);
49
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
50
    return 0;
51
}
52

53
template < typename T >
54
inline T read(void){
55
    T ret(0);
56
    int flag(1);
57
    char c = getchar();
58
    while(c != '-' && !isdigit(c))c = getchar();
59
    if(c == '-')flag = -1, c = getchar();
60
    while(isdigit(c)){
61
        ret *= 10;
62
        ret += int(c - '0');
63
        c = getchar();
64
    }
65
    ret *= flag;
66
    return ret;
67
}

[ABC255G] Constrained Nim

题面

一般 Nim 游戏基础上增加 $m$$m$ 条限制，限制当石子数为 $x_i$$x_i$ 时不能拿走其中的 $y_i$$y_i$ 个。

Solution

显然博弈论，考虑 SG函数。Nim 游戏标准套路，对于多个石子堆求出每个石子堆石子数 $a_i$$a_i$ 的 $SG(a_i)$$SG(a_i)$，若 $\underset{i=1}{\overset{n}{⨁}}SG(a_i)=0$$\bigoplus_{i = 1}^n SG(a_i) = 0$ 则先手必输，反之必胜。关于 SG函数 的详解：SG函数学习笔记。

本题的区别即为 $m$$m$ 条限制，考虑如何处理。显然一般 Nim 游戏的 SG 函数有转移 $SG(i)=\mathrm{mex}\{SG(j)\mid j\in [1,i-1]\}$$SG(i) = \operatorname{mex}\{SG(j) \mid j \in [1, i - 1]\}$，本题的区别不难想到就是在一般的 SG函数 基础上，在求 $\mathrm{mex}$$\operatorname{mex}$ 的时候需要从中去掉一些值，也就是去掉 $SG(x_i)$$SG(x_i)$ 转移中的 $SG(x_i-y_i)$$SG(x_i - y_i)$。严谨点叙述就是 $SG(i)=\mathrm{mex}\{SG(j)\mid j\in [1,i-1]\wedge (i,j)\ne (x_k,x_k-y_k),k\in [1,m]\}$$SG(i) = \operatorname{mex}\{SG(j) \mid j \in [1, i - 1] \land (i, j) \neq (x_k, x_k - y_k), k \in[1, m] \}$。考虑维护，显然值域过大无法硬做。发现每次从中去掉一些值后，$\mathrm{mex}$$\operatorname{mex}$ 的值就会变为最小的被全部删除的元素。然后在这个位置以后，下一条限制以前，每次的 $SG(i)=SG(i-1)+1$$SG(i) = SG(i - 1) + 1$。发现整个值的分布实际上就是一些特殊点和很多条斜率为 $1$$1$ 的线段。所以我们对于答案，考虑开个 map 记录转折点，每次查询对应的所在位置然后增加对应数量的 $1$$1$ 即可。

具体实现过程也不难理解，开个 map 里套 basic_string 维护对应 $x_i$$x_i$ 的所有 $x_i-y_i$$x_i - y_i$，然后遍历，显然升序遍历过程中 $x_i$$x_i$ 以内的 $SG$$SG$ 均已确定。然后考虑如何确定当前的 $SG(i)$$SG(i)$，不难发现对于没有限制的 $SG$$SG$ 值即为其之前的所有 $SG$$SG$ 的最大值，也就是前缀最大值 $+1$$+1$。对于有限制的，我们枚举其所有限制，找到最小的一个被删没的值（注意这里比较的时候要 $+1$$+1$，原因是遍历到此时的时候一般情况下会有一个 $SG(i)=i$$SG(i) = i$），将其设为这个。此为特殊点，然后在其之后的点依然按照一般的斜率为 $1$$1$ 地增长，用前缀最大值更新，记录一下即可。

Code

xxxxxxxxxx
77
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, M;
26
ll A[210000];
27
ll oplus(0);
28
map < ll, basic_string < ll > > rest;
29
map < ll, ll > SG, repeat;
30

31
ll CalSG(ll x){
32
    auto sp = *prev(SG.upper_bound(x));
33
    return sp.second + (x - sp.first);
34
}
35

36
int main(){
37
    N = read(), M = read(); SG.insert({0, 0});
38
    for(int i = 1; i <= N; ++i)A[i] = read < ll >();
39
    for(int i = 1; i <= M; ++i){
40
        ll p = read < ll >(), v = read < ll >();
41
        rest[p] += p - v;
42
    }
43
    ll preMx(-1);
44
    for(auto &mp : rest){
45
        preMx = max(preMx, CalSG(mp.first - 1));
46
        map < ll, ll > tmp;
47
        for(auto val : mp.second)tmp[CalSG(val)]++;
48
        for(auto cur : tmp){
49
            if(cur.second >= repeat[cur.first] + 1){
50
                repeat[cur.first]++;
51
                SG[mp.first] = cur.first;
52
                break;
53
            }
54
        }preMx = max(preMx, CalSG(mp.first));
55
        SG[mp.first + 1] = preMx + 1;
56
    }
57
    for(int i = 1; i <= N; ++i)oplus ^= CalSG(A[i]);
58
    printf("%s\n", oplus ? "Takahashi" : "Aoki");
59
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
60
    return 0;
61
}
62

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

[ABC255Ex] Range Harvest Query

题面

给定一片 $N$$N$ 格的农田，从第 $0$$0$ 天开始，第 $i$$i$ 格农田每天会长出 $i$$i$ 的作物。

给出 $Q$$Q$ 个询问，每次询问以 $D,L,R$$D,L,R$ 的格式给出，表示询问在第 $D$$D$ 天，收割 $[L,R]$$[L,R]$ 的农田，会获得多少作物？答案对 $998244353$$998244353$ 取模。注意询问相互依赖，即在每一次收割后，$[L,R]$$[L,R]$ 的作物应当清零。

Solution

ODT 随便搞一下即可，没有任何难度，处理一下细节即可。一下子居然没看出来，日常身败名裂。

Code

xxxxxxxxxx
87
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
struct Node{
28
    ll l, r;
29
    mutable ll lst;
30
    friend const bool operator < (const Node &a, const Node &b){
31
        return a.l < b.l;
32
    }
33
};
34

35
class ODT{
36
private:
37
    set < Node > tr;
38
public:
39
    auto Insert(Node p){return tr.insert(p);}
40
    auto Split(ll p){
41
        auto it = tr.lower_bound(Node{p});
42
        if(it != tr.end() && it->l == p)return it;
43
        advance(it, -1);
44
        ll l = it->l, r = it->r, lst = it->lst;
45
        tr.erase(it);
46
        Insert(Node{l, p - 1, lst});
47
        return Insert(Node{p, r, lst}).first;
48
    }
49
    ll Assign(ll l, ll r, ll days){
50
        ll ret(0);
51
        auto itR = Split(r + 1), itL = Split(l);
52
        for(auto it = itL; it != itR; ++it)
53
            (ret += ((__int128_t)(it->l + it->r) * (it->r - it->l + 1) / 2ll) % MOD * (days - it->lst) % MOD) %= MOD;
54
        tr.erase(itL, itR);
55
        Insert(Node{l, r, days});
56
        return ret;
57
    }
58
}odt;
59

60
ll N; int Q;
61

62
int main(){
63
    N = read < ll >(), Q = read();
64
    odt.Insert(Node{1, N, 0});
65
    while(Q--){
66
        ll D = read < ll >(), L = read < ll >(), R = read < ll >();
67
        printf("%lld\n", odt.Assign(L, R, D));
68
    }
69
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
70
    return 0;
71
}
72

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

UPD

update-2022_12_07 初稿