山东省第六届ACM比赛 总结

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

山东省第六届ACM省赛题目

题目链接

总结：这都是什么神仙题目，虽然说有简单的，但是感觉好几道题涉及到的知识点我以前没怎么重视过。看到师哥队昨晚这场比赛A了9道，本以为题目难度还行，看来是我高估自己了（师哥太强了）。好在是过的题目都是一遍过，罚时还是不错的。

A题

给你一些人的身高和体重，先把身高从小到大排个序，然后奇数号是一个队，偶数号是一个队，然后我们需要看哪个队伍的体重大一些，体重大的就赢得最后的比赛。考察结构体排序。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
struct node{
   double h,w;
}a[201];
bool cmp(node a ,node b)
{
    return a.h < b.h;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lf %lf",&a[i].h,&a[i].w);
        }
        sort(a + 1,a + n + 1,cmp);
        double sum = 0;
        double sum1 = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(i % 2)
            {
                sum += a[i].w;
            }
            else{
                sum1 += a[i].w;
            }
        }
        if(sum > sum1)
            cout << "red" << '\n';
        else if(sum < sum1)
            cout << "blue" << '\n';
        else
            cout << "fair" << '\n';
     }
}
B题

第一眼看完题目就想到了用multiset，因为multiset可以自动排好序，同时还不会去重。然后我们找的时候从multiset里挨着找就行了。然后删除的时候，我们只需要删除一个数字，而不是全删除，这个需要注意。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>
#include <set>
using namespace std;
int main()
{
    int t,n,A;
    scanf("%d",&t);
    while(t--)
    {
        multiset<int>M;
        multiset<int>::iterator it;
        string s;
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i)
        {
            cin >> s;
            if(s[0] == 'b')
            {
                scanf("%d",&A);
                M.insert(A);
            }
            else if(s[0] == 'c')
            {
                scanf("%d",&A);
                M.erase(M.find(A));
            }
            else{
                int flag = 1;
                for(it = M.begin(); it != M.end(); ++it)
                {
                    if(M.count(*it) == 1)
                    {
                        flag = 0;
                        printf("%d\n",*it);
                        break;
                    }
                }
                if(flag)
                {
                    printf("none\n");
                }
            }
        }
    }
}
C题

一道博弈题，一般我看到博弈就想直接放弃的，但是看到A的人挺多，不做的话也没题做啊QWQ。开始的时候写了前几个数字的答案，没发现什么。再后来重新做的时候，发现原来前面做错了几个数字，再理一遍思路，写出前几个数的答案，发现大于2的时候，全是另一个人赢，于是果断（其实是小心翼翼）的写了一个简单的代码就交了。A了，看来有的时候还真是需要敢想敢写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>
#include <set>
using namespace std;
int a[100001];
int main()
{
   int t, n;
   cin >> t;
   while(t--)
   {
     long long num;
     cin >> num;
     if(num <= 2)
        cout << "zbybr" << '\n';
     else
        cout << "blankcqk" << '\n';
   }
}
F题

题目是读懂了，需要达到三角形内部的三边共点，问题是真的不知道怎么写啊。后来看别人的题解，发现有个赛瓦定理，好吧，原谅我数学真的不好。同时还需要二分。后来WA的原因也是因为eps开的精度不够高。附上赛瓦定理的图：

塞瓦定理是指在△ABC内任取一点O，延长AO、BO、CO分别交对边于D、E、F，则

$$\frac{BD}{DC}\times\frac{CE}{EA}\times\frac{AF}{FB} = 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
44
45
46
47
48
49
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>
#include <set>
#include <math.h>
using namespace std;
const double eps = 1e-8;
int main()
{
   int n;
   double t1,t2,t3;
   scanf("%d",&n);
   while(n--)
   {
       scanf("%lf %lf %lf",&t1,&t2,&t3);
       double b = min(t1,t2);
       b = min(b,t3);
       int flag = 0;
       double l = 0.0 , r = b;
       while(l < r)
       {
           double mid = (l + r) / 2;
           double sum = 1;
           double num1 = mid/t1;
           double num2 = 1 - mid/t1;
           double num3 = num2/num1;
           sum *= num3;
           num1 = mid/t2;
           num2 = 1 - mid/t2;
           num3 = num2/num1;
           sum *= num3;
           num1 = mid/t3;
           num2 = 1 - mid/t3;
           num3 = num2/num1;
           sum *= num3;
           if(fabs(sum - 1.0) < eps){
            printf("YES %.4f\n",mid);
            flag = 1;
            break;
           }
           if(sum > 1)  l = mid;
           else r = mid;
       }
       if(!flag)
       cout << "NO" << '\n';
   }
}
H题

题解链接

J题

题目很简单，就是看两个数是不是相等，同时两个数还得都是11的倍数。注意题目中的数字可以非常大。师哥正好看到我在做这个题，当场指出我的错误，同时又耐心的告诉了我大数取模的处理方法。以前没涉及到这个，又收获了一点。

  • c++
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 <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>
#include <set>
using namespace std;
const int M1 = 11;
int main()
{
   int t;
   cin >> t;
   while(t--)
   {
       string s,s1;
        cin >> s;
        cin >> s1;
        int flag = 1;
        int cnt = 0;
        if(s.size() != s1.size())
        {
            cout << "NO" << '\n';
            continue;
        }
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == s1[i])
                cnt++;
        }
        if(cnt == s.size())
        {
            flag = 0;
        }
        int sum1 = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            sum1 = (sum1 * 10 + s[i] - '0') % M1;
        }
        if(sum1 == 0 && flag == 0)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
   }
}
  • JAVA
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
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);
		int t;
		BigInteger a,b;
		t = cin.nextInt();
		while(t-- > 0) {
		a = cin.nextBigInteger();
		b = cin.nextBigInteger();
		if(a.compareTo(b) != 0)
		{
			System.out.println("NO");
			continue;
		}
		if(a.mod(BigInteger.valueOf(11)).compareTo(BigInteger.valueOf(0)) == 0)
				{
			          System.out.println("YES");
				}
		else
			System.out.println("NO");
	}
}
}