AtCoder Beginner Contest 265 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abc不说了

[ABC265D] Iroha and Haiku (New ABC Edition)

题面

题意：

有一个长度为$N$$N$的数列$A=(A_0,...,A_{N-1})$$A=(A_0,...,A _{N-1})$,

判断有满足以下所有条件的整数$(x,y,z,w)$$(x,y,z,w)$是否存在

• $0\ge x<y<z<w\le N$$0\geq x < y < z < w \le N$
• $A_x+A_{x+1}+...+A_{y-1}=P$$A_x+A_{x+1}+...+A_{y-1} = P$
• $A_y+A_{y+1}+...+A_{z-1}=Q$$A_y+A_{y+1}+...+A_{z-1}= Q$
• $A_z+A_{z+1}+...+A_{w-1}=R$$A_z+A_{z+1}+...+A_{w-1}=R$

Solution

一个比较显然的思路就是枚举 $x$$x$ 然后二分 $y,z,w$$y, z, w$，或者用 set 也行，复杂度都是 $O(n\log n)$$O(n \log n)$ 的，似乎可以直接用单调性均摊线性解决，不过没必要。

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;
26
ll P, Q, R;
27
ll a[210000];
28
ll sum[210000];
29

30
int main(){
31
    N = read(), P = read < ll >(), Q = read < ll >(), R = read < ll >();
32
    for(int i = 1; i <= N; ++i)sum[i] = sum[i - 1] + (a[i] = read());
33
    for(int x = 1; x <= N - 2; ++x){
34
        int l = x, r = N - 2, ans(-1);
35
        while(l <= r){
36
            int mid = (l + r) >> 1;
37
            if(sum[mid] - sum[x - 1] >= P)ans = mid, r = mid - 1;
38
            else l = mid + 1;
39
        }if(!~ans || sum[ans] - sum[x - 1] != P)continue;
40
        int y = ans + 1;
41
        // printf("x = %d, y = %d\n", x, y);
42
        l = y, r = N - 1, ans = -1;
43
        while(l <= r){
44
            int mid = (l + r) >> 1;
45
            if(sum[mid] - sum[y - 1] >= Q)ans = mid, r = mid - 1;
46
            else l = mid + 1;
47
        }if(!~ans || sum[ans] - sum[y - 1] != Q)continue;
48
        int z = ans + 1;
49
        // printf("x = %d, y = %d, z = %d\n", x, y, z);
50
        l = z, r = N, ans = -1;
51
        while(l <= r){
52
            int mid = (l + r) >> 1;
53
            if(sum[mid] - sum[z - 1] >= R)ans = mid, r = mid - 1;
54
            else l = mid + 1;
55
        }if(!~ans || sum[ans] - sum[z - 1] != R)continue;
56
        // printf("x = %d, y = %d, z = %d, w = %d\n", x, y, z, ans + 1);
57
        printf("Yes\n"), exit(0);
58
    }printf("No\n");
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
}

[ABC265E] Warp

题面

ZK 现在在一个二维平面。他现在会进行 $N$$N$ 次传送，每次传送回执行如下移动之一：

• 从当前点 $(x,y)$$(x,y)$ 移动到 $(x+A,y+B)$$(x+A,y+B)$
• 从当前点 $(x,y)$$(x,y)$ 移动到 $(x+C,y+D)$$(x+C,y+D)$
• 从当前点 $(x,y)$$(x,y)$ 移动到 $(x+E,y+F)$$(x+E,y+F)$

同时在这个平面上有 $M$$M$ 个点 $(X_1,Y_1),\dots ,(X_M,Y_M)$$(X_1,Y_1),\ldots,(X_M,Y_M)$ ，这些点 ZK 是无法停留或经过的。

问 $N$$N$ 次传送一共会有多少种路径？输出答案对 $998244353$$998244353$ 取模。

Solution

十分显然的 DP，令 $dp(i,j,k)$$dp(i, j, k)$ 表示 $i$$i$ 次第一种 $j$$j$ 次第二种 $k$$k$ 次第三种的方案数，判断一下能不能走即可。

Code

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

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

10
using namespace std;
11

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

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

21
#define MOD (998244353ll)
22

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

26
int N, M;
27
ll A, B, C, D, E, F;
28
set < pair < ll, ll > > blk;
29
ll dp[310][310][310];
30
ll ans(0);
31
bool isBlocked(pair < ll, ll > pos){return blk.find({pos.first, pos.second}) != blk.end();}
32
pair < ll, ll > GetPos(int i, int j, int k){return {A * i + C * j + E * k, B * i + D * j + F * k};}
33

34
int main(){
35
    N = read(), M = read();
36
    A = read(), B = read(), C = read(), D = read(), E = read(), F = read();
37
    while(M--){int x = read(), y = read(); blk.insert({x, y});}
38
    dp[0][0][0] = 1;
39
    for(int i = 0; i <= N; ++i)
40
        for(int j = 0; j <= N; ++j)
41
            for(int k = 0; k <= N; ++k){
42
                if(i + j + k > N || isBlocked(GetPos(i, j, k)))continue;
43
                (dp[i][j][k] += ((i ? dp[i - 1][j][k] : 0) + (j ? dp[i][j - 1][k] : 0) + (k ? dp[i][j][k - 1] : 0)) % MOD) %= MOD;
44
                if(i + j + k == N)(ans += dp[i][j][k]) %= MOD;
45
            }
46
    printf("%lld\n", ans);
47
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
48
    return 0;
49
}
50

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

[ABC265F] Manhattan Cafe

题面

在 $n$$n$ 维空间中存在 $p,q$$p, q$ 两点，求有多少个整点满足到 $p,q$$p, q$ 的曼哈顿距离均不大于 $d$$d$。

Solution

细节巨多的 DP。

首先有一个较为显然的 $\mathtt{\text{3D1D}}$$\texttt{3D1D}$ 的 $O(n{d}^3)$$O(nd^3)$ 的做法，即令 $dp(i,j,k)$$dp(i, j, k)$ 表示考虑前 $i$$i$ 维到 $p$$p$ 曼哈顿距离为 $j$$j$，到 $q$$q$ 曼哈顿距离为 $k$$k$ 的方案数，然后这个东西 $O(d)$$O(d)$ 的转移较为显然，即枚举 $i$$i$ 维的坐标，令其为 $x$$x$ 则转移为：

然后这个东西实际上是可以通过类似前缀和的东西转移的，但是是类似对角线前缀和的，比较复杂细节巨多，所以这里参考以下机房大佬 @sssmzy 的做法。

考虑将状态修改为 $dp(i,j,k)$$dp(i, j, k)$ 表示考虑前 $i$$i$ 维，到 $p$$p$ 和 $q$$q$ 的曼哈顿距离和为 $j$$j$，到 $p$$p$ 的曼哈顿距离为 $k$$k$。

这个时候考虑两种可能性，对于某次枚举的位置 $x$$x$，若满足 $p_i\le x\le q_i\vee q_i\le x\le p_i$$p_i \le x \le q_i \lor q_i \le x \le p_i$，也就是说 $x$$x$ 在 $p,q$$p, q$ 之间，那么 $j$$j$ 这一维是从 $j-|p_i-q_i|$$j - \lvert p_i - q_i \rvert$ 转移而来，而 $k$$k$ 从 $k$$k$ 到 $k-|p_i-q_i|$$k - \lvert p_i - q_i \rvert$ 这段区间转移而来，那么即可以用前缀和转移。

考虑对于 $x$$x$ 在 $p,q$$p, q$ 之外的情况，那么对于每个 $x\leftarrow x+1\vee x\leftarrow x-1$$x \leftarrow x + 1 \lor x \leftarrow x - 1$，显然存在 $j\leftarrow j+2,k\leftarrow j+1$$j \leftarrow j + 2, k \leftarrow j + 1$。所以我们只需要再维护一个前缀和 $su{m}_2(j,k)=su{m}_2(j-2,k-1)+dp(j,k)$$sum_2(j, k) = sum_2(j - 2, k - 1) + dp(j, k)$ 即可。

具体来说，维护一个 $sum$$sum$ 和 $su{m}_2$$sum_2$，意义同上。同时因为空间问题我们需要把第一维滚动掉。具体的转移即若 $j<|p_i-q_i|$$j \lt \lvert p_i - q_i \rvert$ 那么 $dp(j,k)=0$$dp(j, k) = 0$。否则令 $dis=|p_i-q_i|$$dis = \lvert p_i - q_i \rvert$，即为：

转移的意义即为在 $p,q$$p, q$ 中间和分别在 $p,q$$p, q$ 的两侧。

于是每次处理完 DP 后清空并重新维护 $sum,su{m}_2$$sum, sum_2$ 即可。

最终复杂度为 $O(n{d}^2)$$O(nd^2)$，可以通过。

Code

xxxxxxxxxx
81
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, D;
28
int P[110], Q[110];
29
ll dp[2100][1100];
30
ll sum[2100][1100];
31
ll sum2[2100][1100];
32
ll ans(0);
33

34
int main(){
35
    N = read(), D = read();
36
    for(int i = 1; i <= N; ++i)P[i] = read();
37
    for(int i = 1; i <= N; ++i)Q[i] = read();
38
    dp[0][0] = 1;
39
    for(int j = 0; j <= D * 2; ++j)
40
        for(int k = 0; k <= D; ++k)
41
            sum[j][k] = ((k - 1 >= 0 ? sum[j][k - 1] : 0) + dp[j][k]) % MOD,
42
            sum2[j][k] = ((j - 2 >= 0 && k - 1 >= 0 ? sum2[j - 2][k - 1] : 0) + dp[j][k]) % MOD;
43
    for(int i = 1; i <= N; ++i){
44
        for(int j = 0; j <= D * 2; ++j)
45
            for(int k = 0; k <= D; ++k){
46
                int dis = abs(P[i] - Q[i]);
47
                dp[j][k] = j >= dis
48
                    ?
49
                        ((sum[j - dis][k] - (k - dis - 1 >= 0 ? sum[j - dis][k - dis - 1] : 0) + MOD) % MOD +
50
                        (j - dis - 2 >= 0 && k - 1 >= 0 ? sum2[j - dis - 2][k - 1] % MOD : 0) +
51
                        (j - dis - 2 >= 0 && k - dis - 1 >= 0 ? sum2[j - dis - 2][k - dis - 1] % MOD : 0)) % MOD
52
                    : 0;
53
            }
54
        memset(sum, 0, sizeof sum), memset(sum2, 0, sizeof sum2);
55
        for(int j = 0; j <= D * 2; ++j)
56
            for(int k = 0; k <= D; ++k)
57
                sum[j][k] = ((k - 1 >= 0 ? sum[j][k - 1] : 0) + dp[j][k]) % MOD,
58
                sum2[j][k] = ((j - 2 >= 0 && k - 1 >= 0 ? sum2[j - 2][k - 1] : 0) + dp[j][k]) % MOD;
59
    }
60
    for(int j = 0; j <= D * 2; ++j)for(int k = 0; k <= min(j, D); ++k)
61
        if(j - k <= D) (ans += dp[j][k]) %= MOD;
62
    printf("%lld\n", ans);
63
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
64
    return 0;
65
}
66

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

[ABC265G] 012 Inversion

题面

有一个元素全为 $0,1$$0,1$ 或 $2$$2$ 的数列 $A=(A_1,A_2,\dots ,A_n)$$A = (A_1,A_2,\ldots,A_n)$。现在有两种操作：

1. 1 L R：询问区间 $[L,R]$$[L,R]$ 内的逆序对数量；
2. 2 L R S T U：将区间 $[L,R]$$[L,R]$ 内的所有 $0$$0$ 改为 $S$$S$，$1$$1$ 改为 $T$$T$，$2$$2$ 改为 $U$$U$。

Solution

显然线段树。每个节点维护 $cn{t}_{x,y}$$cnt_{x, y}$ 表示多少对 $(x,y)$$(x, y)$ 的逆序对，维护 $si{z}_x$$siz_x$ 表示多少个 $x$$x$，再维护一下 lazytag，东西虽然比较多但是很显然且直观，细节不少。

Code

xxxxxxxxxx
136
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;
26
int A[110000];
27
struct RetNode{
28
    ll cnt;
29
    ll siz0, siz1, siz2;
30
};
31

32
class SegTree{
33
private:
34
    ll cnt[110000 << 2][3][3], siz[110000 << 2][3];
35
    ll lz[110000 << 2][3];
36
    #define LS (p << 1)
37
    #define RS (LS | 1)
38
    #define MID ((gl + gr) >> 1)
39
public:
40
    SegTree(void){for(int i = 0; i <= 101000 << 2; ++i)for(int j = 0; j <= 2; ++j)lz[i][j] = j;}
41
    void Pushup(int p){
42
        for(int i = 0; i <= 2; ++i)siz[p][i] = siz[LS][i] + siz[RS][i];
43
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)
44
            cnt[p][i][j] = cnt[LS][i][j] + cnt[RS][i][j] + siz[LS][i] * siz[RS][j];
45
    }
46
    void Pushdown(int p){
47
        if(lz[p][0] == 0 && lz[p][1] == 1 && lz[p][2] == 2)return;
48
        for(int i = 0; i <= 2; ++i)lz[LS][i] = lz[p][lz[LS][i]];
49
        for(int i = 0; i <= 2; ++i)lz[RS][i] = lz[p][lz[RS][i]];
50
        ll tsiz[3]; memset(tsiz, 0, sizeof tsiz);
51
        ll tcnt[3][3]; memset(tcnt, 0, sizeof tcnt);
52
        for(int i = 0; i <= 2; ++i)tsiz[lz[p][i]] += siz[LS][i];
53
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)
54
            tcnt[lz[p][i]][lz[p][j]] += cnt[LS][i][j];
55
        for(int i = 0; i <= 2; ++i)siz[LS][i] = tsiz[i];
56
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)cnt[LS][i][j] = tcnt[i][j];
57
        memset(tsiz, 0, sizeof tsiz), memset(tcnt, 0, sizeof tcnt);
58
        for(int i = 0; i <= 2; ++i)tsiz[lz[p][i]] += siz[RS][i];
59
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)
60
            tcnt[lz[p][i]][lz[p][j]] += cnt[RS][i][j];
61
        for(int i = 0; i <= 2; ++i)siz[RS][i] = tsiz[i];
62
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)cnt[RS][i][j] = tcnt[i][j];
63
        for(int i = 0; i <= 2; ++i)lz[p][i] = i;
64
    }
65
    void Build(int p = 1, int gl = 1, int gr = N){
66
        if(gl == gr)return siz[p][A[gl = gr]] = 1, void();
67
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
68
        Pushup(p);
69
    }
70
    RetNode Query(int l, int r, int p = 1, int gl = 1, int gr = N){
71
        if(l <= gl && gr <= r)
72
            return RetNode{cnt[p][2][0] + cnt[p][2][1] + cnt[p][1][0], siz[p][0], siz[p][1], siz[p][2]};
73
        if(gr < l || r < gl)return RetNode{0, 0, 0, 0};
74
        Pushdown(p);
75
        auto Lret = Query(l, r, LS, gl, MID), Rret = Query(l, r, RS, MID + 1, gr);
76
        return RetNode{
77
            Lret.cnt + Rret.cnt + Lret.siz2 * Rret.siz0 + Lret.siz2 * Rret.siz1 + Lret.siz1 * Rret.siz0,
78
            Lret.siz0 + Rret.siz0,
79
            Lret.siz1 + Rret.siz1,
80
            Lret.siz2 + Rret.siz2
81
        };
82
    }
83
    void Modify(int l, int r, int S, int T, int U, int p = 1, int gl = 1, int gr = N){
84
        if(l <= gl && gr <= r){
85
            ll tsiz[3]; memset(tsiz, 0, sizeof tsiz);
86
            ll tcnt[3][3]; memset(tcnt, 0, sizeof tcnt);
87
            int ctlz[3] = {S, T, U};
88
            for(int i = 0; i <= 2; ++i)lz[p][i] = ctlz[lz[p][i]];
89
            for(int i = 0; i <= 2; ++i)tsiz[ctlz[i]] += siz[p][i];
90
            for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)
91
                tcnt[ctlz[i]][ctlz[j]] += cnt[p][i][j];
92
            for(int i = 0; i <= 2; ++i)siz[p][i] = tsiz[i];
93
            for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)cnt[p][i][j] = tcnt[i][j];
94
            return;
95
        }Pushdown(p);
96
        if(l <= MID)Modify(l, r, S, T, U, LS, gl, MID);
97
        if(MID + 1 <= r)Modify(l, r, S, T, U, RS, MID + 1, gr);
98
        Pushup(p);
99
    }
100
}st;
101

102
int main(){
103
    // freopen("in.txt", "r", stdin);
104
    // freopen("out.txt", "w", stdout);
105
    N = read(), Q = read();
106
    for(int i = 1; i <= N; ++i)A[i] = read();
107
    st.Build();
108
    while(Q--){
109
        int opt = read();
110
        if(opt == 1){
111
            int l = read(), r = read();
112
            printf("%lld\n", st.Query(l, r).cnt);
113
        }else{
114
            int l = read(), r = read(), S = read(), T = read(), U = read();
115
            st.Modify(l, r, S, T, U);
116
        }
117
    }
118
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
119
    return 0;
120
}
121

122
template < typename T >
123
inline T read(void){
124
    T ret(0);
125
    int flag(1);
126
    char c = getchar();
127
    while(c != '-' && !isdigit(c))c = getchar();
128
    if(c == '-')flag = -1, c = getchar();
129
    while(isdigit(c)){
130
        ret *= 10;
131
        ret += int(c - '0');
132
        c = getchar();
133
    }
134
    ret *= flag;
135
    return ret;
136
}

题面

Solution

Code

xxxxxxxxxx
1
1

UPD

update-2022__ 初稿