SDNU 训练赛总结

发表于 更新于 分类于 阅读次数：

SDNU 训练赛总结

ACM训练

A题

思路

就是简单的排个序，输出第K大小的数字，同时将前K大的数字的标号输出来。因为文件WA的自闭，QWQ。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
using namespace std;

struct node{
   int index;
   int v;
}a[1010];
int cmp(node a,node b)
{
    return a.v > b.v;
}
int main()
{
    int n,k;
    freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
    scanf("%d %d",&n,&k);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i].v);
        a[i].index = i;
    }
    sort(a + 1, a + n + 1,cmp);

    printf("%d\n",a[k].v);
    for(int i = 1; i <= k; ++i)
    {
        printf("%d%c",a[i].index,i == k ?'\n':' ');
    }
}

B题

题意

有N个人，他们分别有weight，beautiful, 现在让你挑选多个人，使得不超过总权重M的情况下，总的beautiful值最大。但是一些人可能是朋友，对于一个朋友组，要么选择不超过一个人，要么选择所有人。

思路

我们先用并查集把属于一个朋友群的人放到一个集合里。然后一个集合一个集合的枚举。对于每个集合，也是分别枚举一个人的情况和所有人的情况。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map>
int f[1010], dp[2010], w[2001],b[2001];
using namespace std;
int find(int x)
{
    if(x != f[x])
        f[x] = find(f[x]);
    return f[x];
}

void combine(int x,int y)
{
    int fa = find(x);
    int fb = find(y);
    if(fa != fb)
        f[fa] = fb;
}
int main()
{
    int n, m ,W, aa, bb, num;
    vector<int>V[2001];
    cin >> n >> m >> W;
    for(int i = 1; i <= n; ++i)
        f[i] = i;
    for(int i = 1; i <= n; ++i)
        cin >> w[i];
    for(int i = 1; i <= n; ++i)
        cin >> b[i];
    while(m--)
    {
        cin >> aa >> bb;
        combine(aa,bb);
    }
    for(int i = 1; i <= n; ++i)
        V[find(i)].push_back(i);
    for(int i = 1; i <= n; ++i)
    {
        if(i == find(i)){
        for(int j = W; j >= 0 ; --j)
        {
            int sum1 = 0;
            int sum2 = 0;
            for(int k = 0; k < V[i].size(); ++k)
            {
                num = V[i][k];
                sum1 += w[num];
                sum2 += b[num];
                if(j >= w[num])
                {
                    dp[j] = max(dp[j], dp[j - w[num]] + b[num]);
                }
            }
            if(j >= sum1)
                dp[j] = max(dp[j], dp[j - sum1] + sum2);
        }
        }
    }
    cout << dp[W] << '\n';

}

C题

题意

给你一些钱币的组合总数，让你输出应该怎么组合。我们应该用1和2来进行组合即可。比如说输入314，那么如果钱币只有1和2的话，所达到的金额数应该是2 * n - 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map>

using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << 2 * n - 1 << ' ' << 2 << '\n';
    cout << 1 << ' ' << 2 << '\n';
}

D题

思路

对于一个N * N的矩阵，他有N / 2+1 个奇数，我们只需要合理的安排其中的位置，剩下的填上偶数就行了。每行每列以及对角线上的奇数的个数都应该是奇数个，因此最后我们构造的矩阵中间的菱形，也是正方形都是奇数，剩下的都是偶数。

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map>

using namespace std;

int main()
{
    int a[50][50], n;
    cin >> n;
    int cnt = 1;
    int tot = 2;
    int cx = n / 2 + 1;
    int cy = cx;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(abs(cx - i) + abs(cy - j) < n / 2 + 1)
                {
                    a[i][j] = cnt;
                    cnt += 2;
                }
            else
            {
                a[i][j] = tot;
                tot += 2;
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            printf("%d%c",a[i][j],j == n ? '\n':' ');
        }
    }
}

E题

思路

题意中是一种递归的算法。但是我们可以直接模拟贪心思路。把所有的数字放到一个数组里，然后从大到小排序。我们分别取前1个数字的最大数(相当于总矩阵的最大值)，然后取前四个数字的最大值（相当于4个子矩阵的每个矩阵的最大值），然后是前16个….. 这样我们就不需要在构造出矩阵才能求最大值了。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map>

using namespace std;
bool cmp(int a, int b)
{
    return a > b;
}
int a[20000010];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        scanf("%d",&a[i]);
    sort(a + 1,a + n + 1,cmp);
    int k = 1;
    long long sum;
    while(k <= n)
    {
        for(int i = 1; i <= k; ++i)
        {
            sum += a[i];
        }
        k *= 4;
    }
    cout << sum << '\n';

}

F题

题意

给你三种topo图，然后数据之后，问你属于哪种topo.

思路

只要记录每个节点的度即可。

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
#include <bits/stdc++.h>
using namespace std;
int vis[100001];
int main()
{
    int n, m, a, b;
    memset(vis, 0 ,sizeof(vis));
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        vis[a]++;
        vis[b]++;
    }
    int cnt = 0 , cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(vis[i] == 1)
            cnt++;
        if(vis[i] == 2)
            cnt1++;
        if(vis[i] == n - 1)
            cnt2++;
    }
    if(cnt == 2 && cnt1 == n - 2)
        cout << "bus topology" << '\n';
    else if(cnt1 == n)
        cout << "ring topology" << '\n';
    else if(cnt == n - 1 && cnt2 == 1)
        cout <<  "star topology" << '\n';
    else
        cout << "unknown topology" << '\n';
}

G题

思路

我们可以把总的花费时间求出来，然后看看这个总时间是否在一段区间内，在的话，最终的答案就是这个总时间。否则，答案是距离这个总时间最近的那个时间。在第11个样例错的，是没有考虑在还没有工作时间之前就已经完成任务的情况。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map>

using namespace std;
struct node{
   int l,r;
}b[2001];
int a[1010], c[2001];
bool cmp(node a, node b)
{
    if(a.l != b.l)
        return a.l < b.l;
    else return a.r < b.r;
}
int main()
{
    int n, m;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
        sum += a[i];
    }
    cin >> m ;
    int max1 = -1;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d",&b[i].l,&b[i].r);
        if(max1 < b[i].r)
            max1 = b[i].r;
        c[i - 1] = b[i].l;
    }
    if(sum > max1)
    {
        cout << "-1" << '\n';
    }
    else if(sum < b[1].l)            //wrong 11 test
    {
        cout << b[1].l << '\n';
    }
    else{
        sort(b + 1, b + m + 1, cmp);
        int flag = 0;
        for(int i = 1; i <= m; ++i)
        {
            if(b[i].l <= sum && b[i].r >= sum)
            {
                flag = 1;
                cout << sum << '\n';
                break;
            }
        }
        if(!flag)
        {
           int d = lower_bound(c , c + m , sum) - c ;
           cout << c[d] << '\n';
        }
    }
}

H题

思路

本来想N*N的复杂度，发现不行，后来看这个是有序的，那就二分。用lower_bound函数比较简单一些。

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

using namespace std;
struct node{
   int c,t;
}a[100010];
int sum[100010];
int main()
{
    int n,m,k;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d %d",&a[i].c,&a[i].t);     //c代表次数,t代表一首歌的时间
    }
    sum[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        sum[i] = sum[i - 1] + a[i].c * a[i].t;
    }
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d",&k);
        int m = lower_bound(sum + 1, sum + n + 1,k) - (sum + 1);
        if(sum[m] == k)
             cout << m << '\n';
        else
             cout << m + 1 << '\n';
    }

}