AtCoder Beginner Contest 264 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abcd 不说了

[ABC264E] Blackout 2

题面

ZK 国有 $N$$N$ 座城市和 $M$$M$ 座发电站，我们称城市和发电站为地点。

这些地点的标号为 $1,2,\dots ,N+M$$1,2,\dots,N+M$，其中标号 $1,2,\dots ,N$$1,2,\dots,N$ 是城市，标号 $N+1,N+2,\dots ,N+M$$N+1,N+2,\dots,N+M$ 是发电站。

这个国家有 $E$$E$ 条能源传输线路。第 $i$$i$ 条线路双向连接地点 $U_i$$U_i$ 和地点 $V_i$$V_i$。一个城市如果可以通过某些线路到达发电站，则称这个城市是有供电的。

现在有 $Q$$Q$ 条询问。第 $i(1\le i\le Q)$$i\;(1\le i\le Q)$ 条询问，代表第 $X_i$$X_i$ 条线路停止工作，并且将来也无法修复。

每次询问后输出有供电的城市。

Solution

没什么可说的，比较显然，把询问离线然后倒着做，用并查集维护加边即可，经典套路。

Code

xxxxxxxxxx
93
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
template < typename T = int >
22
inline T read(void);
23

24
struct Edge{int s, t;}edg[510000];
25
int N, M, E;
26
int Q;
27
ll rans[510000];
28
bool del[510000];
29
int qs[510000];
30
ll ans(0);
31

32
class UnionFind{
33
private:
34
    int fa[510000];
35
    int siz[510000];
36
    bool light[510000];
37
public:
38
    UnionFind(void){for(int i = 1; i <= 501000; ++i)fa[i] = i;}
39
    void Init(void){
40
        for(int i = 1; i <= N; ++i)siz[i] = 1;
41
        for(int i = N + 1; i <= N + M; ++i)light[i] = true;
42
    }
43
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
44
    void Merge(int s, int t){
45
        int rs = Find(s), rt = Find(t);
46
        if(rs == rt)return;
47
        // printf("Mergeing rs = %d, rt = %d, light is %d %d\n", rs, rt, light[rs] ? 1 : 0, light[rt] ? 1 : 0);
48
        if(light[rs] ^ light[rt]){
49
            if(!light[rs] && light[rt])swap(rs, rt);
50
            ans += siz[rt];
51
            siz[rs] += siz[rt];
52
            fa[rt] = rs;
53
        }else{
54
            siz[rs] += siz[rt];
55
            fa[rt] = rs;
56
        }
57
    }
58
}uf;
59

60
int main(){
61
    // freopen("test_18.txt", "r", stdin);
62
    // freopen("out.txt", "w", stdout);
63
    N = read(), M = read(), E = read();
64
    uf.Init();
65
    for(int i = 1; i <= E; ++i){
66
        int s = read(), t = read();
67
        edg[i] = Edge{s, t};
68
    }Q = read();
69
    for(int i = 1; i <= Q; ++i)del[qs[i] = read()] = true;
70
    for(int i = 1; i <= E; ++i)if(!del[i])uf.Merge(edg[i].s, edg[i].t);//, printf("merge : %d %d\n", edg[i].s, edg[i].t);
71
    for(int i = Q; i >= 1; --i){
72
        rans[i] = ans;
73
        uf.Merge(edg[qs[i]].s, edg[qs[i]].t);
74
    }for(int i = 1; i <= Q; ++i)printf("%lld\n", rans[i]);
75
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
76
    return 0;
77
}
78

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

[ABC264F] Monochromatic Path

题面

给定一个 $H$$H$ 行 $W$$W$ 列的 $01$$01$ 矩阵。你可以花费 $R_i$$R_i$ 将矩阵第 $i$$i$ 行进行 $01$$01$ 反转，可以花费 $C_j$$C_j$ 将矩阵第 $j$$j$ 列进行 $01$$01$ 反转。你需要最小化花费，并使得从 $(1,1)$$(1, 1)$ 出发，只能向右或下走到达 $(H,W)$$(H, W)$ 至少有一条路径满足均为 $0$$0$ 或 $1$$1$。

Solution

首先不难想到每一行或一列最多进行一次反转操作，否则是无用的。发现只能向右或向下，则无后效性，故可以尝试 DP。

设 $dp(i,j,0/1,0/1)$$dp(i, j, 0/1, 0/1)$ 表示处理到第 $i$$i$ 行 $j$$j$ 列，第 $i$$i$ 行和第 $j$$j$ 列是否反转的最小花费。

我们设当前状态为 $dp(i,j,x,y)$$dp(i, j, x, y)$，令 $G_{i,j}$$G_{i, j}$ 表示矩阵的元素，则对于向下走的下一步的转移比较显然：

对于向右走的下一步也同理可得。

初始值即为 $dp(1,1,0,0)\leftarrow 0,dp(1,1,1,0)\leftarrow R_1,dp(1,1,0,1)\leftarrow C_1,dp(1,1,1,1)\leftarrow R_1+C_1$$dp(1, 1, 0, 0) \leftarrow 0, dp(1, 1, 1, 0) \leftarrow R_1, dp(1, 1, 0, 1) \leftarrow C_1, dp(1, 1, 1, 1) \leftarrow R_1 + C_1$。

最终答案即为 $min\{dp(H,W,x,y)\}$$\min\{dp(H, W, x, y)\}$。

Code

xxxxxxxxxx
71
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 H, W;
26
ll R[2100], C[2100];
27
ll dp[2100][2100][2][2];
28
bitset < 2100 > G[2100];
29

30
int main(){
31
    H = read(), W = read();
32
    for(int i = 1; i <= H; ++i)R[i] = read();
33
    for(int i = 1; i <= W; ++i)C[i] = read();
34
    for(int i = 1; i <= H; ++i)
35
        for(int j = 1; j <= W; ++j){
36
            char c = getchar(); while(!isdigit(c))c = getchar();
37
            G[i][j] = c == '1' ? true : false;
38
        }
39
    memset(dp, 0x3f, sizeof dp);
40
    dp[1][1][0][0] = 0, dp[1][1][1][0] = R[1], dp[1][1][0][1] = C[1], dp[1][1][1][1] = R[1] + C[1];
41
    for(int i = 1; i <= H; ++i)
42
        for(int j = 1; j <= W; ++j)
43
            for(int x = 0; x <= 1; ++x)
44
                for(int y = 0; y <= 1; ++y){
45
                    if((G[i][j] ^ x ^ y )== (G[i + 1][j] ^ y))dp[i + 1][j][0][y] = min(dp[i + 1][j][0][y], dp[i][j][x][y]);
46
                    else dp[i + 1][j][1][y] = min(dp[i + 1][j][1][y], dp[i][j][x][y] + R[i + 1]);
47
                    if((G[i][j] ^ x ^ y) == (G[i][j + 1] ^ x))dp[i][j + 1][x][0] = min(dp[i][j + 1][x][0], dp[i][j][x][y]);
48
                    else dp[i][j + 1][x][1] = min(dp[i][j + 1][x][1], dp[i][j][x][y] + C[j + 1]);
49
                }
50
    ll ans(LONG_LONG_MAX);
51
    for(int x = 0; x <= 1; ++x)for(int y = 0; y <= 1; ++y)ans = min(ans, dp[H][W][x][y]);
52
    printf("%lld\n", ans);
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

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

[ABC264G] String Fair

题面

给定 $n$$n$ 条评分规则，每条存在字符串 $T_i$$T_i$ 和得分 $P_i$$P_i$。你需要构造一个任意长度但非空的字符串 $S$$S$，在 $S$$S$ 中每次出现 $T_i$$T_i$ 就会获得 $P_i$$P_i$ 得分。你需要最大化得分，输出最大值。若无限大则输出 Infinity。

Solution

一个十分精妙的图论。

关键的信息在 $|T_i|\le 3$$\lvert T_i \rvert \le 3$，这样的话我们就可以考虑进行建边。我们令 $P_{str}$$P_{str}$ 表示字符串为 $str$$str$ 的时候的得分，如果没有该字符串的评分规则即为 $0$$0$。

于是考虑如对于从 $ab$$ab$ 通过 $c$$c$ 可以有一条边到 $bc$$bc$，边权即为 $P_{abc}+P_{bc}+P_c$$P_{abc} + P_{bc} + P_{c}$。同时注意一些细节，如从空字符串可以通过任意字符，如通过 $a$$a$ 连结到 $a$$a$，边权即为 $P_a$$P_a$，以及对于长度为 $1$$1$ 的字符串连结到长度为 $2$$2$ 的同理。

这样将图建完之后不难发现只需要 SPFA 跑一遍单源最长路，取最大的 $dis$$dis$ 即可，如果存在正环那么显然无限大。

于是点数为 $n={26}^2+26+1$$n = 26^2 + 26 + 1$，边数即为 $m=26n$$m = 26n$，于是 SPFA 最坏复杂度即为 $O(nm)$$O(nm)$，也就是 ${26}^5$$26^5$ 的级别，可以通过。

当然这里我们用 map 实现，手动实现一个 hash() 之后用 unorderer_map 即可去掉 map 的 $\log$$\log$。

Code

xxxxxxxxxx
104
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

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[21000];
33
ROPNEW(ed);
34
Edge* head[1100];
35

36
int N;
37
int cnt(0);
38
unordered_map < string, int > score;
39
map < pair < int, int >, int > mp;
40
unordered_map < int, pair < int, int > > rmp;
41
bitset < 1100 > inq;
42
int dep[1100];
43
ll dis[1100];
44
ll ans(LONG_LONG_MIN);
45

46
void SPFA(void){
47
    memset(dis, 0xc0, sizeof dis);
48
    queue < int > cur;
49
    cur.push(1); inq[1] = true; dep[1] = 1, dis[1] = 0;
50
    while(!cur.empty()){
51
        int p = cur.front(); cur.pop();
52
        inq[p] = false;
53
        for(auto i = head[p]; i; i = i->nxt){
54
            if(dis[p] + i->val > dis[SON]){
55
                dis[SON] = dis[p] + i->val;
56
                ans = max(ans, dis[SON]);
57
                dep[SON] = dep[p] + 1;
58
                if(dep[SON] > 26 * 26 + 26 + 1)printf("Infinity\n"), exit(0);
59
                if(!inq[SON])cur.push(SON), inq[SON] = true;
60
            }
61
        }
62
    }
63
}
64

65
int main(){
66
    N = read();
67
    for(int i = 1; i <= N; ++i){
68
        string S; cin >> S;
69
        score.insert({S, read()});
70
    }mp.insert({{0, 0}, ++cnt}), rmp.insert({cnt, {0, 0}});
71
    for(int i = 'a'; i <= 'z'; ++i)mp.insert({{0, i}, ++cnt}), rmp.insert({cnt, {0, i}});
72
    for(int i = 'a'; i <= 'z'; ++i)for(int j = 'a'; j <= 'z'; ++j)
73
        mp.insert({{i, j}, ++cnt}), rmp.insert({cnt, {i, j}});
74
    for(int i = 1; i <= cnt; ++i)for(int j = 'a'; j <= 'z'; ++j){
75
        ll tot(0); string S;
76
        if(rmp[i].first)S += (char)rmp[i].first;
77
        if(rmp[i].second)S += (char)rmp[i].second;
78
        S += j; tot += score[S];
79
        while(!S.empty()){
80
            S.erase(S.begin());
81
            tot += score[S];
82
        }
83
        head[i] = new Edge{head[i], mp[{rmp[i].second, j}], tot};
84
    }SPFA();
85
    printf("%lld\n", ans);
86
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
87
    return 0;
88
}
89

90
template < typename T >
91
inline T read(void){
92
    T ret(0);
93
    int flag(1);
94
    char c = getchar();
95
    while(c != '-' && !isdigit(c))c = getchar();
96
    if(c == '-')flag = -1, c = getchar();
97
    while(isdigit(c)){
98
        ret *= 10;
99
        ret += int(c - '0');
100
        c = getchar();
101
    }
102
    ret *= flag;
103
    return ret;
104
}

[ABC264Ex] Perfect Binary Tree

题面

存在一棵以 $1$$1$ 为根节点的 $n$$n$ 个节点的树，给定序列 $P_{n-1}$$P_{n - 1}$ 表示 $[2,n]$$[2, n]$ 节点的父亲。给定 $k$$k$，你需要从 $[1,k]$$[1, k]$ 中选择一些点，对于每一个 $k$$k$ 一次询问，求有多少种选法使得选出的点为一棵以 $1$$1$ 为根节点的满二叉树。输出 $k\in [1,n]$$k \in [1, n]$ 的答案，答案对 $998244353$$998244353$ 取模。

Solution

首先一个比较重要的性质就是 $n$$n$ 个节点的满二叉树层高为 ${\log }_2^n$$\log_2^n$，所以在原树里层高超过 ${\log }_2^n$$\log_2^n$ 的节点就可以直接忽略了。

不难想到 DP，令 $dp(p,i)$$dp(p, i)$ 表示以 $p$$p$ 为根节点层高为 $i$$i$ 的满二叉树方案数。

朴素的转移十分显然，即在其儿子里找到两个层高为 $i-1$$i - 1$ 的满二叉树拼起来即可，即转移为：

考虑到我们每次询问都是增加一个节点，如此的转移方式复杂度显然是不正确的，考虑优化。不难想到这个式子可以转化为从和平方里去除平方和，即：

于是这个东西就可以支持 $O(1)$$O(1)$ 修改了，维护一下和以及平方和即可。注意需要记录上一次的值和新的值，减去旧的加上新的。同时考虑发现每次增加一个点，将会改变该点到 $1$$1$ 节点的整条链，并且只会改变这些点，同时若变化的节点超过 ${\log }_2^n$$\log_2^n$ 层了那么可以直接忽略。

最终的答案即为 $\sum _{i=1}^{\lfloor {\log }_2^n\rfloor }dp(1,i)$$\sum_{i = 1}^{\lfloor \log_2^n \rfloor}dp(1, i)$。

所以每次修改都是 $O(\log n)$$O(\log n)$ 的，最终答案的查询也是 $O(\log n)$$O(\log n)$ 的，最终复杂度 $O(n\log n)$$O(n \log n)$。

Code

xxxxxxxxxx
110
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 Edge{
28
    Edge* nxt;
29
    int to;
30
    OPNEW;
31
}ed[610000];
32
ROPNEW(ed);
33
Edge* head[310000];
34

35
ll qpow(ll a, ll b){
36
    ll ret(1), mul(a);
37
    while(b){
38
        if(b & 1)ret = ret * mul % MOD;
39
        b >>= 1;
40
        mul = mul * mul % MOD;
41
    }return ret;
42
}
43

44
int N;
45
int mxdep;
46
int inv2;
47
int dep[310000];
48
int fa[310000];
49
ll ans(0);
50
ll sum[310000][21], sum2[310000][21];
51

52
ll DP(int p, int i){
53
    if(i == 1)return 1;
54
    return ((sum[p][i] * sum[p][i] % MOD - sum2[p][i]) % MOD + MOD) % MOD * inv2 % MOD;
55
}
56
void dfs(int p = 1, int fa = 0){
57
    dep[p] = dep[fa] + 1;
58
    for(auto i = head[p]; i; i = i->nxt)
59
        if(SON != fa)dfs(SON, p);
60
}
61

62
int main(){
63
    // freopen("in.txt", "r", stdin);
64
    // freopen("out.txt", "w", stdout);
65
    inv2 = qpow(2, MOD - 2);
66
    N = read();
67
    if(N == 1)printf("1\n"), exit(0);
68
    mxdep = (int)log2(N);
69
    for(int i = 2; i <= N; ++i){
70
        fa[i] = read();
71
        head[i] = new Edge{head[i], fa[i]};
72
        head[fa[i]] = new Edge{head[fa[i]], i};
73
    }dfs();
74
    for(int cp = 1; cp <= N; ++cp){
75
        if(dep[cp] <= mxdep){
76
            sum[cp][1] = sum2[cp][1] = 1;
77
            ll cnt(1), cur(cp), lst(-1), lstDP(0);
78
            while(cur != 1){
79
                lst = cur;
80
                cur = fa[cur], ++cnt;
81
                ll tmp = DP(cur, cnt);
82
                (((sum[cur][cnt] -= lstDP) %= MOD) += MOD) %= MOD;
83
                (((sum2[cur][cnt] -= lstDP * lstDP % MOD) %= MOD) += MOD) %= MOD;
84
                lstDP = tmp;
85
                (sum[cur][cnt] += DP(lst, cnt - 1)) %= MOD;
86
                (sum2[cur][cnt] += DP(lst, cnt - 1) * DP(lst, cnt - 1) % MOD) %= MOD;
87
            }
88
        }ans = 0;
89
        for(int i = 1; i <= mxdep; ++i)(ans += DP(1, i)) %= MOD;
90
        printf("%lld\n", ans);
91
    }
92
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
93
    return 0;
94
}
95

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

UPD

update-2023_01_03 初稿