山东省第六届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的倍数。注意题目中的数字可以非常大。师哥正好看到我在做这个题，当场指出我的错误，同时又耐心的告诉了我大数取模的处理方法。以前没涉及到这个，又收获了一点。
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';
}
}
|
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");
}
}
}
|