2020HDU多校第三场

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

Tokitsukaze and Multiple （HDU-6794） (1004)

题意：有一个长度为n的序列，你现在将序列中连续两个元素合并多次，然后问你在经过一些操作之后，能得到的p的倍数元素的最大可能数量。

思路：这道题的话，我们用map函数来做。

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
using namespace std;
map<ll,ll>mapp;
ll a[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, p;
    cin >> t;
    while (t--)
    {
        cin >> n >> p;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            a[i] %= p;
        }
        int ans = 0, sum = 0;
        mapp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            sum += a[i];
            sum %= p;
            if (mapp[sum] != 0)
            {
                ans++;
                mapp.clear();
                mapp[0] = 1;
                sum = 0;
            }
            else
                mapp[sum] = 1;
        }
        cout << ans << endl;
    }
    return 0;
}

Little W and Contest （HDU-6795） （1005）

题意：现在有n个人，然后每三个人可以组成一队，但是三个之间不能互相认识。比如A认识B，B认识C，那么A就可以通过B认识C。问你随着联系的增加，每次能组成几个队伍。

这道题的话，我们用并查集来做，将相互认识的人放在同一个并查集中，同一个并查集中的人不能够成为队友。保存总的1能力值人数为num[0]，总的2能力值人数为num[1]。每个并查集中pre[i][0]表示祖先为i点的并查集中的1能力值人数，pre[i][1]表示2能力值人数，队伍组成的情况有两种： 1 2 2 和 2 2 2。注意去重，取余的位置和防止爆int，不要对分子先进行取模，防止造成分子除分母无法刚好除尽的情况，然后对于每次交友之后，形成不同集合之后，对于结果都是有影响的，要去除原本u和v所在的集合与这两个集合之外人组成team的数量，同时也要注意u1*v2等等时可能爆int，要加ll。

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
using namespace std;
int a[maxx];
int pre[maxx];
int f[maxx][2];
int num[2];
int getf(int a)
{
    if (a == pre[a])
        return a;
    return pre[a] = getf(pre[a]);
}
int mer(int a, int b)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa == fb)
        return fa;
    pre[fb] = fa;
    f[fa][0] += f[fb][0];
    f[fa][1] += f[fb][1];
    return fa;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        memset(f, 0, sizeof(f));
        num[0] = num[1] = 0;
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            pre[i] = i;
            cin >> a[i];
            if (a[i] == 1)
            {
                num[0]++;
                f[i][0] = 1;
            }
            if (a[i] == 2)
            {
                num[1]++;
                f[i][1] = 1;
            }
        }
        ll ans = 1ll * num[1] * (num[1] - 1) / 2 % mod * num[0] % mod + 1ll * num[1] * (num[1] - 1) * (num[1] - 2) / 6 % mod;
        cout << ans % mod << endl;
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            if (i >= n - 2)
            {
                cout << "0" << endl;
                continue;
            }
            int fa = getf(u);
            int fb = getf(v);
            int u1 = f[fa][0], u2 = f[fa][1];
            int v1 = f[fb][0], v2 = f[fb][1];
            int cnt = mer(u, v);
            int x = f[cnt][0];
            int y = f[cnt][1];
            ans -= 1ll * u1 * v2 % mod * (num[1] - y) % mod;
            if (ans < 0)
                ans += mod;
            ans -= 1ll * u2 * v1 % mod * (num[1] - y) % mod;
            if (ans < 0)
                ans += mod;
            ans -= 1ll * u2 * v2 % mod * (n - x - y) % mod;
            if (ans < 0)
                ans += mod;
            cout << ans % mod << endl;
        }
    }
    return 0;
}

Tokitsukaze and Rescue (HDU-6797) (1007)

题意：给出一张无向完全图，现在要求删除k条边，问删除后的最短路的最大值是多少，k最大是5。

思路：这道题的话，我们可以发现题目中说了所有的边权均是随机数，然后实现就好了，然后用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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 110;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
using namespace std;
int g[maxx][maxx], pre[6][maxx], dis[maxx];
bool vis[maxx];
int n, ans;
void Dijkstra(int m)
{
    memset(dis, inf, sizeof(int) * (n + 5));
    memset(vis, false, n + 5);
    dis[1] = 0;
    for (int i = 1; i < n; i++)
    {
        int minn = inf;
        int u = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] < minn)
            {
                minn = dis[j];
                u = j;
            }
        }
        vis[u] = true;
        for (int v = 1; v <= n; v++)
        {
            if (dis[v] > dis[u] + g[u][v])
            {
                dis[v] = dis[u] + g[u][v];
                pre[m][v] = u;
            }
        }
    }
}
void dfs(int m)
{
    Dijkstra(m);
    if (!m)
    {
        ans = max(ans, dis[n]);
        return;
    }
    int pos = n;
    while (pos != 1)
    {
        int u = pos, v = pre[m][pos];
        int temp = g[u][v];
        g[u][v] = g[v][u] = inf;
        dfs(m - 1);
        g[u][v] = g[v][u] = temp;
        pos = pre[m][pos];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int m;
        cin >> n >> m;
        for (int i = 1; i <= n * (n - 1) / 2; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            g[u][v] = g[v][u] = w;
        }
        ans = 0;
        dfs(m);
        cout << ans << endl;
    }
    return 0;
}

Parentheses Matching （HDU-6799）（1009）

题意：给你一个含有’(‘，’)’，‘‘的字符串，允许把’*’变为’(‘或’)’或’ ‘，求最小的括号匹配合法序列。

思路：这道题的话，想要最小的序列，那就需要尽量减少‘’的使用，所以我们需要在原序列中就尽可能的匹配括号。然后可以发现右括号都集中在左边，左括号都集中在右边，于是要构造最小的序列的话就对于右括号来说，尽可能的选靠左的‘’变左括号，而对于左括号来说，尽可能的选靠右的‘*’变右括号即可。

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx=100010;
using namespace std;
typedef pair<char,int>pii;
stack<pii>q;
char s[maxx];
char t[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> s + 1;
        int n = strlen(s + 1);
        for (int i = 1; i <= n; i++)
        {
            t[i] = s[i];
            if (s[i] == '(')
                q.push(pii(s[i], i));
            if (s[i] == ')')
            {
                if (!q.empty())
                {
                    t[q.top().second] = t[i] = 0;
                    q.pop();
                }
            }
        }
        while (!q.empty())
        {
            q.pop();
        }
        bool flag = 1;
        int l = n + 1, ls = 0, rs = 0;
        for (int i = 1; i <= n; i++)
        {
            if (t[i] == '*')
                ls++;
            if (t[i] == ')')
            {
                if (!ls)
                {
                    flag = 0;
                    break;
                }
                ls--;
                rs++;
            }
            if (t[i] == '(')
            {
                l = i;
                break;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            if (t[i] == '*' && rs)
            {
                rs--;
                s[i] = '(';
            }
        }
        ls = 0;
        rs = 0;
        for (int i = n; i >= l; i--)
        {
            if (t[i] == '*')
                rs++;
            if (t[i] == '(')
            {
                if (!rs)
                {
                    flag = 0;
                    break;
                }
                rs--;
                ls++;
            }
        }
        for (int i = n; i >= l; i--)
        {
            if (t[i] == '*' && ls)
            {
                ls--;
                s[i] = ')';
            }
        }
        if (!flag)
            cout << "No solution!" << endl;
        else
        {
            for (int i = 1; i <= n; i++)
            {
                if (s[i] == '(' || s[i] == ')')
                {
                    cout << s[i];
                }
            }
            cout << endl;
        }
    }
    return 0;
}

赏

×

纯属好玩

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

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

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

文章作者:Stephencurry6666

发布时间:2020年07月30日 - 10时16分

最后更新:2020年07月30日 - 10时29分

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

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

文章目录
  1. 1. Tokitsukaze and Multiple （HDU-6794） (1004)
  2. 2. Little W and Contest （HDU-6795） （1005）
  3. 3. Tokitsukaze and Rescue (HDU-6797) (1007)
  4. 4. Parentheses Matching （HDU-6799）（1009）
,
字数统计：87.6k 载入天数...载入时分秒...