2020HDU多校第四场

多校
字数统计: 1.9k字   |   阅读时长: 9分

Kindergarten Physics （HDU-6812） (1011)

题意：给你两个质点a和b，然后给出a和b的质量和它们之间的距离h，问你经过万有引力的作用之后，在经过t0时间之后，它们之间的距离。

思路：这道题的话，我们需要套用物理公式。$F(万有引力)=(Gxmaxmb)/rxr$,$F=ma$,$S=(1/2)xaxtxt$。

AC代码：

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
const int G = 6.67430 * (1e-11);
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        double a, b, d, t0;
        cin >> a >> b >> d >> t0;
        double a1 = G * b / (d * d);
        double a2 = G * a / (d * d);
        double s1 = (1 / 2) * a1 * t0 * t0;
        double s2 = (1 / 2) * a2 * t0 * t0;
        d = d - s1 - s2;
        printf("%.6lf\n", d);
    }
    return 0;
}

Blow up the Enemy （HDU-6803） (1002)

题意：给定有n种武器，每种武器有2种属性：伤害A和冷却时间D，张三和爸爸各从n种武器种选择一个武器进行对战。张三和爸爸各从n种武器种选择一个武器进行对战。每人初始HP=100，每种武器每次攻击可以使得对手HP值减去Ai，HP≤0的一方出局。初始时武器未冷却，每攻击一次，武器冷却Di时长，Di时间后，可立刻攻击。爸爸每次从n种武器种等概率地随机选择一种武器，若二人的HP同时小于等于0，那么二人各有0.5的概率获胜。请帮助张三选择武器，使得他能够以最大的概率获胜。

思路：这道题的话，我们可以先算出每种武器打掉100血的时间，然后选择最小的，然后再分别与每种武器进行比较，计算概率即可。

AC代码：

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 10010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
const int G = 6.67430 * (1e-11);
using namespace std;
struct node
{
    int a;
    int d;
    double tim;
} edge[maxx];
bool cmp(node x, node y)
{
    return x.tim < y.tim;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> edge[i].a >> edge[i].d;
            if (100 % edge[i].a == 0)
                edge[i].tim = (100 / edge[i].a - 1) * edge[i].d;
            else
                edge[i].tim = (100 / edge[i].a) * edge[i].d;
        }
        sort(edge, edge + n, cmp);
        double minn = edge[0].tim;
        double ans = 1;
        for (int i = 1; i < n; i++)
        {
            if (edge[i].tim == minn)
                ans++;
            else
                break;
        }
        double cnt = 1 - (ans / n) * 0.5;
        printf("%.6lf\n", cnt);
    }
    return 0;
}

Equal Sentences （HDU-6806） (1005)

题意：给你一串字符串S，现在有两个要求：1. S中的单词的多集与T中的单词的多集相同。2. 对于一个单词概要，它在S中的第i次出现和在T中的第i次出现的索引差异不超过1。(句子中的第k个单词的索引是k。)只要单词在两个句子中出现至少i次，这对所有的a和i都成立。然后我们可以说S和T几乎相同。但是请注意，“几乎相等”不是一个等价关系，不像它的名字。也就是说，如果句子A和B接近相等，B和C接近相等，那么A和C可能不接近相等。然后问你有多少个句子与S几乎相同。

思路：这道题的话，在读完题之后和jp在讨论之后，发现就是如果前后单词是一样的话，那么就算一个句子。所以我想到了上楼梯，和这个有异曲同工之妙。于是我就列了dp方程，那就是n=1的时候，只有1种；n=2的时候分两种情况，相等或者不相等；n>=3的时候，也是分相等和不相等两种情况。当n>=3的时候，要是当前和上一个相等，那就直接$dp[i]=dp[i-1]$；要是不相等，那就是等于前两个相加$dp[i]=dp[i-1]+dp[i-2]$。

AC代码：

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 200010;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int G = 6.67430 * (1e-11);
using namespace std;
int dp[maxx];
string s[maxx];
int solve(int n)
{
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    dp[1] = 1;
    if (s[1] != s[2])
        dp[2] = 2;
    else
        dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        if (s[i] != s[i - 1])
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
        else
            dp[i] = dp[i - 1] % mod;
    }
    return dp[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        memset(dp, 0, sizeof(dp));
        int ans = solve(n);
        cout << ans << endl;
    }
    return 0;
}

Deliver the Cake （HDU-6805）（1004）

题意：给出一个nm的无向图，有边权。张三在起点s，目标是t。点分成左点右点和中间点，到左点的时候必须用左手，到右点的时候必须用右手，中间点没有特殊要求。张三每次切换左右手都要花费额外的时间，询问起点到终点的最短路。

思路：这道题的话，我们把每个点拆成两个点，L点拆成两个L，R点拆成两个R，M点拆成一个L一个R。然后跑Dijkstra+优先队列即可。

AC代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;
const ll inf = 1e18;
int n, m, s, t, cost;
string ss;
struct node
{
    int u;
    int v;
    int w;
    int next;
} edge[maxn * 8];
int head[maxn * 3];
int tol = 0;
void addedge(int u, int v, int w)
{
    edge[tol].u = u;
    edge[tol].v = v;
    edge[tol].w = w;
    edge[tol].next = head[u];
    head[u] = tol++;

    edge[tol].u = v;
    edge[tol].v = u;
    edge[tol].w = w;
    edge[tol].next = head[v];
    head[v] = tol++;
}
ll d[maxn];
int visit[maxn];
char wjm[maxn];
struct qnode
{
    int v;
    ll w;
    bool operator<(const qnode &r) const
    {
        return w > r.w;
    }
};
void dij(int s)
{
    memset(visit, 0, sizeof(visit));
    for (int i = 1; i <= 2 * n; i++)
        d[i] = inf;
    priority_queue<qnode> q;
    d[s] = 0;
    q.push({s, 0});
    qnode tmp;
    while (!q.empty())
    {
        tmp = q.top();
        q.pop();
        int u = tmp.v;
        if (visit[u])
            continue;
        visit[u] = 1;
        for (int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            int tt;
            if (wjm[u] == wjm[v])
                tt = 0;
            else
                tt = 1;
            if (!visit[v] && d[v] > d[u] + edge[i].w + tt * cost)
            {
                d[v] = d[u] + edge[i].w + tt * cost;
                q.push({v, d[v]});
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d%d%d", &n, &m, &s, &t, &cost);
        for (int i = 1; i <= n * 2; i++)
            head[i] = -1;
        cin >> ss;
        for (int i = 1; i <= n; i++)
        {
            if (ss[i - 1] == 'L')
            {
                wjm[i] = 'L';
                wjm[i + n] = 'L';
            }
            else if (ss[i - 1] == 'R')
            {
                wjm[i] = 'R';
                wjm[i + n] = 'R';
            }
            else
            {
                wjm[i] = 'L';
                wjm[i + n] = 'R';
            }
        }
        tol = 0;
        for (int i = 0; i < m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(u + n, v, w);
            addedge(u + n, v + n, w);
            addedge(u, v + n, w);
        }
        ll ans = 1e18;
        dij(s);
        ans = min(ans, d[t]);
        ans = min(ans, d[t + n]);
        dij(s + n);
        ans = min(ans, d[t]);
        ans = min(ans, d[t + n]);
        printf("%lld\n", ans);
    }
    return 0;
}

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:2020HDU多校第四场

文章作者:Stephencurry6666

发布时间:2020年07月31日 - 17时03分

最后更新:2020年07月31日 - 17时17分

原始链接:https://stephencurry6666.github.io/2020/07/31/2020HDU%E5%A4%9A%E6%A0%A1%E7%AC%AC%E5%9B%9B%E5%9C%BA/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. Kindergarten Physics （HDU-6812） (1011)
  2. 2. Blow up the Enemy （HDU-6803） (1002)
  3. 3. Equal Sentences （HDU-6806） (1005)
  4. 4. Deliver the Cake （HDU-6805）（1004）
,
字数统计：87.6k 载入天数...载入时分秒...