首页 模拟赛

考裂开了。

结论，线段树，树上期望dp，恶心题

# A. 签到题（qiandao）

nt 结论题。

一个点度数模 cc 不为 0 有 1 的代价，否则没有代价。

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
#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} 
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e6 + 10;
int n, m, k, c;
int deg[N];

signed main(){
//    freopen("qiandao.in", "r", stdin);
//    freopen("qiandao.out", "w", stdout);
    n = read(), m = read(), k = read(), c = read();
    for(int i = 1; i <= k; ++i){
        int u = read(), v = read();
        deg[u]++, deg[v + n]++;
    }
    int ans = 0;
    for(int i = 1; i <= n + m; ++i)
        ans += (deg[i] % c != 0);
    write(ans), puts("");
    return 0;
}

# B. M 弟娃（magic）

线段树裸题。

判一下祖先关系什么的，然后线段树上区间加。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

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

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

const int N = 3e5 + 10;
int n, m;
vector <int> G[N];
int fa[N][20], dfn[N], tim, dep[N], siz[N];

inline void dfs(int x, int f){
    fa[x][0] = f, dep[x] = dep[f] + 1, dfn[x] = ++tim, siz[x] = 1;
    for(int i = 1; i <= 19; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(auto y : G[x]){
        if(y == f) continue;
        dfs(y, x), siz[x] += siz[y];
    }
}

inline int jump(int x, int p){
    for(int i = 19; i >= 0; --i)
        if(dfn[fa[x][i]] > dfn[p]) x = fa[x][i];
    return x;
}


#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)

int tag[N << 2], mx[N << 2];

inline void pushup(int rt){
    mx[rt] = max(mx[ls], mx[rs]);
}

inline void pushdown(int rt){
    if(tag[rt]){
        mx[ls] += tag[rt], mx[rs] += tag[rt];
        tag[ls] += tag[rt], tag[rs] += tag[rt];
        tag[rt] = 0;
    }
}

inline void upd(int L, int R, int l = 1, int r = n, int rt = 1){
    if(L > R || L > r || R < l) return;
    if(L <= l && r <= R) return tag[rt]++, mx[rt]++, void();
    pushdown(rt);
    upd(L, R, l, mid, ls), upd(L, R, mid + 1, r, rs);
    pushup(rt);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = 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 <= m; ++i){
        int x = read(), y = read();
        if(dfn[x] > dfn[y]) swap(x, y);
        if(x == y){
            upd(1, n);
        }else if(dfn[y] <= dfn[x] + siz[x] - 1){
            x = jump(y, x);
            upd(dfn[y], dfn[y] + siz[y] - 1), upd(1, dfn[x] - 1);
            upd(dfn[x] + siz[x], n);
        }else{
            upd(dfn[x], dfn[x] + siz[x] - 1);
            upd(dfn[y], dfn[y] + siz[y] - 1);
        }
        write(mx[1]), puts("");
    }
    return 0;
}

# C. 变异大老鼠（arrest）

由于题目里说了 1∼i1 \sim i 的最短路只有 1 条，所以建出来就是一颗树。

然后就是裸的树上背包。

设 fx,if_{x, i} 表示 xx 子树内放了 ii 个警察抓到的期望。

转移就背包转移，注意还要给 xx 节点上放警察单独转移。

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
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;

const int N = 310;
const int M = 3e4 + 10;
int n, m, k;
struct node{
    int v, w, nxt;
}edge[M << 1];
int head[N], tot;

inline void add(int x, int y, int z){
    edge[++tot] = (node){y, z, head[x]};
    head[x] = tot;
} 

typedef pair<int, int> P;
int dis[N], vis[N], fr[N];

inline void dij(){
    priority_queue <P, vector<P>, greater<P> > q;
    memset(dis, 0x3f, sizeof(dis));
    q.push(P(0, 1)), dis[1] = 0;
    while(!q.empty()){
        int x = q.top().se; q.pop();
        if(vis[x]) continue; vis[x] = 1;
        for(int i = head[x]; i; i = edge[i].nxt){
            int y = edge[i].v;
            if(dis[y] > dis[x] + edge[i].w){
                dis[y] = dis[x] + edge[i].w, fr[y] = x;
                q.push(P(dis[y], y));
            }
        }
    }
}

vector <int> G[N];
double f[N][N], p[N][N];

inline void dfs(int x){
    for(auto y : G[x]){
        dfs(y);
        for(int i = k; i >= 0; --i)
            for(int j = 1; j <= i; ++j)
                f[x][i] = max(f[x][i], f[x][i - j] + f[y][j] * (1.0 / G[x].size()));
    }
    for(int i = k; i >= 0; --i)
        for(int j = 1; j <= i; ++j)
            f[x][i] = max(f[x][i], f[x][i - j] * (1.0 - p[x][j]) + p[x][j]);
}

signed main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; ++i){
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= k; ++j) scanf("%lf", &p[i][j]);
    dij();
    for(int i = 2; i <= n; ++i) G[fr[i]].pb(i);
    dfs(1);
    printf("%.10lf\n", f[1][k]);
    return 0;
}

# D. 朝鲜时蔬（vegetable）

神秘题。

读题分有 40，比较简单的部分分有 70.

但是这里都不讲了，要看题解去这里

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int mod = 1e9 + 7;
int n, m, k, tn;

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

inline int inv(int x) {return qpow(x, mod - 2);}

inline void calc21(){
    int res = 0;
    for(int l = 1, r; l <= tn; l = r + 1){
        r = tn / (tn / l);
        res = (res + (r - l + 1) * (tn / l - 1) % mod) % mod;
    }
    cout << res << '\n';
}

inline void calc32(){
    int res = 0, inv2 = inv(2);
    for(int l = 3, r; l <= tn; l = r + 1){
        r = tn / (tn / l);
        int len, c = 0, tl, tr;
        tl = l, tr = r;
        if(l % 2 == 0) tl++, c = (c + (l % mod * inv2 % mod - 1 + mod) % mod) % mod;
        if(r % 2 == 1) tr--, c = (c + ((r + 1) % mod * inv2 % mod - 1 + mod) % mod) % mod;
        tl %= mod, tr %= mod;
        len = (tr - tl + mod + 1) % mod * inv2 % mod;
        int a = ((tl + 1) * inv2 % mod - 1 + mod) % mod, b = (tr * inv2 % mod - 1 + mod) % mod;
        res = (res + (2 * (a + b) % mod * len % mod * inv2 % mod + c) % mod * (tn / l) % mod) % mod;
    }
    cout << res << '\n';
}

inline void calc42(){
    if(tn == 4) cout << 1 << '\n';
    else if(tn < 11){
        int ans = 0;
        for(int a = 1; a <= n; ++a)
            for(int b = a + 1; b <= n; ++b)
                for(int c = b + 1; c <= n; ++c)
                    for(int d = c + 1; d <= n; ++d){
                        int s = a + b + c + d, t = 0;
                        t += (s % (a + b) == 0) + (s % (a + c) == 0) + (s % (a + d) == 0) + (s % (b + c) == 0) + (s % (b + d) == 0) + (s % (c + d) == 0);
                        ans += (t == 3);
                    }
        cout << ans << '\n';
    }else cout << (tn / 11 + tn / 29) % mod << '\n';
}

inline int S3(int n){
    int tn = n; n %= mod;
    int sum = n * (n + 1) % mod * (2 * n + 1) % mod * inv(6) % mod;
    sum = (sum - 6 * (n * (n + 1) % mod * inv(2) % mod) % mod + mod) % mod;
    sum = (sum + 5 * n) % mod;
    sum = (sum + 3 * (tn / 2) % mod + 4 * (tn / 3) % mod) % mod;
    return sum;
}

inline void calc43(){
    if(tn == 4) cout << "1\n";
    else if(tn == 5) cout << "5\n";
    else{
        int ans = 0;
        for(int l = 1, r; l <= tn; l = r + 1){
            r = tn / (tn / l);
            ans = (ans + (tn / l) % mod * (S3(r) - S3(l - 1) + mod) % mod) % mod;
        }
        cout << ans * inv(12) % mod << '\n';
    }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m >> k, tn = n;
    n %= mod;
    
    if(m == 1 && k == 1) return cout << n % mod << '\n', 0;
    if(m == 2 && k == 2) return cout << n * (n - 1) % mod * qpow(2, mod - 2) % mod << '\n', 0;
    if(m == 3 && k == 3) return cout << n * (n - 1) % mod * (n - 2) % mod * qpow(6, mod - 2) % mod << '\n', 0;
    if(m == 4 && k == 4) return cout << n * (n - 1) % mod * (n - 2) % mod * (n - 3) % mod * qpow(24, mod - 2) % mod << '\n', 0; 
    
    if(m == 2 && k == 1) return calc21(), 0;
    if(m == 3 && k == 1) return cout << tn / 3 % mod << '\n', 0;
    if(m == 3 && k == 2) return calc32(), 0;

    if(m == 4 && k == 1) return cout << (tn <= 5 ? 1 : (tn / 6 + tn / 9 + tn / 10 + tn / 12 + tn / 15 + tn / 21) % mod) << '\n', 0;
    if(m == 4 && k == 2) return calc42(), 0;
    if(m == 4 && k == 3) return calc43(), 0;
    return 0;
}

更新于 阅读次数 次