语法周赛 Round 18 题解
2024年12月25日大约 4 分钟
A. 高兴
分析
- 难度:简单数学,基础条件判断。
- 子任务 1(30 分):需要注意,并不是无脑做正方形更好的,有可能不做成正方形能赚更多钱。如果做了正方形,那么肯定会做尽可能大的正方形。把两种情况都计算一下收入即可。子任务 1 保证了
是 的倍数,如果做正方形,边长刚好是n/4
,没有额外的藤条。 - 子任务 2(30 分):其实没有啥特殊的作用。
- 子任务 3(40 分):如果做正方形,显然会做成一个边长是
n/4
的正方形,然后会剩下 的藤条。计算两种方案的售价即可。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int n, a, b;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b;
int ans1 = n * a;
int ans2 = n % 4 * a + (n / 4) * (n / 4) * b;
cout << max(ans1, ans2);
return 0;
}
B. 考试
分析
- 难度:枚举优化。
- 子任务 1(30 分):此时显然能拿到满分,输出
即可。 - 子任务 2(30 分):保证了每题要么满分要么
分,贪心选择花时间小的即可。 - 子任务 3(40 分):基础枚举,检查所有情况,分别枚举
,然后显然 ,然后找到得分的最大值即可。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a1, a2, a3;
int b1, b2, b3;
int c1, c2, c3;
int d1, d2, d3;
cin >> a1 >> a2 >> a3;
cin >> b1 >> b2 >> b3;
cin >> c1 >> c2 >> c3;
cin >> d1 >> d2 >> d3;
int x1, x2, x3, x4, ans = 0;
for (int ia = 0; ia <= 120; ia++)
for (int ib = 0; ib <= 120 - ia; ib++)
for (int ic = 0; ic <= 120 - ia - ib; ic++)
{
int id = 120 - ia - ib - ic;
int now = 0;
if (ia >= a3)
now += 100;
else if (ia >= a2)
now += 60;
else if (ia >= a1)
now += 30;
if (ib >= b3)
now += 100;
else if (ib >= b2)
now += 60;
else if (ib >= b1)
now += 30;
if (ic >= c3)
now += 100;
else if (ic >= c2)
now += 60;
else if (ic >= c1)
now += 30;
if (id >= d3)
now += 100;
else if (id >= d2)
now += 60;
else if (id >= d1)
now += 30;
if (now > ans)
{
ans = now;
x1 = ia;
x2 = ib;
x3 = ic;
x4 = id;
}
}
//cout << ans << "\n";
cout << x1 << " " << x2 << " " << x3 << " " << x4 << "\n";
return 0;
}
C. 加速
分析
- 难度:简单推理,字符串
- 子任务 1(30 分):显然可以列举出来所有情况。
- 子任务 2(30 分):保证了有解,可以想到如果要翻转,那必然是某个地方出现了连续两个相同的字符,需要在两个相同的字符中间断开翻转。
- 子任务 3(40 分):如果出现了连续三个字符一样,或者有多处连续两个字符一样显然都是无解。但需要注意一个特殊情况,万一断开的位置反转到后面有一样的字符也不可以,比如
rrbr
,前两个字符断开反转的话,到后面还是相等的两个字符。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
int cntX = 0;
int pos = 0;
for (int i = 1; i < n; i++)
{
if (s[i] == s[i - 1])
{
cntX++;
pos = i;
}
}
// 多个位置要断开
if (cntX > 1)
{
cout << "-1";
return 0;
}
// 断开的地方不能翻到后面去
if (cntX == 1 && s[pos] == s[s.size() - 1])
{
cout << "-1";
return 0;
}
cout << pos;
return 0;
}
D. 油箱
分析
- 难度:暴力枚举。
- 子任务 1(30 分):保证两个油箱,双重循环枚举所有装油可能性即可。
- 子任务 2(30 分):每个油箱容量都是
,那显然只有010101....
和101010...
两种合法的装油方法,算算这两个有几个装油量小于 即可。 - 子任务 3(40 分):很容易被误会为类似于摆花要考动态规划,但考虑到
且 ,显然可以用所有 位数来枚举所有可能性。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[10];
int x[10];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
int up = 1;
for (int i = 1; i <= n; i++)
up *= 10;
ans = 0;
for (int i = 0; i < up; i++)
{
for (int j = 1, ii = i; j <= n; j++)
{
x[j] = ii % 10;
ii /= 10;
}
bool flag = true;
// 和为 m
int sum = 0;
for (int j = 1; j <= n; j++)
sum += x[j];
if (sum > m)
flag = false;
// 油箱限制范围内
for (int j = 1; j <= n; j++)
if (x[j] > a[j])
flag = false;
// 相邻奇偶性不同
for (int j = 2; j <= n; j++)
if (x[j] % 2 == x[j - 1] % 2)
flag = false;
if (flag)
ans++;
}
cout << ans;
return 0;
}