Luobuyu's Blog

0%

hdu多校(第四场)

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 9k 阅读时长 ≈ 8 分钟
2020年hdu暑期多校训练(第四场)，基础题目搞了些非常规操作

A.

题目描述：

数据范围：

题解：

代码：

1
2


B. Blow up the Enemy

题目描述：

$ n $ 把武器，每把拥有伤害 $ a_i $ 和冷却时间 $ d_i $ ，父亲随机选择一把，小明选择一把，求小明赢的最大概率

数据范围：略

题解：

计算每把武器获得胜利所需要的时间 $ (ceil(100/a_i) - 1) \times d_i $ 注意需要减一。然后排序，与最小的时间相同的概率都是 $ 0.5 / n $ ，其他的则为 $ 1 / n $

代码：

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>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e3 + 10;
int t, n, m, k;

int a[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &t);
    int x, y;
    while (t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%d", &x, &y);
            a[i] = (ceil(100.0 / x) - 1) * y;
        }
        sort(a + 1, a + 1 + n);
        int tot = 0, tmp = a[1];
        for (int i = 1; i <= n; i++)
        {
            if(a[i] == tmp)
            {
                tot++;
            }
        }

        printf("%.10f\n", 0.5 / n * tot + 1.0 / n * (n - tot));
    }
    return 0;
}

C. Contest of Rope Pulling

题目描述：

image-20200731165551930.png

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

$ 1\le n, m \le 1000 $

$ 1\le w_i \le 1000, -10^9 \le v_i \le 10^9 $

题解：

对第二个班级的 $ w_i $ 取反，可以使用 $ 0-1 $ 背包，使用一维空间即可。

如果直接按照输入 $ dp $ 的话， $ w $ 一直为正累加会有 $ 1e6 $ ，值域太大了，可以用用 $ random\_shuffle $ 随机化一下位置，这样大概可以保证前面的 $ w $ 和在 $ 0 $ 附近上下浮动了。

代码：

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(NULL));
const ll INF = 1e18;
const int N = 2005, M = 200005, bas = M / 2;
struct node { int ty, w, v; } a[N<<1];
int n, m, lim, L, R;
ll F[M], G[M];

void cmax(ll &x, ll y){
    if (y > x) x = y;
}

ll solve() {
    cin >> n >> m;
    for (int i = 1; i <= n + m; i ++) {
        cin >> a[i].w >> a[i].v;
        a[i].ty = (i <= n ? 1 : -1);
    }
    shuffle(a + 1, a + n + m + 1, rnd);
    lim = sqrt(n + m) * 1000 * 2;
    ll *f = F + bas, *g = G + bas;
    f[L = R = 0] = 0;
    for (int i = 1; i <= n + m; i ++) {
        if (a[i].ty == 1) {
            int nR = min(R + a[i].w, lim);
            for (int j = L; j <= R; j ++) {
                g[j] = f[j];
            }
            for (int j = R + 1; j <= nR; j ++) {
                g[j] = -INF;
            }
            for (int j = L; j <= nR - a[i].w; j ++) {
                cmax(g[j + a[i].w], f[j] + a[i].v);
            }
            R = nR;
        }
        else {
            int nL = max(L - a[i].w, -lim);
            for (int j = L; j <= R; j ++) {
                g[j] = f[j];
            }
            for (int j = nL; j <= L - 1; j ++) {
                g[j] = -INF;
            }
            for (int j = nL + a[i].w; j <= R; j ++) {
                cmax(g[j - a[i].w], f[j] + a[i].v);
            }
            L = nL;
        }
        swap(f, g);
    }
    return f[0];
}

int main() {
    int Test;
    cin >> Test;
    for (int Case = 1; Case <= Test; Case ++) {
        printf("%lld\n", solve());
    }
    return 0;
}

D. Deliver the Cake

题目描述：

$ n $ 个点 $ m $ 条双向边。有三种状态 $ LRM $ ，每个点拥有一种状态，张三从 $ s $ 到 $ t $ ， $ L $ 状态需要使用左手， $ R $ 使用右手， $ M $ 无限制。左右手转换需要花费 $ x $ 。问最小花费。

数据范围：
$ 1\le T \le 100 $

$ 1\le n \le 10^5, 1\le m \le 2\times10^5, 1\le x \le 10^9 $

$ 1\le w \le 10^9 $

题解：

图上的决策问题，分层图最短路，虚拟结点。

分层图最短路可以使用 $ dp $ 方式，开二维数组，也可以分点，将点分成不同的状态。

将点只看做 $ LR $ 两个状态，开辟两倍的空间。每个点有三种状态，组合一下九种状态，使用循环建边比较方便。最后判断一下起点终点类型，跑一下最短路。也可以建几个虚拟结点让起点的两个状态，终点的两个状态都连过去，直接跑最短路。

代码：

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
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const char TYPE[3] = "LR";

int tcase, n, m, k;
int s, t, x;
char type[maxn];

int head[maxn], cnt;
struct Edge
{
    int v, next;
    ll w;
} edge[maxm << 1];
inline void addEdge(int u, int v, ll w)
{
    ++cnt;
    edge[cnt] = {v, head[u], w};
    head[u] = cnt;
}

bool vis[maxn];
ll dis[maxn];
void dijstra(int s)
{
    priority_queue<pair<ll, int>> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));

    dis[s] = 0;
    q.push({-dis[s], s});
    while (!q.empty())
    {
        auto out = q.top();
        q.pop();
        int u = out.second;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if (dis[u] + edge[i].w < dis[v])
            {
                dis[v] = dis[u] + edge[i].w;
                q.push({-dis[v], v});
            }
        }
    }
}

void init()
{
    memset(head, 0, sizeof(head));
    cnt = 0;
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/D.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    scanf("%d", &tcase);
    while (tcase--)
    {
        scanf("%d%d%d%d%d", &n, &m, &s, &t, &x);
        init();
        scanf("%s", type + 1);
        int u, v;
        ll w;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%lld", &u, &v, &w);
            for (int j = 0; j <= 1; j++)
            {
                for (int k = 0; k <= 1; k++)
                {
                    if ((TYPE[j] == type[u] || type[u] == 'M') && (TYPE[k] == type[v] || type[v] == 'M'))
                    {
                        addEdge(u + j * n, v + k * n, w + x * (j ^ k));
                        addEdge(v + k * n, u + j * n, w + x * (j ^ k));
                    }
                }
            }
        }
        ll ans = INF_LL;
        for (int i = 0; i <= 1; i++)
        {
            for (int j = 0; j <= 1; j++)
            {
                if ((TYPE[i] == type[s] || type[s] == 'M') && (TYPE[j] == type[t] || type[t] == 'M'))
                {
                    dijstra(s + n * i);
                    ans = min(ans, dis[t + n * j]);
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E. Equal Sentences

题目描述：

定义句子相等为：对一个单词来说第 $ i $ 次出现位置相差不超过 $ 1 $

给出一个句子，问有多少种与之相等的（包括自己）

数据范围：
$ 1\le T \le 100 $

$ 1\le n \le 10^5 $

$ 10 $ 个单词是最大

题解：

显然需要进行 $ DP $ 。定义 $ dp[i] $ 表示前 $ i $ 个单词有多少种句子。每一个单词只和它前面的一个相交换

a b c d e

1 2 3 4 5

假设 $ i= 5 $ ，如果 $ 5 $ 和 $ 4 $ 不交换的话 $ dp[5] = dp[4] $ ，如果交换的话 $ dp[5] = dp[3] $ ，故 $ dp[5] = dp[4] + dp[3] $ 。这是能交换的情况，如果 $ 5 == 4 $ 则不能交换 $ dp[5] = dp[4] $ ，斐波那契数列

代码：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e5 + 10;
int t, n, m, k;
string s[maxn];
int dp[maxn];
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", &n);
        for(int i = 1; i <= n; i++)
        {
            cin >> s[i];
            dp[i] = 0;
        }
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            if(s[i] != s[i-1])
            {
                dp[i] = (dp[i-2] + dp[i-1] ) % mod;
            }
            else
            {
                dp[i] = dp[i - 1];
            }
        }
        printf("%d\n", dp[n]);
    }
    return 0;
}

F.

题目描述：

数据范围：

题解：

代码：

1
2


G. Go Running

题目描述：

二维坐标系上有一些点，使用最少的斜率为 $ -1,1 $ 的直线覆盖这些点

数据范围：
$ 1\le T \le 100 $

$ 1\le n \le 10^5,\sum n \le 5\times10^5 $

$ 1\le t_i, x_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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#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 = 1e5 + 10;
const int maxm = 1e6 + 10;
int t, n, m, k;

struct Edge
{
    int v, next;
} edge[maxm << 1];
int head[maxn], cnt;
inline void addEdge(int u, int v)
{
    edge[++cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int dx[maxn], dy[maxn]; //遍历层次 
int mx[maxn], my[maxn]; //匹配结点
int dis;
bool vis[maxn];
int nx, ny;
bool bfs()
{
    queue<int> q;
    memset(dx, -1, sizeof(dx));
    memset(dy, -1, sizeof(dy));

    for(int i = 1; i <= nx; i++)
    {
        if(mx[i] == -1)
        {
            q.push(i);
            dx[i] = 0;
        }
    }
    dis = INF;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        // 该路径长度大于dis，等待下一次BFS扩充
        // dis是到Y集合的长度，所以dis一定是一个奇数
        if(dx[u] > dis)
            break;
        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if(dy[v] != -1)
                continue;
            dy[v] = dx[u] + 1;
            if(my[v] == -1) dis = dy[v];
            else
            {
                dx[my[v]] = dy[v] + 1;
                q.push(my[v]);
            }
        }
    }
    return dis != INF;
}

bool dfs(int u)
{
    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].v;
        if(!vis[v] && dy[v] == dx[u]+1)
        {
            vis[v] = true;
            if(my[v] != -1 && dy[v] == dis)
                continue;
            if(my[v] == -1 || dfs(my[v]))
            {
                my[v] = u;
                mx[u] = v;
                return true;
            }
        }
    }
    return false;
}

int HK()
{
    int ans = 0;
    memset(mx, -1, sizeof(mx));
    memset(my, -1, sizeof(my));
    while (bfs())
    {
        for(int i = 1; i <= ny; i++)
            vis[i] = false;
        for (int i = 1; i <= nx; i++)
        {
            if(mx[i] == -1 && dfs(i))
            {
                ans++;
            }
        }
    }
    return ans;
}

int a[maxn], b[maxn];
int d[maxn << 1], top = 0;
void init()
{
    memset(head, 0, sizeof(head));
    cnt = 0;
    top = 0;
}

int main()
{
#define COMP_DATA
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
    freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/G.in", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    freopen("in.txt", "r", stdin);
#endif
#endif
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &a[i], &b[i]);
            d[++top] = a[i] + b[i];
            d[++top] = a[i] - b[i];
        }

        sort(d + 1, d + 1 + top);
        nx = ny = unique(d + 1, d + 1 + top) - d - 1;
        for(int i = 1; i <= n; i++)
        {
            int u = lower_bound(d + 1, d + 1 + nx, a[i] + b[i]) - d;
            int v = lower_bound(d + 1, d + 1 + nx, a[i] - b[i]) - d;
            addEdge(u, v);
        }

        printf("%d\n", HK());
    }
    return 0;
}

H.

题目描述：

数据范围：

题解：

代码：

1
2


I.

题目描述：

数据范围：

题解：

代码：

1
2


J.

题目描述：

数据范围：

题解：

代码：

1
2


K. Kindergarten Physics

题目描述：

这神仙题，两点只在万有引力作用下相向运动，求时间 $ t $ 的时候相距的距离。

数据范围：
$ 1\le T \le 100 $

$ 1\le a,b,d,t\le 100 $

$ eps \le 10^{-6} $

题解：

我沙雕了，一直在推公式，结果微分方程解不出来，最后看看数据范围和样例才发现之间的力可以忽略不计，真就忽略不计了呗。直接读入输出。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eqs = 1e-5;
int t, n, m, k;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &t);
    while(t--)
    {
        int a, b, l, t;
        scanf("%d%d%d%d", &a, &b, &l, &t);
        printf("%d\n", l);
    }
    return 0;
}