语法周赛 Round 8 题解
2024年12月25日大约 6 分钟
A.红色警戒
分析
- 难度:主要难点在于读题
- 子任务 1(30 分):由于所有桥的耐久度都相同,所以炸掉谁都一样,本来直接输出任何一座桥的耐久度都可以,但要注意耐久度为
也要一辆卡车,所以至少要输出 。 - 子任务 2(30 分):此时保证了数据从小到大排序,所以第一座桥的耐久度是最低的,输出
即可。 - 子任务 3(40 分):此时要找到九座桥的最小值,再来按照前面的做法即可。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, ans;
ans = 1001;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
cin >> a; if (a < ans) ans = a;
if(ans == 0) ans = 1;
cout << ans;
return 0;
}
B.有趣的&运算
分析
- 难度:需要一些数学思维,要能推理出只要拆开了就只会让结果变大或者保持不变,因此答案就是只分为一个区间
[1,n]
,所有数进行与运算的结果。 - 子任务 1(30 分):只有两个数,答案只有两种情况:
或者 ,输出其中较小的即可。 - 子任务 2(30 分):
非常小,可以暴力枚举所有的划分方案,但实际上暴力枚举所有划分方案的代码挺难写。 - 子任务 3(40 分):求所有数进行与运算的结果,需要注意和求和的初始化为
不同,与运算的初始化比较复杂。你可以初始化为第一个数或者初始化为补码为全 的 。
满分参考代码
做法 1
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, ai, ans;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> ai;
if (i == 1)
ans = ai;
else
ans = ans & ai;
}
cout << ans;
return 0;
}
做法 2
利用
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, ai, ans;
cin >> n;
ans = -1;
for (int i = 1; i <= n; i++)
{
cin >> ai;
ans = ans & ai;
}
cout << ans;
return 0;
}
C.比赛的获奖规则
分析
- 难度:结构体排序的模拟题
- 子任务 1(30 分):此时省去了排序的步骤,可以先算出有效队伍数量,然后算出需要输出的排名,最后输出对应的排名即可。
- 子任务 2(30 分):最后输出的就是排在前面金牌区的选手,耐心写完排序后会简单很多。
- 子任务 3(40 分):题目怎么说的就怎么排序就好,我的代码中有一些特殊处理,我把打星队伍的排名挪到了最低,这样最后输出某个排名区间的队伍会方便一点。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int n;
struct Team
{
string school, team;
int solved, tim;
bool flag; // 是否打星
};
Team a[200000 + 5];
bool cmp(Team x, Team y)
{
if (x.flag == false &&
y.flag == false)
return x.school < y.school;
if (x.flag == false ||
y.flag == false)
return x.flag > y.flag;
if (x.solved != y.solved)
return x.solved > y.solved;
return x.tim < y.tim;
}
int main()
{
cin >> n;
int A = 0, J, Y, T;
for (int i = 1; i <= n; i++)
{
cin >> a[i].school >> a[i].team >>
a[i].solved >> a[i].tim;
a[i].flag = (a[i].solved > 0) &&
(a[i].team.back() != '*');
A += a[i].flag;
}
J = A * 10 / 100 + (A * 10 % 100 > 0);
Y = A * 30 / 100 + (A * 30 % 100 > 0) - J;
T = A * 60 / 100 + (A * 60 % 100 > 0) - Y - J;
sort(a + 1, a + n + 1, cmp);
string s;
cin >> s;
int l, r;
if (s == "gold")
l = 1, r = J;
else if (s == "silver")
l = J + 1, r = J + Y;
else
l = J + Y + 1, r = J + Y + T;
cout << (r - l + 1) << "\n";
for (int i = l; i <= r; i++)
cout << a[i].school << " "
<< a[i].team << " "
<< a[i].solved << " "
<< a[i].tim << "\n";
return 0;
}
D.真的是毒瘤题吗?
分析
- 难度:比较麻烦的二维数组上的模拟,满分需要一个小技巧,求出初始值后每次只修改变动带来的影响。
- 子任务 1(30 分):只有操作
,整个数组没有修改过,按照题目模拟求出所有单词出现的次数即可。 - 子任务 2(30 分):数据范围很小,可以纯枚举做所有操作。
- 子任务 3(40 分):数据范围比较大,每次查询不能纯暴力枚举了。当算出了初始的所有单词以及对应的出现次数后,容易发现每次只修改了一个位置,因此最多影响了和这个位置有关的单词。可以先去掉之前所有相关的单词,然后新增新产生的单词即可。这里我没有偷懒使用
map
存所有单词出现次数,而是直接采用了一个四维数组。然后我写了挺多辅助函数,来让我的主函数更简洁。当时间复杂度没有问题的时候,我建议同学们也可以采用这样的方法,不用图快,把每一块做清楚能省掉更多调试的时间。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
char g[305][305];
int cnt[30][30][30][30];
int dx[] = {0, 1, 0, 1};
int dy[] = {0, 0, 1, 1};
// 行数、列数、方向(竖1、横2、右下斜着3)、长度
string getS(int x, int y, int fx, int len)
{
if (x < 1 || y < 1)
return "";
if (fx == 1 && x + len - 1 > n)
return "";
if (fx == 2 && y + len - 1 > m)
return "";
if (fx == 3 && (x + len - 1 > n ||
y + len - 1 > m))
return "";
string res = "";
for (int i = 0; i < len; i++)
{
res += g[x][y];
x += dx[fx];
y += dy[fx];
}
return res;
}
// s 的出现次数加上 num
void cal(string s, int num)
{
int a[4] = {0, 0, 0, 0};
for (int i = 0; i < s.size(); i++)
a[i] = s[i] - 'a' + 1;
cnt[a[0]][a[1]][a[2]][a[3]] += num;
}
// 返回 s 的出现次数
int getCnt(string s)
{
int a[4] = {0, 0, 0, 0};
for (int i = 0; i < s.size(); i++)
a[i] = s[i] - 'a' + 1;
return cnt[a[0]][a[1]][a[2]][a[3]];
}
// 把 (x,y) 相关的单词数量增加 t
void change(int x, int y, int t)
{
for (int len = 1; len <= 4; len++)
{
cal(getS(x, y, 1, len), t);
cal(getS(x, y, 2, len), t);
cal(getS(x, y, 3, len), t);
}
for (int len = 2; len <= 4; len++)
{
cal(getS(x - 1, y, 1, len), t);
cal(getS(x, y - 1, 2, len), t);
cal(getS(x - 1, y - 1, 3, len), t);
}
for (int len = 3; len <= 4; len++)
{
cal(getS(x - 2, y, 1, len), t);
cal(getS(x, y - 2, 2, len), t);
cal(getS(x - 2, y - 2, 3, len), t);
}
for (int len = 4; len <= 4; len++)
{
cal(getS(x - 3, y, 1, len), t);
cal(getS(x, y - 3, 2, len), t);
cal(getS(x - 3, y - 3, 3, len), t);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> g[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int len = 1; len <= 4; len++)
{
cal(getS(i, j, 1, len), 1);
cal(getS(i, j, 2, len), 1);
cal(getS(i, j, 3, len), 1);
}
int q;
cin >> q;
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int x, y;
char c;
cin >> x >> y >> c;
change(x, y, -1);
g[x][y] = c;
change(x, y, 1);
}
if (op == 2)
{
string s;
cin >> s;
cout << getCnt(s) << "\n";
}
}
return 0;
}