首页 模拟赛

数论，树状数组 + 按右端点排序再扫一遍，树上背包

# A. gcd

考过原题。

一个非常显然的结论（假设 a>ba > b ）：

gcd⁡(a,b)<=a−ba⊕b>=a−b\gcd(a, b) <= a - b\\ a \oplus b >= a - b

那么我们先枚举一个数 ii 作为 gcd⁡\gcd，然后枚举它的倍数 j (2×i≤j≤n)j\ (2 \times i \leq j \leq n)，判断 j⊕(j−i)j \oplus (j - i) 是否等于 ii，是的话就让答案加 1。

1
2
3
4
5
n = read();
for(int i = 1; i <= n; ++i)
    for(int j = i + i; j <= n; j += i)
        if(j ^ (j - i) == i) ans++;
write(ans), puts("");

# B. max

同样有原题（就是多了个多测）。

类似于 【HH 的项链】 这道题。

考场上的暴力：把每个数的因数全都预处理出来，然后每次查询 l∼rl \sim r 时，把 l∼rl \sim r 中所有数的因数全都放到桶里，答案就是最大的出现至少两次的数，再整个莫队优化一下。

复杂度我也不知道是多少，反正是过不了 QwQ

现在来说正解：

首先还是要把每个数的因数全都预处理出来，然后把询问按照右端点排序。

从左到右依次枚举每一个数 aia_i，然后枚举 aia_i 的所有因数，判断这个因数之前是否出现过（出现过两次及以上就可以当作 gcd⁡\gcd），如果出现过就把这个因数插到树状数组第 lastposlastpos 位上，维护一个前缀最大值。

注意时刻更新 lastposlastpos。

查询的时候枚举以当前点 ii 为右端点的询问，在树状数组上查询 q[i].lq[i].l 为左端点的后缀最大值，就是答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
typedef pair<int, int> P;
int n, m, T;
int a[N];
vector <int> num[N];
vector <P> q[N];

namespace BIT{
    int c[N];

    inline void add(int x, int y){
        for(; x > 0; x -= x & (-x)) c[x] = max(c[x], y);
    }

    inline int qry(int x){
        int res = 0;
        for(; x <= n; x += x & (-x)) res = max(res, c[x]);
        return res;
    }
}
using namespace BIT;

int lst[N], ans[N];

inline void solve(){
    for(int i = 1; i <= n; ++i){
        for(auto x : num[a[i]]) add(lst[x], ~lst[x] ? x : 0), lst[x] = i;
        for(auto x : q[i]) ans[x.se] = qry(x.fi);
    }
}

inline void Clear(){
    for(int i = 1; i <= n; ++i) q[i].clear();
    memset(ans, 0, sizeof(ans));
    memset(lst, -1, sizeof(lst));
    memset(c, 0, sizeof(c));
}

signed main(){
    // freopen("max.in", "r", stdin);
    // freopen("max.out", "w", stdout);
    for(int i = 1; i < N; ++i)
        for(int j = i; j < N; j += i) num[j].pb(i);
    T = read();
    while(T--){
        n = read(), Clear();
        for(int i = 1; i <= n; ++i) a[i] = read();
        m = read();
        for(int i = 1, l, r; i <= m; ++i)
            l = read(), r = read(), q[r].pb(P(l, i));
        solve();
        for(int i = 1; i <= m; ++i) write(ans[i]), puts("");
    }
    return 0;
}

# C. colour

（lndjy{\text{\color{black}l\color{Red}{ndjy}}} 在 Luogu 上放了道私题，就不放链接了）

非常妙的树形背包。

设 fx,if_{x, i} 表示以 xx 为根的子树内与 xx 颜色相同的联通块大小为 ii 时合法的方案树，不考虑颜色。

设 sumxsum_x 表示以 xx 为根的子树内，colx≠colfa[x]col_x \neq col_{fa[x]} 且其他所有条件都符合的方案数，即：

sumx=∑i=1min⁡(l,siz[x])fx,i×(k−1)sum_x = \sum_{i = 1}^{\min(l, siz[x])} f_{x, i} \times (k - 1)

乘 (k−1)(k - 1) 是因为不能和父亲的颜色相同。

然后再来看 fx,if_{x, i} 如何转移。

分两种情况讨论：

  • xx 的儿子 yy 和 xx 颜色相同，那么就是树上背包板题了，先枚举与 xx 颜色相同的联通块大小，然后枚举 yy 子树内与 yy 颜色相同的联通块大小（此时 colx=colycol_x = col_y），那么有：

    fx,i=∑jfx,j×fy,i−jf_{x, i} = \sum_{j}f_{x, j} \times f_{y, i - j}

  • 儿子 yy 的颜色与 xx 不相同，那就很简单了，直接令 fx,if_{x, i} 乘上 sumysum_y 再加上刚才背包计算出来的结果就行。

    （至于为什么能直接乘 sumysum_y，我只能说 sumysum_y 的定义实在是巧妙）

注意最后的答案是 ∑i=1l(f1,i×k)\sum\limits_{i = 1}^l (f_{1, i} \times k)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
#define pb push_back
#define get_B(x) x / B

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
const int mod = 998244353;
int n, k, l, ans;
vector <int> g[N];
int f[N][210], siz[N], sum[N];

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int mul(int a, int b) {return 1ll * a * b % mod;}

inline void dfs(int x, int fa){
    f[x][1] = siz[x] = 1;
    for(auto y : g[x]){
        if(y == fa) continue;
        dfs(y, x);
        int sizu = siz[x]; siz[x] += siz[y];
        for(int i = min(l, siz[x]); i >= 1; --i){
            int res = 0;
            for(int j = min(i - 1, siz[y]); j >= max(1, i - sizu); --j)
                res = add(res + mul(f[x][i - j], f[y][j]));// x 与 y 颜色相同
            f[x][i] = add(res + mul(f[x][i], sum[y]));// x 与 y 颜色不同
        }
    }
    if(siz[x] == 1) sum[x] = k - 1;
    else for(int i = min(l, siz[x]); i >= 1; --i) sum[x] = add(sum[x] + mul(f[x][i], k - 1));
}

signed main(){
    n = read(), k = read(), l = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read();
        g[u].pb(v), g[v]. pb(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= l; ++i) ans = add(ans + f[1][i]);
    write(mul(ans, k)), puts("");
    return 0;
}

# D. temmie

还不会，咕咕咕。

更新于 阅读次数 次