2019 SDNU Contest 18 赛后总结

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

比赛链接

5月3日比赛总结：前期发育良好，后期猥琐发育。这是2019年刚刚过去的浙江省ACM省赛题目 。后期看群里，7题铜9题银？只有两支师哥队伍是铜牌? 太真实了。看榜单浙江省的前几名好多都是中学生，惭愧啊。

E题

每次可以把一个数字移动到最前面去，问你最少移动多少次能够使得该序列为非递减序列。离比赛完毕还有3个小时零13分钟，我们一直在看这个题，emmm,只是单纯的看，没别的，连想都不想，是真的想不出来QAQ，我们智商不够啊。看了题解才知道什么思路： 我们每次往前移动，自然是移动小的数字，那我们从最后一个数字开始往前看有多少个已经排好的数字，那么用总的个数-已经排好的数字个数就是最终的答案了。举个例子： 1 3 5 4 6 7 2 8 我们从后面看，8 7 6 5是已经按顺序排好的，剩下1 3 4 2 未排好，那么最终的答案就是 8 - 4 = 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
#include <bits/stdc++.h>
using namespace std;
int a[100001];
int main()
{
    int t, n;
    scanf("%d",&t);
    while(t--)
    {
        priority_queue<int>Q;
        scanf("%d",&n);
        for(int i = 1; i <= n ;++i)
        {
            scanf("%d",&a[i]);
            Q.push(a[i]);
        }
        int ans = n;
        for(int i = n ; i >= 1; --i)
        {
            if(a[i] == Q.top())
            {
                ans--;
                Q.pop();
            }
        }
        printf("%d\n",ans);
    }
}

F题

将已给的字符串删掉其中的几个字母，签到题。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
       string s,s1;
       cin >> s;
       s1 += s[0];
       for(int i = 1; i < s.size(); ++i)
       {
           if(s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'y' && s[i] != 'o' && s[i] != 'u')
           {
               s1 += s[i];
           }
       }
       cout << s1 << endl;
   }
}

G题

找大于等于该数字的能被7整除但不能被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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i = n; ; ++i)
        {
            if(i % 7 == 0 && i % 4 !=0)
            {
                printf("%d\n",i);
                break;
            }
        }
    }
}

H题

通俗点说，如果一个数既大于他左边的数字，也大于他右边的数字那么这个数是个不好的数字。

现在让你最多删除一个数字（不删也行，可以删除任意一个数字），问最后剩下的不好的数字的个数最少是多少。队友翻译完后，想了一会，觉得删除一个数字只对他左右两边的数字产生影响，因此可以进行O（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
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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <math.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int a[100001];
int main()
{
    int t;
    int n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i)
        {
          scanf("%d",&a[i]);
        }
        if(n <= 3)
        {
            printf("0\n");
        }
        else{
        int cnt = 0;
        for(int i = 2; i <= n -1 ;++i)
        {
            if(a[i] > a[i - 1] && a[i] > a[i + 1])
            {
                cnt++;
            }
        }
        int maxer = 0;

        for(int i = 1; i <= n; ++i)
        {
            int cnt2 = 0;
            if(i == 1)
            {
                if(a[2] > a[1] && a[2] > a[3])
                {
                    cnt2++;
                }
                if(cnt2 == 1)
                {
                    maxer = -1;
                }
                continue;
            }
            if(i == n)
            {
                if(a[n - 1] > a[n] && a[n - 1] > a[n - 2])
                {
                    cnt2++;
                }
                if(cnt2 == 1)
                {
                    maxer = -1;
                }
                continue;
            }
            if(i == 2)
            {
               if(a[3] > a[1] && a[3] > a[4])
               {
                   cnt2++;
               }
               if(a[3] > a[2] && a[3] > a[4])
               {
                   cnt2--;
               }
               if(a[2] > a[1] && a[2] > a[3])
               {
                   cnt2--;
               }
               maxer = min(maxer,cnt2);
               continue;
            }
            if(i == n - 1)
            {
                if(a[i - 1] > a[i - 2] && a[i - 1 ] > a[i + 1])
                {
                    cnt2++;
                }
                if(a[i - 1] > a[i - 2] && a[i - 1] > a[i])
                {
                    cnt2--;
                }
                if(a[i] > a[i - 1] && a[i] > a[i + 1])
                {
                    cnt2--;
                }
                maxer = min(maxer,cnt2);
                continue;
            }
            if(a[i] > a[i - 1] && a[i] > a[i + 1])
            {
                cnt2--;
            }
            if(a[i - 1] > a[i - 2] && a[i - 1] > a[i + 1])
            {
                cnt2++;
            }
            if(a[i - 1] > a[i] && a[i - 1] > a[i - 2])
            {
                cnt2--;
            }
            if(a[i + 1] > a[i - 1] && a[i + 1] > a[i + 2])
            {
                cnt2++;
            }
            if(a[i + 1] > a[i] && a[i + 1] > a[i + 2])
            {
                cnt2--;
            }
            maxer = min(maxer, cnt2);
        }
        printf("%d\n",cnt + maxer);
        }
    }
}

I题

给你一个斐波那契数列，然后问你第a 到第b项的斐波那契数字之和是奇数还是偶数。开场我就看到这个题目，发现每三个数就是循环，但是我的思路需要a先减掉1,a可以是个非常大的数字，C++进行大数-1应该是很麻烦，所以直接用JAVA写，最后直接写了9个if AC, 赛后发现9种if可以合并。

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
import java.io.*;
import java.io.BufferedInputStream;
import java.math.*;
import java.util.*;
import java.text.*;
public class Main
{
	public static void main( String[] args) {
		Scanner cin = new Scanner(System.in);
		BigInteger a,b;
		int t;
		t = cin.nextInt();
		while(t-- > 0) {
		a = cin.nextBigInteger();
		a= a.add(BigInteger.valueOf(-1));
		b = cin.nextBigInteger();
		BigInteger flag , flag1, c;
		flag = a.mod(BigInteger.valueOf(3));
		flag1 = b.mod(BigInteger.valueOf(3));
		c = flag.subtract(flag1);
		if(c.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(0)) == 0)
		{
			System.out.println(0);
		}
		else {
			System.out.println(1);
		}
	}
	}
}

J题

赛后好多人都补了这个题，发现考察的是优先队列和并查集，题目确实不错。说的是有n个人，m对关系，都是朋友关系，现在一个人一个人进场，如果这个人发现场内没有他的朋友，他就会不高兴，现在让你最小化不高兴的人数，同时输出最小字典序的进场顺序。注意A和B是朋友，B和C是朋友，但是A和C不一定是朋友。

开始我想的是谁的朋友多先输出谁，后来想出了这个思路不对。比如说 1和2是朋友，2和3是朋友，3和4是朋友，4和5是朋友，5还和2 3 4 是朋友，5的朋友最多，但是你不能先输出5，应该输出1 2 3 4 5这才是最小字典序。也就是说我们不应该找朋友最多的人，而是把这些关系利用并查集合并成一个一个的联通块，只有根节点是不高兴的人，后面的人都是和这个并查集里的人有关系的。最终f[i] = i的个数就是不高兴的人的个数。我们先把这些不高兴的人放进优先队列里，然后在逐渐的找和这些人是朋友的那些人，在把他们放进队列里，这样不断重复，知道队列为空。我们做的就是从一开始就是字典序，然后后面每一步都是最小字典序了。为了保证一开始是最小字典序，我们在进行并查集的合并的时候，要尽量的把序号小的人放在根节点。

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
#include <bits/stdc++.h>
using namespace std;
vector<int>V[1000001];
int vis[1000001],f[1000001],b[1000001];
int Find(int x)
{
    if(x != f[x])
    {
        f[x] = Find(f[x]);
    }
    return f[x];
}
int combine(int a,int b)
{
    int fa = Find(a);
    int fb = Find(b);
    if(fa < fb)
        f[fb] = fa;
    if(fa > fb)
        f[fa] = fb;
}
int main()
{
    int t,n,m,aa,bb;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        for(int i = 1; i <= n; ++i)
        {
            f[i] = i;
            vis[i] = 0;
            V[i].clear();
        }
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d",&aa,&bb);
            combine(aa ,bb);
            V[aa].push_back(bb);
            V[bb].push_back(aa);
        }
        int ans = 0;
        priority_queue<int,vector<int>,greater<int> >P;
        for(int i = 1; i <= n; ++i)
        {
            if(f[i] == i)
            {
                ans++;
                P.push(i);
                vis[i] = 1;
            }
        }
        int tot = 0;
        int cnt = 0;
        while(!P.empty())
        {
            int num = P.top();
            P.pop();
            b[++tot] = num;
            for(int i = 0; i < V[num].size(); ++i)
            {
                int t = V[num][i];
                if(!vis[t])
                {
                    vis[t] = 1;
                    P.push(t);
                }
            }
        }
        cout << ans << endl;
        for(int i = 1; i <= tot; ++i)
        {
            if(cnt == 0)
            {
                cout << b[i];
                cnt++;
            }
            else{
                cout << ' ' << b[i];
            }
        }
        cout << '\n';
    }
}