山东省第五届ACM省赛
比赛题目
总结：大约拿出了2个多小时的时间来看题，一个是开始的时间有点晚了，同时后期卡在一个题上纠结，也就不想做了，共A了4道题，看了看当年的榜单，也就是混个铜牌的末尾。但是如今大家都进步了，更不应该松懈了。
A题
纯粹的数学题，做这道题真的让我怀疑我的数学水平了，y’ = 2ax + b，我竟然认为在x处的切线的斜率是2a, 关键是求出抛物线的表达式，然后进行积分，这道题最后才A了，真的不应该啊。好处就是这种题不会WA，一遍过。
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 <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <math.h>
using namespace std;
int main()
{
double a;
double P,T;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lf %lf %lf",&P,&T,&a);
double b = tan(a);
double num;
num = ( b * P ) / (-(2.0 * T * P) + (T * T));
double sum;
sum = (num * T * T * T )/ 3.0 + (b * T * T) / 2.0 - 0.5 * (2 * num * T + b) * (P - T) * (P - T);
printf("%.3f\n",sum);
}
}
|
E题
签到题，求10以内的阶乘
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
| #include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <math.h>
using namespace std;
int main()
{
int t;
int n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int sum = 1;
for(int i = 1; i <= n; ++i)
{
sum *= i;
}
cout << sum << '\n';
}
}
|
F题
给你一颗完全二叉树，给你任意两个节点的标号，问你这两个节点之间的最短距离是多少。第一次看的时候没思路，看A的人比较多之后，就有思路了。我们先把深度较深的节点往上找他的祖先，知道他的祖先和那个较浅的节点是兄弟节点，同时我们记录好较深的节点移动了几次，假设是m次。这样之后我们只需要求两个同深度的节点他们的最短距离，我们同时把他们往上移，直到他们的祖先相同，假设移动的次数是n次，那么这两个同深度的节点的距离就是2 * n，最后2 * n + m就是答案
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
| #include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <math.h>
using namespace std;
const int maxn = 10000010;
int deep(int n)
{
return floor(log2(n)) + 1;
}
int main()
{
int t, n, m, n1, m1;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
n1 = max(n , m);
m1 = min(n , m);
int dp1 = deep(n1);
int dp2 = deep(m1);
int sum = 0;
while(dp1 > dp2)
{
n1 /= 2;
dp1 = deep(n1);
sum++;
}
if(n1 != m1)
{
for(int i = 1; ;i++)
{
n1 /= 2;
m1 /= 2;
sum += 2;
if(n1 == m1)
break;
}
}
cout << sum << '\n';
}
}
|
G题
比赛的时候没有A，赛后补题发现是dp，发现很多排列组合的题都是dp,找一个一般的状态，都与它的前一状态相关。比如说这道题，设置$ dp[i][j] $ 为前i场比赛用了j种桌子的方法数目
有如下递推式:
$$ dp[i][j] = dp[i - 1][j] \times j + dp[i][j] \times (m - j + 1)$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
long long dp[101][101];
while(scanf("%d %d",&n,&m) != EOF)
{
long long mod = 1000000007;
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= min(m, i); ++j)
{
dp[i][j] = (dp[i - 1][j] * j % mod + dp[i - 1][j - 1] * (m - j + 1) % mod) % mod;
}
}
cout << dp[n][m] << '\n';
}
}
|
J题
告诉你一个序列 ，x1,x2,x3,xn 以及每个值对应w1,w2,w3,wn;
现在问你满足要求的某一个Xk是哪一个数字。
我们看到题目中有个xi < xk 和 xi > xk 就要想到排序了，同时我们要用前缀和记录前i个数字的和，这样当我们遍历到第i个数字的时候，我们就可以在O（1）时间表达出 第i个数字之前的所有数字的和，以及第i个数字之后的所有数字的和。就可以在O（n）的复杂度内算出Xk的值。WA了两次，是因为没有注意long long。
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
| #include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <math.h>
using namespace std;
const int maxn = 10000010;
const double eps = 1e-6;
struct node{
int x ,w;
}a[maxn];
long long sum[maxn];
int cmp(node a,node b)
{
return a.x < b.x;
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
for(int i = 1; i <= n; ++i)
{
scanf("%d",&a[i].x);
}
long long SUM = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d",&a[i].w);
SUM += a[i].w;
}
sort(a + 1,a + n + 1,cmp);
sum[0] = 0;
for(int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + a[i].w;
}
for(int i = 1; i <= n; ++i)
{
double num1 = (double)sum[i - 1];
double num2 = (double)(sum[n] - sum[i]);
if(num1 < (SUM * 1.0) / 2 && ((num2 < (SUM * 1.0)/ 2) || fabs(num2 - (SUM * 1.0)/ 2) < eps))
{
printf("%d\n",a[i].x);
break;
}
}
}
}
|