T1 点外卖

难度：简单分支语句。

算法：模拟。

子任务 $1$（$30$ 分）：由于黄焖鸡米饭的价格没达到所有红包的使用要求，所以红包都用不了，直接输出 $n$ 即可。

子任务 $2$（$30$ 分）：由于所有红包优惠的价格都一样，所以只需要判断能不能使用任何一个红包就好，即 n <= a1 || n <= a2 || n <= a3 成立就输出 n - b1，否则输出 n。

子任务 $3$（$40$ 分）：分别判断在三个红包的影响下，分别的最终价格是多少，然后挑选最低的输出即可。

C++ 代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, a1, b1, a2, b2, a3, b3;
    int ans1, ans2, ans3;
    cin >> n;
    cin >> a1 >> b1;
    cin >> a2 >> b2;
    cin >> a3 >> b3;
    
    ans1 = ans2 = ans3 = n;
    if (n >= a1) ans1 -= b1;
    if (n >= a2) ans2 -= b2;
    if (n >= a3) ans3 -= b3;
    
    cout << min(ans1, min(ans2, ans3)) << endl;
    
    return 0;
}

T2 优化代码

难度：简单的数学、基础循环代码阅读理解。

算法：数学，模拟。

子任务 $1$（$30$ 分）：直接提交题面的代码即可，白送的 $30$ 分。

子任务 $2$（$30$ 分）：最内层的循环中，$k$ 从 $1$ 到 $i$ 的枚举，当 $k$ 为 $10$ 的倍数时，$now$ 被增加了 $j$。而 $1$ 到 $i$ 中，$10$ 的倍数有 i/10 个，所以整个内层循环可以优化成一句 now = (i / 10) * j。

子任务 $3$（$40$ 分）：优化完最内层循环后，在中间的循环里，$j$ 从 $1$ 到 $i$ 的枚举，每次循环都给 $ans$ 增加了 (i / 10) * j。即 ans += (i / 10) * 1 + (i / 10) * 2 + ... + (i / 10) * i。提取一个公因式 (i / 10)，就可以优化为 ans += (i / 10) * (1 + 2 + ... + i)，使用等差数列求和公式，即可把内部两层循环优化为 ans += (i / 10) * ((1 + i) * i / 2)。

C++ 代码：

#include <bits/stdc++.h>
using namespace std;

long long n, ans;

int main()
{
    cin >> n;
    ans = 0;
    
    for (long long i = 1; i <= n; i ++ )
        ans += i / 10 * (i * (1 + i) / 2);
    
    cout << ans << endl;
    
    return 0;
}

T3 unrank

难度：$60$ 分只要会基础的字符串，暴力枚举即可。满分做法较多。

算法：字符串处理，枚举。

子任务 $1$（$30$ 分）：因为保证了 $n$ 为 $1$，所以直接判断 $m$ 个字符串有没有和第二行的那个字符串一样的即可。

子任务 2（$30$ 分）：$n,m$ 都小于等于 $10^3$ ，直接双重循环暴力枚举检查即可。

子任务 $3$（$40$ 分）：重点是判断第三行的每个字符串是否在第二行出现过。

可以把字符串当作一个 $27$ 进制的整数处理，或者直接使用一个四维数组标记即可，这样的时间复杂度为 $O(n+m)$。

学过 $set$ 的同学可以直接用 $set$ 标记，用一个 $O(mlogn)$ 时间复杂度的代码完成该题。

当然也可以把两行字符串分别排序，然后用双指针检查，此时时间复杂度的瓶颈为排序的 $O(nlogn)$。

这里给出 $27$ 进制整数标记的做法。

C++ 代码：

#include <bits/stdc++.h>
using namespace std;

int n, m;
bool a[30 * 30 * 30 * 30 + 5];
string s;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> s;
        int now = 0;
        for (int i = 0; i < s.size(); i ++ )
            now = now * 27 + (s[i] - 'a' + 1);
        a[now] = true;
    }
    
    int ans = 0;
    for (int i = 1; i <= m; i ++ )
    {
        cin >> s;
        int now = 0;
        for (int i = 0; i < s.size(); i++)
            now = now * 27 + (s[i] - 'a' + 1);
        if (!a[now])
            ans ++ ;
    }
    
    cout << ans << endl;
    
    return 0;
}

T4 最大逆序对和

难度：前两个子任务比较简单，满分需要用贪心的思想去分析判断，对于前期同学一定难度。

算法：贪心。

子任务 $1$（$30$ 分）：由于保证了整体逆序，所以直接输入前两个数，输出他们的和即可。也就是说，你提交一个 $a+b$ 问题的代码就能拿到 $30$ 分。

子任务 $2$（$30$ 分）：因为 $n≤5000$，所以直接 $O(n^2)$ 枚举所有逆序对即可。但如果想要拿到 $60$ 分，你需要判断当前是子任务 $1$ 还是子任务 $2$。

子任务 3（40 分）：考虑枚举逆序对中靠后的那个第二个数 $a[i]$ ，显然对应的前一个数 $a[j]$ 必须满足 j<i 并且 $a[j]>a[i]$。考虑到我们需要找到最大的逆序对和，显然贪心选择 $a[1] ∼a[i−1]$ 中最大的数来和 $a[i]$ 对比肯定是最好的。维护一下这个前缀最大值就可以 $O(n)$ 完成该题了。

C++ 代码：

#include <bits/stdc++.h>
using namespace std;

int n;
int a[112345];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    
    int ans = 0, maxn = a[1];
    for (int i = 2; i <= n; i ++ )
    {
        if (a[i] < maxn)
            ans = max(ans, a[i] + maxn);
        else
            maxn = a[i];
    }
    
    cout << ans << endl;
    
    return 0;
}