2022.11.22 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

给定序列区间查询区间内是否所有数字各不相同。

$n,q\le 5\times {10}^5$$n, q \le 5 \times 10^5$。

看完题就想到莫队了。。然后发现数据范围刚好卡莫队，根号过不去，不过一下子还是没想出来线段树写法，糊完莫队写完后面的回来对拍发现莫队寄了，调了十多分钟没调出来，又想了一下然后突然想到线段树怎么写了。

记录每个点的值上一次出现的位置，挂到线段树上，区间查询最大值，如果最大值小于 $l$$l$ 一定合法，反之不合法。

Code

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

25
int N, K;
26
int a[510000];
27
int lst[510000];
28

29
class SegTree{
30
private:
31
    int tr[510000 << 2];
32
    #define LS (p << 1)
33
    #define RS (LS | 1)
34
    #define MID ((gl + gr) >> 1)
35
public:
36
    void Pushup(int p){
37
        tr[p] = max(tr[LS], tr[RS]);
38
    }
39
    void Build(int p = 1, int gl = 1, int gr = N){
40
        if(gl == gr)return tr[p] = a[gl = gr], void();
41
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
42
        Pushup(p);
43
    }
44
    int Query(int l, int r, int p = 1, int gl = 1, int gr = N){
45
        if(l <= gl && gr <= r)return tr[p];
46
        if(gr < l || r < gl)return 0;
47
        return max(Query(l, r, LS, gl, MID), Query(l,r, RS, MID + 1, gr));
48
    }
49
}st;
50

51
int main(){
52
    freopen("A.in", "r", stdin);
53
    freopen("A.out", "w", stdout);
54
    N = read(), K = read();
55
    for(int i = 1; i <= N; ++i){
56
        int v = read();
57
        a[i] = lst[v];
58
        lst[v] = i;
59
    }st.Build();
60
    while(K--){
61
        int l = read(), r = read();
62
        printf("%s\n", st.Query(l, r) < l ? "Yes" : "No");
63
    }
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
}

T2

给定序列 $a_n$$a_n$，求其中长度为 $k$$k$ 的上升子序列个数。

DP 比较好想，然后居然没想到用树状数组或者线段树优化。。最后加上一些玄学剪枝，最坏复杂度 $O(n^{2}k)$$O(n^2k)$，显然过不了，最后只拿了 $40\mathtt{\text{pts}}$$40\texttt{pts}$，题本身挺水的，没写过我这确实很 sb。

Code

xxxxxxxxxx
66
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 (ll)(1e9 + 7)
23

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

27
int N, K;
28
ll ans(0);
29
int a[11000];
30
ll dp[11000][110];
31
basic_string < int > nxt[11000];
32

33
int main(){
34
    freopen("B.in", "r", stdin);
35
    freopen("B.out", "w", stdout);
36
    N = read(), K = read();
37
    for(int i = 1; i <= N; ++i)a[i] = read();
38
    for(int i = 1; i <= N; ++i)
39
        for(int j = i + 1; j <= N; ++j)
40
            if(a[j] > a[i])nxt[i] += j;
41
    for(int i = 1; i <= N; ++i)dp[i][1] = 1;
42
    for(int i = 1; i <= N - 1; ++i)
43
        for(int j = 1; j <= K; ++j)
44
            for(auto nx : nxt[i])
45
                (dp[nx][j + 1] += dp[i][j]) %= MOD;
46
    for(int i = 1; i <= N; ++i)(ans += dp[i][K]) %= MOD;
47
    printf("%lld\n", ans);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

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

T3

坐标系中从 $(0,0)$$(0, 0)$ 到 $(n,m)$$(n, m)$，每次只能向右或向上，同时存在 $k$$k$ 个障碍，求到达终点的方案数。

容斥 + exCRT + exLucas，奇怪题，暴力分和性质分拿到了，容斥部分想到了一大半吧，最后用 DP 容斥转移过程没想出来，最终也只拿了 $40\mathtt{\text{pts}}$$40\texttt{pts}$，寄。

Code

xxxxxxxxxx
123
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
ll N, M, K, MOD;
28
bool blk[1100][1100];
29
bool inq[1100][1100];
30
int cnt[1100][1100];
31

32
ll ans(0);
33

34
void bfs(void){
35
    cnt[0][0] = 1;
36
    queue < pair < int, int > > unex;
37
    unex.push({0, 0});
38
    inq[0][0] = true;
39
    for(int i = 1; i <= N + M; ++i){
40
        queue < pair < int, int > > tmp;
41
        while(!unex.empty()){
42
            auto tp = unex.front(); inq[tp.first][tp.second] = false; unex.pop();
43
            int tx = tp.first + 0, ty = tp.second + 1;
44
            if(tx <= N && ty <= M && !blk[tx][ty]){
45
                (cnt[tx][ty] += cnt[tp.first][tp.second]) %= MOD;
46
                if(!inq[tx][ty])inq[tx][ty] = true, tmp.push({tx, ty});
47
            }
48
            tx = tp.first + 1, ty = tp.second + 0;
49
            if(tx <= N && ty <= M && !blk[tx][ty]){
50
                (cnt[tx][ty] += cnt[tp.first][tp.second]) %= MOD;
51
                if(!inq[tx][ty])inq[tx][ty] = true, tmp.push({tx, ty});
52
            }
53
        }while(!tmp.empty())unex.push(tmp.front()), tmp.pop();
54
    }printf("%lld\n", cnt[N][M] % MOD);
55
}
56

57
ll fact[1100000], inv[1100000];
58
ll qpow(ll a, ll b){
59
    ll ret(1), mul(a);
60
    while(b){
61
        if(b & 1)ret = ret * mul % MOD;
62
        b >>= 1;
63
        mul = mul * mul % MOD;
64
    }return ret;
65
}
66
void Init(void){
67
    fact[0] = 1;
68
    for(int i = 1; i < MOD; ++i)fact[i] = (fact[i - 1] * i) % MOD;
69
    inv[MOD - 1] = qpow(fact[MOD - 1], MOD - 2);
70
    for(int i = MOD - 2; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
71
}
72

73
ll GetMinC(int n, int m){
74
    if(n < m)return 0;
75
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
76
}
77

78
ll Lucas(__int128_t n, __int128_t m){
79
    if(n < m)return 0;
80
    if(n <= MOD && m <= MOD)return GetMinC(n, m);
81
    return Lucas(n / MOD, m / MOD) * Lucas(n % MOD, m % MOD) % MOD;
82
}
83

84
int main(){
85
    freopen("C.in", "r", stdin);
86
    freopen("C.out", "w", stdout);
87
    N = read < ll >(), M = read < ll >(), K = read(), MOD = read();
88
    Init();
89
    if(!K){
90
        printf("%lld\n", Lucas((__int128_t)N + M, (__int128_t)N));
91
        // bfs();
92
    }else{
93
        // if(N <= 1000 && M <= 1000){
94
            for(int i = 1; i <= K; ++i){int x = read(), y = read(); blk[x][y] = true;}
95
            bfs();
96
        // }else{
97
            // (ans += Lucas((__int128_t)N + M, (__int128_t)N)) %= MOD;
98
            // for(int len = 1; len <= K; ++len){
99
            //     ans += Lucas((__int128_t))
100
            // }
101
        // }
102
    }
103
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
104
    return 0;
105
}
106

107

108

109
template < typename T >
110
inline T read(void){
111
    T ret(0);
112
    int flag(1);
113
    char c = getchar();
114
    while(c != '-' && !isdigit(c))c = getchar();
115
    if(c == '-')flag = -1, c = getchar();
116
    while(isdigit(c)){
117
        ret *= 10;
118
        ret += int(c - '0');
119
        c = getchar();
120
    }
121
    ret *= flag;
122
    return ret;
123
}

T4

对树染色，要求相邻两点颜色不同，每个节点有一个序列表示可能被染的颜色，颜色共有 $k$$k$ 种，求合法染色方案数。

很 sb 的树形 DP，做过好几次类似题了，居然只糊了一个 $O(n^{2}k)$$O(n^2k)$ 的 DP，然后没对拍，还似乎写挂了，直接爆零。

稍微动点脑子基本就能想到不用 $O(n^{2}k)$$O(n^2k)$ 枚举，直接加上所有的减去颜色相同的即可 $O(1)$$O(1)$。。。

Code

xxxxxxxxxx
88
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 (ll)(1e9 + 7)
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[11000];
32
ROPNEW(ed);
33
Edge* head[5100];
34

35
int N, K;
36
unordered_set < int > exist[5100];
37
ll dp[5100][5100];
38

39
void dfs(int p = 1, int fa = 0){
40
    for(auto i = head[p]; i; i = i->nxt)
41
        if(SON != fa)dfs(SON, p);
42
    if(!head[p]->nxt && p != 1)
43
        for(auto ex : exist[p])dp[p][ex] = 1;
44
    else{
45
        for(auto ex : exist[p])
46
            for(auto i = head[p]; i; i = i->nxt)
47
                if(SON != fa)
48
                    for(auto exs : exist[SON])
49
                        if(exs != ex)
50
                            (dp[p][ex] += dp[SON][exs]) %= MOD;
51
    }
52
}
53

54
int main(){
55
    freopen("D.in", "r", stdin);
56
    freopen("D.out", "w", stdout);
57
    N = read(), K = read();
58
    for(int i = 1; i <= N; ++i){
59
        int c = read();
60
        while(c--)exist[i].insert(read());
61
    }
62
    for(int i = 1; i <= N - 1; ++i){
63
        int s = read(), t = read();
64
        head[s] = new Edge{head[s], t};
65
        head[t] = new Edge{head[t], s};
66
    }dfs();
67
    ll ans(0);
68
    for(auto ex : exist[1])(ans += dp[1][ex]) %= MOD;
69
    printf("%lld\n", ans);
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

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

正解

T2

$O(n^{2}k)$$O(n^2k)$ 的 DP 十分显然，用树状数组优化一下转移即可。

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
#define MOD (ll)(1e9 + 7)
23

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

27
int N, K;
28
ll ans(0);
29
int a[11000];
30
ll dp[11000][110];
31
basic_string < int > data;
32
// basic_string < int > nxt[11000];
33

34
class BIT{
35
private:
36
    int tr[11000];
37
public:
38
    int lowbit(int x){return x & -x;}
39
    void Modify(int x, int v = 1){while(x <= N)(tr[x] += v) %= MOD, x += lowbit(x);}
40
    ll Query(int x){ll ret(0); while(x)(ret += tr[x]) %= MOD, x -= lowbit(x); return ret;}
41
}bit[110];
42

43
int main(){
44
    freopen("B.in", "r", stdin);
45
    freopen("B.out", "w", stdout);
46
    N = read(), K = read();
47
    for(int i = 1; i <= N; ++i)a[i] = read(), data += a[i];
48
    sort(data.begin(), data.end());
49
    data.erase(unique(data.begin(), data.end()), data.end());
50
    for(int i = 1; i <= N; ++i)a[i] = distance(data.begin(), upper_bound(data.begin(), data.end(), a[i]));
51
    for(int i = 1; i <= N; ++i)dp[i][1] = 1;
52
    for(int i = 1; i <= N; ++i)
53
        for(int j = 1; j <= K; ++j)
54
            (dp[i][j] += bit[j - 1].Query(a[i] - 1)) %= MOD,
55
            bit[j].Modify(a[i], dp[i][j]);
56
    // for(int i = 1; i <= N; ++i)printf("dp[%d][%d] = %lld\n", i, K, dp[i][K]);
57
    for(int i = 1; i <= N; ++i)(ans += dp[i][K]) %= MOD;
58
    printf("%lld\n", ans);
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
}

T3

先把前面题补一补然后刷刷 exLucas 之类的再补这道题吧。。

Code

xxxxxxxxxx
1
1
//TODO

T4

树形 DP，设 $dp(i,j)$$dp(i, j)$ 表示染完 $i$$i$ 子树，其根节点颜色为 $j$$j$ 的合法方案数，转移很显然，加上所有颜色和减去不合法的然后把所有子树乘起来即可。

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(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 (ll)(1e9 + 7)
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[11000];
32
ROPNEW(ed);
33
Edge* head[5100];
34

35
int N, K;
36
basic_string < int > exist[5100];
37
ll sum[5100];
38
ll dp[5100][5100];
39

40
void dfs(int p = 1, int fa = 0){
41
    for(auto i = head[p]; i; i = i->nxt)
42
        if(SON != fa)dfs(SON, p);
43
    if(!head[p]->nxt && p != 1)
44
        for(auto ex : exist[p])dp[p][ex] = 1, sum[p]++;
45
    else{
46
        for(auto ex : exist[p]){
47
            dp[p][ex] = 1;
48
            for(auto i = head[p]; i; i = i->nxt)
49
                if(SON != fa)
50
                    (dp[p][ex] *= (sum[SON] - dp[SON][ex] + MOD) % MOD) %= MOD;
51
            (sum[p] += dp[p][ex]) %= MOD;
52
        }
53
    }
54
}
55

56
int main(){
57
    freopen("D.in", "r", stdin);
58
    freopen("D.out", "w", stdout);
59
    N = read(), K = read();
60
    for(int i = 1; i <= N; ++i){
61
        int c = read();
62
        while(c--)exist[i] += read();
63
    }
64
    for(int i = 1; i <= N - 1; ++i){
65
        int s = read(), t = read();
66
        head[s] = new Edge{head[s], t};
67
        head[t] = new Edge{head[t], s};
68
    }dfs();
69
    // for(int i = 1; i <= N; ++i)printf("sum[%d] = %lld\n", i, sum[i]);
70
    printf("%lld\n", sum[1]);
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-2022_11_22 初稿