山东省第五届ACM省赛 总结

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

山东省第五届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;
           }
       }
   }
}