2020HDU多校第二场

多校
字数统计: 1.4k字   |   阅读时长: 7分

Total Eclipse（HDU-6763）（1001）

题意：现在有n个城市和m条双向通道用于连接城市，然后每个城市都有一个亮度b。然后现在有人想把所以城市的亮度全部降为0。他可以有k次操作，每次可以选择1~n之间任意数量的城市进行降1的亮度，问你最少需要多少次操作才可以将所以城市亮度都降为0。

思路：这道题的话，在昨天比赛的时候我和我的队友也想到了用并查集来做，但是却没能实现。然后我看了看大佬们实现的代码，有了一些想法。我们可以先将我们的亮度从大到小排序，然后我们依次加入x点，并且加入和这个点相连的所有点，如果新加入的y点的亮度大于x点，那么我们就把他们合并。在之后我们计算答案的时候，对于x节点，当需要删除他的时候他已经减去了他的父亲节点的亮度了，所以只需要再减去剩下的$d−dfather$的答案。所以最后求一下和就可以了。

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 200010;
const int inf = 0x3f3f3f3f;
using namespace std;
int d[maxx], pre[maxx], fa[maxx], vis[maxx], num[maxx];
vector<int> g[maxx];
bool cmp(int a, int b)
{
    return d[a] > d[b];
}
int getf(int a)
{
    if (pre[a] == a)
        return pre[a];
    return pre[a] = getf(pre[a]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, m;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            g[i].clear();
        for (int i = 1; i <= n; i++)
        {
            cin >> d[i];
            pre[i] = i;
            vis[i] = fa[i] = 0;
            num[i] = i;
        }
        sort(num + 1, num + 1 + n, cmp);
        for (int i = 1; i <= m; i++)
        {
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        for (int i = 1; i <= n; i++)
        {
            int x = num[i];
            vis[x] = 1;
            for (auto it : g[x])
            {
                if (!vis[it])
                    continue;
                int fy = getf(it);
                if (fy == x)
                    continue;
                fa[fy] = pre[fy] = x;
            }
        }
        ll res = 0;
        for (int i = 1; i <= n; i++)
            res += d[i] - d[fa[i]];
        cout << res << endl;
    }
    return 0;
}

Lead of Wisdom(HDU-6772) (1010)

题意：给你k种类型的物品若干种，一个种类只能选一种物品，求题中DMG的最大值。

思路：这道题的话，直接暴搜竟然可以，参考了些大佬的思路，感觉自己也明白了。暴搜的话正着dfs会wa，反着dfs即可。

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 1010;
const int inf = 0x3f3f3f3f;
using namespace std;
int f[maxx][maxx][5], ans[maxx];
ll res;
int n, m;
void dfs(int x, int a, int b, int c, int d)
{
    if (x < 1)
    {
        ll tmp = 1ll * a * b * c * d;
        res = max(res, tmp);
        return;
    }
    if (!ans[x])
    {
        dfs(x - 1, a, b, c, d);
        return;
    }
    for (int i = 1; i <= ans[x]; i++)
        dfs(x - 1, f[x][i][1] + a, f[x][i][2] + b, f[x][i][3] + c, f[x][i][4] + d);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        res = 0;
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
            ans[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            int cnt;
            cin >> cnt;
            ans[cnt]++;
            for (int j = 1; j <= 4; j++)
                cin >> f[cnt][ans[cnt]][j];
        }
        dfs(1, 100, 100, 100, 100);
        cout << res << endl;
    }
    return 0;
}

The Oculus(HDU-6768) (1006)

题意：给你两个数，每个都是用斐波那契数列（01表示）来表示的，规定$F1=1,F2=2$，再给你他们相乘后的结果C用斐波那契数列来表示，现在我将C中的斐波那契数列的某一位1删掉，问你删掉的是哪一位。

思路：这道题的话，双哈希过去。因为我们只是把一个1翻成了0，所以枚举C数组遇见0就把他翻转过来看是不是hash值相等，如果相等则答案就是这一位。

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 2000010;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 9;
const int mod1 = 1e9 + 7;
using namespace std;
ll f[maxn], f1[maxn];
ll na, nb, nc, sa, sb, sc, sa1, sb1, sc1;
ll a[maxn], b[maxn], c[maxn];
void solve()
{
    scanf("%lld", &na);
    for (int i = 1; i <= na; i++)
        scanf("%lld", &a[i]);
    scanf("%lld", &nb);
    for (int i = 1; i <= nb; i++)
        scanf("%lld", &b[i]);
    scanf("%lld", &nc);
    for (int i = 1; i <= nc; i++)
        scanf("%lld", &c[i]);
    sa = sb = sc = 0;
    sa1 = sb1 = sc1 = 0;
    for (int i = 1; i <= na; i++)
        sa = (sa + f[i] * a[i]) % mod;
    for (int i = 1; i <= nb; i++)
        sb = (sb + f[i] * b[i]) % mod;
    for (int i = 1; i <= nc; i++)
        sc = (sc + f[i] * c[i]) % mod;
    for (int i = 1; i <= na; i++)
        sa1 = (sa1 + f1[i] * a[i]) % mod1;
    for (int i = 1; i <= nb; i++)
        sb1 = (sb1 + f1[i] * b[i]) % mod1;
    for (int i = 1; i <= nc; i++)
        sc1 = (sc1 + f1[i] * c[i]) % mod1;
    for (int i = 1; i <= nc; i++)
        if (c[i] == 0)
        {
            int tmp = (sc + f[i]) % mod, tmp1 = (sc1 + f1[i]) % mod1;
            if (tmp == (sa * sb) % mod && tmp1 == (sa1 * sb1) % mod1)
            {
                printf("%lld\n", i);
                break;
            }
        }
}
int main()
{
    f[1] = 1, f[2] = 2;
    for (int i = 3; i < maxn; i++)
        f[i] = (f[i - 1] + f[i - 2]) % mod;
    f1[1] = 1, f1[2] = 2;
    for (int i = 3; i < maxn; i++)
        f1[i] = (f1[i - 1] + f1[i - 2]) % mod1;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

赏

×

纯属好玩

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

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

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

文章作者:Stephencurry6666

发布时间:2020年07月27日 - 17时12分

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

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

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

文章目录
  1. 1. Total Eclipse（HDU-6763）（1001）
  2. 2. Lead of Wisdom(HDU-6772) (1010)
  3. 3. The Oculus(HDU-6768) (1006)
,
字数统计：87.6k 载入天数...载入时分秒...