语法周赛 Round 4 题解
2024年12月25日大约 4 分钟
A.点外卖
分析
- 难度:简单分支语句
- 子任务 1(30 分):由于黄焖鸡米饭的价格没达到所有红包的使用要求,所以红包都用不了,直接输出
即可。 - 子任务 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 分):直接提交题面的代码即可,白送的
分。 - 子任务 2(30 分):最内层的循环中,
从 到 的枚举,当 为 的倍数时, 被增加了 。而 到 中, 的倍数有 个,所以整个内层循环可以优化成一句now = (i / 10) * j;
- 子任务 3(40 分):优化完最内层循环后,在中间的循环里,
从 到 的枚举,每次循环都给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;
}
C.unrank
分析
- 难度:
分只要会基础的字符串,暴力枚举即可。满分做法较多。 - 子任务 1(30 分):因为保证了
为 ,所以直接判断 个字符串有没有和第二行的那个字符串一样的即可。 - 子任务 2(30 分):
都小于等于 ,直接双重循环暴力枚举检查即可。 - 子任务 3(40 分):重点是判断第三行的每个字符串是否在第二行出现过。
- 可以把字符串当作一个
进制的整数处理,或者直接使用一个四维数组标记即可,这样的时间复杂度为 。 - 学过
set
的同学可以直接用set
标记,用一个 时间复杂度的代码完成该题。 - 当然也可以把两行字符串分别排序,然后用双指针检查,此时时间复杂度的瓶颈为排序的
。
- 可以把字符串当作一个
满分参考代码
这里给出张昊宇同学的四维数组标记的做法。
#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;
}
D.最大逆序对和
分析
- 难度:前两个子任务比较简单,满分需要用贪心的思想去分析判断,对于前期同学一定难度。
- 子任务 1(30 分):由于保证了整体逆序,所以直接输入前两个数,输出他们的和即可。也就是说,你提交一个
问题的代码就能拿到 分。 - 子任务 2(30 分):因为
,所以直接 枚举所有逆序对即可。但如果想要拿到 分,你需要判断当前是子任务 还是子任务 。 - 子任务 3(40 分):考虑枚举逆序对中靠后的那个第二个数
,显然对应的前一个数 必须满足 并且 。考虑到我们需要找到最大的逆序对和,显然贪心选择 中最大的数来和 对比肯定是最好的。维护一下这个前缀最大值就可以 完成该题了。
满分参考代码
#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;
}