语法周赛 Round 14 题解
2024年12月25日大约 4 分钟
A.喜欢开方的 33DAI
分析
- 难度:趣味题,语法上只需要输入输出和常用数学函数,难点主要在运气。
- 子任务 1(30 分):输出
0
即可。 - 子任务 2(30 分):平方根有可能是
3
或-3
。任选一个输出,然后祈祷运气好猜对了即可,猜错了就再交一次。 - 子任务 3(40 分):输入一个数,输出他的算术平方根即可。本题难点在于判题时会随机的选择正的还是负的,所以如果错了需要再次提交,直到正确为止。如果代码没有问题,每次提交都有
\frac{1}{4}
的概率拿到满分。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x;
cin >> x;
cout << (int)sqrt(x) << "\n";
return 0;
}
可能有同学会好奇是怎么做到随机判题的,简单来说就是写了另一个代码来判断你的答案是否正确。我们把这样的判题方法叫做 special judge。
#include "testlib.h"
#include <ctime>
int main(int argc, char *argv[])
{
registerTestlibCmd(argc, argv);
int ja = ans.readInt();
int pa = ouf.readInt();
int seed = clock();
if (seed % 2)
ja = -ja;
if (ja != pa)
quitf(_wa, "expected %d, found %d, %d", ja, pa, seed);
quitf(_ok, "answer is %d, %d", ja, seed);
}
B. 喜欢除法的 TooY0ung
分析
- 难度:因为后两题相对较难,所以第二题给了个相对简单的题目。
- 子任务 1(30 分):当
时,显然 不用变化,如果 是偶数就不用变,否则就需要-1
,所以变成了一个简单的条件判断的题目。 - 子任务 2(30 分):容易发现就是要把每个
除以 的余数都减掉。子任务 2 的数据范围保证了不需要使用long long
- 子任务 3(40 分):子任务 2 的基础上开好
long long
即可。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, ai;
cin >> n;
long long ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> ai;
ans += ai % i;
}
cout << ans;
return 0;
}
C. 玩字符串的 Didi
分析
- 难度:简单分析、排序。
- 子任务 1(30 分):此时变化后要么是
、要么是 ,看看是否有一个和 一样就好。 - 子任务 2(30 分):一个凑数的子任务,没啥意义。
- 子任务 3(40 分):由于每次选择的区间左端点不能小于之前选择的区间左端点,所以显然可以考虑从小到大考虑每个位置作为左端点时需要做到多少。对于
来说,如果它与 一致,显然就不需要操作了,否则就需要在 串的 后面去找 ,假设在 的位置。此时显然就需要对 进行排序。因为如果对更短的区间排序,显然不可能有效。对更长的区间排序则有可能会变得更坏,不如回头再扩展到更长。如果排完序后一致,就可以处理下一个位置了,否则就说明不可能完成目标了。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
string t;
cin >> s >> t;
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == t[i])
continue;
// 找找 t[i] 在哪儿
int pos = -1;
for (int j = i + 1; j <= t.size(); j++)
if (s[j] == t[i])
{
pos = j;
break;
}
if (pos == -1)
{
cout << "No";
return 0;
}
// 对 i~pos 进行排序
ans++;
for (int j = i; j <= pos; j++)
for (int k = j + 1; k <= pos; k++)
if (s[k] < s[j])
swap(s[k], s[j]);
if (s[i] != t[i])
{
cout << "No";
return 0;
}
}
cout << "Yes\n";
return 0;
}
D. 随意发糖的 LEEZ
分析
- 难度:有一些小细节的模拟题
- 子任务 1(30 分):每次只能发一颗糖,那么总共缺几颗糖就发几次即可。
- 子任务 2(30 分):每次只能选一个人,那么就一个个去看看发几次能超过要求即可。
- 子任务 3(40 分):既然每次只能发一个区间,我们可以先类似于子任务 2,一个一个人看过去,先给当前用户发到溢出,然后把溢出的依次往后分给后面的
个人即可。有同学可能会觉得这是个双重循环会超时。实际上这个双重循环的时间复杂度还是 ,因为第二重循环每多执行一次,都是给下一个人装满了的情况,那么 枚举到下一个人时就不会在执行第二轮循环了。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int n, m, k, num;
int a[5005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k >> num;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++)
{
// 当前需要这么多
int now = m - a[i];
// 要加这么多次
int cnt = now / num + (now % num > 0);
ans += cnt;
int sum = cnt * num; // 一共这么多,可以分配给 k 个
for (int j = i; j <= i + k - 1 && j <= n; j++)
{
if (sum > m - a[j])
{
sum -= (m - a[j]);
a[j] = m;
}
else
{
a[j] += sum;
sum = 0;
break;
}
}
}
cout << ans << "\n";
return 0;
}