山东省第八届ACM省赛 总结

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

题目链接

总结今天下午的做题情况：做了一下第八届省赛的题目，A了3个题，做的第4个题简直是太坑了。看了题解后，真的想实名吐槽一下这个题目。（当然既然有做出来的，说明也是我的问题）

F题

这就是我想说的题目，我把复数考虑了进去，认为如果二次方程有复数解，也应该输出NO，谁知道按照题目的意思，这也是无解的情况，输出YES，因为这一点我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
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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long ll;
const double eps = 1e-7;
int main()
{
    int t,a ,b ,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&a,&b,&c);
        if(a == 0 && b == 0 && c == 0)
        {
            cout << "NO" << '\n';
            continue;
        }
        if(a == 0 && b == 0 && c != 0)
        {
            cout << "YES" << '\n';
            continue;
        }
        if(a == 0 && b != 0 && c == 0)
        {
            cout << "YES" << '\n';
            continue;
        }
        if(a == 0 && b != 0 && c != 0)
        {
            if( (-c) % b == 0)
            {
                cout << "YES" << '\n';
                continue;
            }
            else
            {
                cout << "NO" << '\n';
                continue;
            }
        }
        int num = b * b - 4 * a * c;
        if(num < 0)
        {
            cout << "YES" << '\n';
            continue;
        }
        int flag = 0;
        for(int i = -11 ; i <= 11; ++i)
        {
            if(num == i * i)
            {
                flag = 1;
                break;
            }
        }
        if(!flag)
        {
            cout << "NO" << '\n';
            continue;
        }
        int num1 = -b + (int)sqrt(num);
        int num2 = -b - (int)sqrt(num);
        if(num1 % (2 * a) != 0 || num2 % (2 * a) != 0)
        {
            cout << "NO" << '\n';
            continue;
        }
        else{
            cout << "YES" << '\n';
            continue;
        }

    }
}

G题

快速幂模板题。

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
long long quick(ll a,ll b)
{
    long long ans = 1;
    a = a % mod;
    while(b)
    {
        if(b % 2)
            ans = ans * a % mod;
        b = b / 2;
        a = a * a % mod;
    }
    return ans;
}
int main()
{
    ll n,m;
    cin >> n >>m ;
    ll sum = 0;
    for(ll i = 1; i <= n; ++i)
    {
        sum = (sum + quick(i,m)) % mod;
    }
    cout << sum << '\n';

}

I题

先找出规律，和五一假期一次比赛的差不多，这个还简单点。看这个数对3取余的结果就行。本来想用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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int elect(string s)
{
    int sum = 0;
    for(int i = 0; i <= s.size(); ++i)
    {
        sum = (sum  * 10 + s[i] - '0') % 3;
    }
    return sum;
}
int main()
{
    string s;
    while(cin >> s)
    {
        int c = elect(s);
        if(c == 0)
            cout << '0' << '\n';
        else
            cout << '1' << '\n';
    }

}

J题

感觉和以前做的一道题目也差不多，当时没有A，今天重新再做的时候思路就很明确了，先把每个数字从小到大排个序，然后从大数开始往前看，究竟下面的小数可不可以加呢，我们需要判断一下他对整体的结果有利没有，有的话就加上，同时还要更新总体的sum。这个题目还有注意的是sum会爆int。

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-7;
struct node{
   int cnt,val;
}a[200001];
int cmp(node a,node b)
{
    return a.val > b.val;
}
int b[200001];
int sum1[200001];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i].val);
    }
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i].cnt);
    }
    sort(a + 1,a + n + 1,cmp);
    int tot = 0;
    sum1[0] = 0;
    for(int i = 1; i <= n ; ++i)
    {
        for(int j = 1; j <= a[i].cnt; ++j)
        {
            b[++tot] = a[i].val;
            sum1[tot] = sum1[tot - 1] + b[tot];
        }
    }
    long long sum = 0;
    for(int i = 1; i <= tot; ++i)
        {
            if(sum1[i - 1] + b[i] > 0)
            {
                sum = sum + sum1[i - 1] + b[i];
            }
            else{
                break;
            }
        }
    cout << sum << '\n';
}