赛后总结

我感觉这次比赛比较难的就第D题和第E题，一个是简化版背包，一个是贪心，其他的都比较简单，用来招新生的话感觉正好，我估计真的去他们学校比的话也就能全对个四题左右吧，其他全是暴力骗分。

我9点半才看到题目，他们应该都比完了，我花了半个小时就全部做出来了，可惜我不是这学校的 55555

题目描述:

解题思路

没啥好说的,基本上全是暴力，遇到字符'A'就加1，遇到字符'B'就减1，然后用一个变量记录最大的值。

代码

//问题A
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int x = 0;
    int n;
    cin >> n;
    string s;
    cin >> s;
    int num = 0;
    int maxnum = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'A')
        {
            x++;
        }
        if (s[i] == 'B')
        {
            x--;
        }
        num = x;
        if (num > maxnum)
        {
            maxnum = num;
        }
    }
    cout << maxnum << endl;
    return 0;
}

题目描述:

解题思路

这题我感觉数据范围过大了，我用的动态规划应该只能过一半的样例，可能需要用到滚动数组或者矩阵快速幂优化，不过能暴力骗分就行，毕竟半小时做的。

代码

//问题B
#include <iostream>
using namespace std;
const long N = 1e8 + 7;
typedef long long LL;
LL q[N];
int main()
{
    LL n;
    scanf("%lld", &n);
    q[0] = 2;
    q[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        q[i] = q[i - 1] + q[i - 2];
    }
    printf("%lld", q[n]);
    return 0;
}

题目描述:

解题思路

这道题我听说他们后面把数据范围加强了，我一开始看题面还以为是那种求总方案的个数或者求花最少的钱的方案之类的dfs的题，后面我又想毕竟是新生赛不可能那么难，于是试着暴力居然过了，看来真是暴力出奇迹。

代码

//问题C
#include <iostream>
using namespace std;
int main()
{
    long n;
    cin >> n;
    int x = 4, y = 7;
    long a = 0, b = 0;
    while (1)
    {
        if (a == n || b == n || a + b == n)
        {
            cout << "Yes" << endl;
            break;
        }
        else
        {
            a = a + x;
            b = b + y;

            if (a > n && b > n && a + b > n)
            {
                cout << "No" << endl;
                break;
            }
        }
    }
    return 0;
}

题目描述:

解题思路

这道题的输入输出样例我真的是不能再熟悉了，就是01背包的样例改过来的，我看了下题目果然是背包问题简化版，想不到新生赛居然出这种题，要是那种没看过背包问题的岂不是直接没了，不过还是被我用哈希表给暴力出来了。

代码

//问题D
#include <iostream>
using namespace std;
const int N = 31;
int v[N], w[N];
int n, m, t, count;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> t;
        for (int j = 0; j < t; ++j)
        {
            cin >> v[j];
            w[v[j]]++;
        }
    }

    for (int i = 0; i < m; ++i)
    {
        if (w[i] == n)
        {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

题目描述:

解题思路

这道题是很明显的贪心问题，难点就在于如何模拟他的选择，如果只选最大的分数就有可能变成10的倍数，如果只选不可能变成10的倍数的分数就可能无法使最后的总得分最大，所以既要最后的总得分不能是10的倍数，又要分数尽可能的大。

我的思路是先把全部的分数加起来，再利用排序从最小的分数开始减，减一次判断一次减之后是不是10的倍数，如果减之后不是那么就减，如果减之后依然是那么就不减，继续判断下一个数，将损失降到最小。

代码

//问题E
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 101;
int q[N], sum, maxnum;
int n;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            cin >> q[i];
            sum += q[i];
        }
        if (sum % 10 == 0)
        {
            sort(q, q + n);
            for (int i = 0; i < n; ++i)
            {
                if (sum - q[i] % 10 != 0)
                {
                    sum -= q[i];
                    break;
                }
            }
        }

        if (sum % 10 == 0)
        {
            sum = 0;
        }
        cout << sum << endl;
        sum = 0;
    }
    return 0;
}

题目描述:

解题思路

这道题没啥好说的，看图都能看出来，四条从下往上的线可以构成3个空格，三条从右往左的线可以构成2个空格，把它们两个的空格数乘起来就可以得到答案。

代码

//问题F
#include <iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    cout << (n - 1) * (m - 1) << endl;
    return 0;
}

题目描述:

解题思路

这道题主要考的就是字符转数字的技巧，看过我以前的高精度博客就知道，减去字符'0'就可以将一个数字字符转成可以参与运算的整形数字，然后乘10来进位，绝对值用abs()函数来求，最后用一个变量将所得的差值最小的数存储起来。

代码

//问题G
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int x = 0;
    int sum = 0;
    int minnum = INT_MAX, k;
    for (int i = 0; i < s.size() - 2; ++i)
    {
        k = i;
        for (int j = 0; j < 3; ++j)
        {
            x += (s[k] - '0');
            if (j != 2)
            {
                x *= 10;
            }

            k++;
        }
        sum = abs(x - 753);
        if (sum < minnum)
        {
            minnum = sum;
        }
        x = 0;
    }
    cout << minnum << endl;
    return 0;
}