Luobuyu's Blog

0%

hdu多校(第六场)

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 9.7k 阅读时长 ≈ 9 分钟
2020年hdu暑期多校训练(第六场)，题目虽然比较水，但是还是有些知识没学过

A. Road To The 3rd Building

题目描述：

给出一个序列，求所有区间平均值的期望 $ 1\le i \le n, i \le j \le n $

数据范围：
$ 1\le T \le 20 \\ 1\le n \le 2 \times 10^5 , \sum n \le 10^6 \\ 1 \le s_i \le 10^9 $

题解：

计算每个数的系数，单独计算每个数对答案的贡献。每个数的系数与上个数相似，减去中间部分再加上即可。

代码：

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>

#define log(x...) fprintf(stderr, x)
#define SUM(l, r) ((sum[r] - sum[(l) - 1] + mod) % mod)

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 0, ch = getchar();
    while (!isdigit(ch)) ch == '-' && (f = 1), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

void test(int n)
{
    for (int k = 1; k <= n; ++ k)
    {
        for (int i = 1; i <= n; ++ i)
            log("%d ", min(min(n - k + 1, k), min(i, n - i + 1)));
        log("\n");
        fflush(stderr);
    }
}

const int N = 2e5 + 5;
const longs mod = 1e9 + 7;
longs inv[N], sum[N], w[N], s[N];

void initInverse(int n, longs p)
{
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = (p - p / i) * inv[p % i] % p;
    inv[0] = 0;
}

int main()
{

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    initInverse(N, mod);
    for (int i = 1; i <= N; ++ i)
        sum[i] = (sum[i - 1] + inv[i]) % mod;
    int t = nextInt();
    while (t --)
    {
        int n = nextInt();
        auto half = n / 2 + bool(n % 2);
        for (int i = 1; i <= n; ++ i)
            s[i] = nextInt();
        w[1] = SUM(1, n);
        for (int i = 2; i <= half; ++ i)
            w[i] = (((w[i - 1] - (i - 1) * SUM(i, n - i + 1) % mod) % mod + mod) % mod + i * SUM(i, n - i + 1) % mod) % mod;
        for (int i = n; i > half; -- i)
            w[i] = w[n - i + 1];
        longs ans = 0, all = inv[n] * inv[n + 1] % mod * 2 % mod;
        for (int i = 1; i <= n; ++ i)
            ans += w[i] * s[i] % mod, ans %= mod;
        ans = ans * all % mod;
        printf("%lld\n", ans);
    }
    return 0;
}

B. Little Rabbit’s Equation

题目描述：

给出一个计算式，判断是几进制的，不存在输出 $ -1 $

数据范围：
$ 1\le |s| \le 15 $

题解：

把字符数字存起来，然后枚举进制判断是否满足。注意除法需要整除。

代码：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 100 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;

char s[maxn];
vector<int> num[4];
int maxx;
char op;
void getNum()
{
    for(int i = 1; i <= 3; i++)
    {
        num[i].clear();
    }
    int len = strlen(s + 1);
    int now = 1;
    for (int i = 1; i <= len; i++)
    {
        if ((s[i] >= '0' && s[i] <= '9') || (s[i] >= 'A' && s[i] <= 'F'))
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                num[now].push_back(s[i] - '0');
                maxx = max(maxx, s[i] - '0' + 1);
            }
            else
            {
                num[now].push_back(s[i] - 'A' + 10);
                maxx = max(maxx, s[i] - 'A' + 11);
            }
        }
        else
        {
            now++;
            if(s[i] != '=')
            {
                op = s[i];
            }
        }
    }
}
ll getMaxxNum(int x, int maxx)
{
    ll ret = 0;
    for(int i = 0; i < num[x].size(); i++)
    {
        ret = ret * maxx + (ll)num[x][i];
    }
    return ret;
}
int getAns()
{
    for(int i = maxx; i <= 16; i++)
    {
        ll a = getMaxxNum(1, i);
        ll b = getMaxxNum(2, i);
        ll c = getMaxxNum(3, i);
        ll tmp = 0;
        if(op == '+') tmp = a+ b;
        else if(op == '-') tmp = a - b;
        else if(op == '*') tmp = a * b;
        else
        {
            if(b == 0 || a % b)
                continue;
            tmp = a / b;
        }
        if(tmp == c)
            return i;
    }
    return -1;
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第六场/1002/data.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    while(scanf("%s", s + 1) != EOF)
    {
        maxx = 2;
        getNum();
        printf("%d\n", getAns());
    }
    return 0;
}

C.

题目描述：

数据范围：

题解：

代码：

1
2


D.

题目描述：

数据范围：

题解：

代码：

1
2


E. Fragrant numbers

题目描述：

给出字符串 $ “1145141919” $ ，该串可以重复多次。字符串加上括号、加或乘得到一个表达式，使表达式的值为 $ N $

数据范围：
$ 1\le T \le 30 \\\\ 1\le N \le 5000 $

题解：

看着像一个 $ dp $ ，就是一个区间 $ dp $ ，使用 $ set $ 存数就行了。盲猜答案都比较小，毕竟 $ 5000 $ 才对应 $ 8 $ ，写个暴力跑一下发现都小于 $ 13 $ 。所以把 $ 13 $ 作为最大长度直接使用区间 $ dp $ 即可。

代码：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 10 + 3;
const int maxm = 5e3 + 10;
int t, n, m, k;

set<int> dp[maxn][maxn];
int a[maxn] = {0, 1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 1, 1};
int ans[maxm];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第六场/1005/in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    for (int i = 1; i < maxn; i++)
    {
        int tmp = 0;
        for (int j = i; j <= min(i + 3, maxn - 1); j++)
        {
            tmp = tmp * 10 + a[j];
            if (tmp <= 5000)
                dp[i][j].insert(tmp);
        }
    }
    for (int len = 2; len < maxn; len++)
    {
        for (int i = 1; i + len - 1 < maxn; i++)
        {
            int j = i + len - 1;
            for (int k = i; k < j; k++)
            {
                if (dp[i][k].size() && dp[k + 1][j].size())
                {
                    for (auto u : dp[i][k])
                    {
                        for (auto v : dp[k + 1][j])
                        {
                            if (u + v <= 5000)
                                dp[i][j].insert(u + v);
                            if (u * v <= 5000)
                                dp[i][j].insert(u * v);
                        }
                    }
                }
            }
        }
    }
    for (int i = 1; i < maxn; i++)
    {
        for (auto it : dp[1][i])
        {
            if (ans[it] == 0)
            {
                ans[it] = i;
            }
        }
    }
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        if(ans[n] != 0)
        {
            printf("%d\n", ans[n]);
        }
        else
        {
            printf("-1\n");
        }
        }
    return 0;
}

F. A Very Easy Graph Problem

题目描述：

给出一张图，边权为 $ 2^i $ ，每个点有个值 $ 0或1 $ ，计算

$ \sum_{i=1}^{n}\sum_{j=1}^{n}d(i,j)\times [a_i=1\wedge a_j=0] $

数据范围：
$ 1\le T \le 8 \\ 1\le n \le 10^5 \\ 1\le m \le 2\times 10^5 \\ \sum n ,\sum m \le 2 \times 10^5 $

题解：

注意边权，边权为 $ 2^i $ 这么特殊一定有某种用处。

前 $ i-1 $ 条边权值和 $ 2^i - 2 \le 2^i $ ，所以如果在前 $ i-1 $ 边之内两点已经连通了，则第 $ i $ 条边不会用上，否则的话才会用上。可以转化为最小生成树。

计算这个值的话，肯定是统计每条边的贡献，对于 $ [1,0] $ 只满足一次，所以只需要记一次。统计每个点左右两侧 $ 0 $ 和 $ 1 $ 的数量，最后 $ 1 $ 和 $ 0 $ 组合计算即可。

2020-08-07 19.28.35

代码：

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
105
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 2e5 + 10;
const int maxm = 2e5 + 10;
int t, n, m, k;
int sum[maxn][3];
int one, zero;
ll ans;
struct Edge
{
    int v, next;
    ll w;
} edge[maxm << 1];
int head[maxn], cnt;
bool vis[maxn];
inline void addEdge(int u, int v, ll w = 0)
{
    ++cnt;
    edge[cnt] = {v, head[u], w};
    head[u] = cnt;
}

int fa[maxn];
int findFa(int u) { return u == fa[u] ? u : (fa[u] = findFa(fa[u])); }

void init(int n)
{
    one = zero = ans = cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        sum[i][0] = sum[i][1] = 0;
        fa[i] = i;
        head[i] = 0;
    }
}

void dfs(int u, int p)
{
    sum[u][0] = sum[u][1] =  0;
    sum[u][sum[u][2]]++;
    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == p) continue;
        dfs(v, u);
        sum[u][0] += sum[v][0];
        sum[u][1] += sum[v][1];
    }

    for (int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v==p)
            continue;
        ans = (ans + 1LL * sum[v][0] * (one - sum[v][1]) % mod * edge[i].w % mod) % mod;
        ans = (ans + 1LL * sum[v][1] * (zero - sum[v][0]) % mod * edge[i].w % mod) % mod;
    }
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        init(n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &sum[i][2]);
            if (sum[i][2])
                one++;
            else zero++;
        }
        int u, v;
        ll w = 1;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &u, &v);
            w = w * 2 % mod;
            int up = findFa(u), vp = findFa(v);
            if(up == vp)
                continue;
            fa[up] = vp;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        dfs(1, -1);
        printf("%lld\n", ans);
    }
    return 0;
}

G.

题目描述：

数据范围：

题解：

代码：

1
2


H.

题目描述：

数据范围：

题解：

代码：

1
2


I. Divisibility

题目描述：

一个命题：

任意一个 $ b $ 进制数 $ y $ ，将各位相加（如果位数大于 $ 1 $ ，继续加）如果得到的数能被 $ x $ 整除，则 $ y $ 能够被 $ x $ 整除。

给出 $ b $ ， $ x $ 判断命题真假

数据范围：
$ 1\le t \le 10^5 \\ 2 \le b, x \le 10^{18} $

题解：

当 $ b \% x \equiv 1 $ 时成立，其他都不成立

$ y \equiv c_1 b^{n-1} + c_2 b^{n-2} + \cdots + c_n b^0 \equiv c_1 + c_2 + \cdots + c_n \pmod{x} = y’ $

代码：

1
略

J. Expectation

题目描述：

一个无向图，求所有生成树权值的期望，生成树的权值定义为所有边的按位与。

数据范围：
$ 1\le t \le 10 \\ 2 \le n \le 100 \\ 1\le m \le 10^4 \\ 1\le w \le 10^9 $

题解：

突破口肯定是在权值与上。求所有的生成树需要使用矩阵树定理。

期望最基础的性质就是期望的和等于和的期望，即 $ E(X + Y) = E(X) + E(Y) $ 。知道这个性质那么有一个很正常的想法就是拆位，因为每一位在按位与的过程中都是相互独立的。单独统计每一位的期望。

现在我们直接枚举二进制的每一位 $ i $ ，对于这一位，如果 $ w_{u, v} $ 的第 $ i $ 位不为 $ 0 $ ，那么我们就直接在 $ u, v $ 直接连一条边。那么对于这张新图，每有一个生成树，那么都会对答案贡献 $ \frac{2^i}{sum} $ ， $ sum $ 是指原图中生成树的个数。用无向图的矩阵树定理就能求出生成树的个数，这道题的整体复杂度是 $ O(Tn^3\log{w} ) $ 。

代码：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 998244353;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 100 + 10;
const int maxm = 1e4 + 10;
int t, n, m, k;

struct Edge
{
    int u, v, w;
} edge[maxm];

ll f[maxn][maxn];
ll gauss(int l = 1, int r = n)
{
    ll ans = 1;
    for(int i = l; i <= r; i++)
    {
        for(int j = i + 1; j <= r; j++)
        {
            while(f[j][i])
            {
                ll t = f[i][i] / f[j][i];
                for(int k = i; k <= r; k++)
                    f[i][k] = (f[i][k] - t * f[j][k] + mod) % mod;
                swap(f[i], f[j]);
                ans = -ans;
            }
        }
        ans = (ans * f[i][i]) % mod;
    }
    return (ans + mod) % mod;
}



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

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第六场/1010/data/1.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &m);
        memset(f, 0, sizeof(f));
        memset(edge, 0, sizeof(edge));
        int u, v, w;
        for (int i = 1; i <= m; ++i)
        {
            scanf("%d %d %d", &u, &v, &w);
            edge[i] = {u, v, w};
            f[u][u]++, f[v][v]++;
            f[u][v]--, f[v][u]--;
        }
        ll sum = gauss(1, n - 1);
        ll ans = 0;
        for(int i = 0; i <= 30; i++)
        {
            memset(f, 0, sizeof(f));
            for(int j = 1; j <= m; j++)
            {
                if(edge[j].w & (1 << i))
                {
                    u = edge[j].u;
                    v = edge[j].v;
                    f[u][u]++, f[v][v]++;
                    f[u][v]--, f[v][u]--;
                }
            }
            ll tmp = gauss(1, n - 1);
            ans = (ans + 1LL * (1 << i) * tmp % mod) % mod;
        }
        printf("%lld\n", ans * qpow(sum, mod - 2, mod) % mod);
    }
    return 0;
}

K.

题目描述：

数据范围：

题解：

代码：

1
2