周赛weekend5

A.点外卖

分析

• 难度：简单分支语句
• 子任务 1（30 分）：由于黄焖鸡米饭的价格没达到所有红包的使用要求，所以红包都用不了，直接输出 n 即可。
• 子任务 2（30 分）：由于所有红包优惠的价格都一样，所以只需要判断能不能使用任何一个红包就好，即 n <= a1 || n <= a2 || n <= a3 成立就输出 n - b1，否则输出 n。
• 子任务 3（40 分）：分别判断在三个红包的影响下，分别的最终价格是多少，然后挑选最低的输出即可。

参考代码

#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)) << "\n";
    return 0;
}

B.优化代码

分析

核心在于三重循环的优化：

for (long long i = 1; i <= n; i++)
{
    for (long long j = 1; j <= i; j++)
    {
        long long now = 0;
        for (long long k = 1; k <= i; k++)
            if (k % 10 == 0)
                now += j;
        ans += now;
    }
}

• 难度：简单的数学、基础循环代码阅读理解
• 子任务 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)。

参考代码

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ans;
int main()
{
    cin >> n;
    ans = 0;
    for (long long i = 1; i <= n; i++)
        ans += i / 10 * ((1 + i) * i / 2);
    cout << ans << "\n";
    return 0;
}

F.unrank

分析

• 难度：60 分只要会基础的字符串，暴力枚举即可。满分做法较多。
• 子任务 1（30 分）：因为保证了 n 为 1，所以直接判断 m 个字符串有没有和第二行的那个字符串一样的即可。
• 子任务 2（30 分）：n,m 都小于等于 103，直接双重循环暴力枚举检查即可。
• 子任务 3（40 分）：重点是判断第三行的每个字符串是否在第二行出现过。
  • 可以把字符串当作一个 27 进制的整数处理，或者直接使用一个四维数组标记即可，这样的时间复杂度为 O(n+m)。
  • 学过 set 的同学可以直接用 set 标记，用一个 O(mlog⁡n) 时间复杂度的代码完成该题。
  • 当然也可以把两行字符串分别排序，然后用双指针检查，此时时间复杂度的瓶颈为排序的 O(nlog⁡n)。

参考代码

这里给出四维数组标记的做法。

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt=0;
string a[50010],r;
bool f[30][30][30][30]={};
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		int l=a[i].size(),c=4-l;
		for(int j=1;j<=c;j++)
		{
			a[i]+=(char)(96);
		}
		f[a[i][0]-96][a[i][1]-96][a[i][2]-96][a[i][3]-96]=true;
	}
	for(int i=1;i<=m;++i)
	{
		cin>>r;
		int l=r.size(),c=4-l;
		for(int j=1;j<=c;j++)
		{
			r+=(char)(96);
		}
		if(!f[r[0]-96][r[1]-96][r[2]-96][r[3]-96])
		{
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

E.最大逆序对和

分析

• 难度：前两个子任务比较简单，满分需要用贪心的思想去分析判断，对于前期同学一定难度。
• 子任务 1（30 分）：由于保证了整体逆序，所以直接输入前两个数，输出他们的和即可。也就是说，你提交一个 a+b 问题的代码就能拿到 30 分。
• 子任务 2（30 分）：因为 n≤5000，所以直接 O(n2) 枚举所有逆序对即可。但如果想要拿到 60 分，你需要判断当前是子任务 1 还是子任务 2。
• 子任务 3（40 分）：考虑枚举逆序对中靠后的那个第二个数 ai，显然对应的前一个数 aj 必须满足 j<i 并且 aj>ai。考虑到我们需要找到最大的逆序对和，显然贪心选择 a1∼ai−1 中最大的数来和 ai 对比肯定是最好的。维护一下这个前缀最大值就可以 O(n) 完成该题了。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[112345];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    int maxAi = a[1];
    for (int i = 2; i <= n; i++)
    {
        if (a[i] < maxAi)
            ans = max(ans, a[i] + maxAi);
        else
            maxAi = a[i];
    }
    cout << ans << "\n";
    return 0;
}