语法周赛 Round 22 题解
2024年12月25日大约 5 分钟
A. 测试三位数
分析
- 难度:简单三位数数位分解
- 子任务 1(30 分):此时所有数字都是完全正确的,输出
222
即可。 - 子任务 2(30 分):首先进行数位分解。因为没有
0
,只要对应位置的数字相等就输出2
。不相等就输出1
即可。 - 子任务 3(40 分):当对应位置不相等时,多检查一下和其它位置是否相等即可。
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
int i = a / 100 % 10;
int j = a / 10 % 10;
int k = a % 10;
int x = b / 100 % 10;
int y = b / 10 % 10;
int z = b % 10;
if (x == i)
cout << '2';
else if (x == j || x == k)
cout << '1';
else
cout << '0';
if (y == j)
cout << '2';
else if (y == i || y == k)
cout << '1';
else
cout << '0';
if (z == k)
cout << '2';
else if (z == i || z == j)
cout << '1';
else
cout << '0';
return 0;
}
B. 猜三位数
分析
- 难度:主要难度在于可能之前没接触过交互题。
- 子任务 1(30 分):直接尝试
的每个数字即可。 - 子任务 2(30 分):
的三个位置各不相同,所以可以过滤掉有相同的情况,剩下 种情况。 - 子任务 3(40 分):
- 做法 1:可以先猜
三个数,就可以确定三个数位分别是哪三个数。然后枚举三个数字的所有排列( 种情况)。这样最多 次就能完成了。 - 做法 2:每次猜的时候三个数独立变化,每个数位都从
尝试到 。如果某个数位回答的是 ,那就不变了。最多 次就猜完了。
- 做法 1:可以先猜
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int ans = 0;
char x, y, z;
cout << 123 << "\n";
cout.flush();
cin >> x >> y >> z;
if (x == '2' && y == '2' && z == '2')
return 0;
if (x != '0')
ans = ans * 10 + 1;
if (y != '0')
ans = ans * 10 + 2;
if (z != '0')
ans = ans * 10 + 3;
cout << 456 << "\n";
cout.flush();
cin >> x >> y >> z;
if (x == '2' && y == '2' && z == '2')
return 0;
if (x != '0')
ans = ans * 10 + 4;
if (y != '0')
ans = ans * 10 + 5;
if (z != '0')
ans = ans * 10 + 6;
cout << 789 << "\n";
cout.flush();
cin >> x >> y >> z;
if (x == '2' && y == '2' && z == '2')
return 0;
if (x != '0')
ans = ans * 10 + 7;
if (y != '0')
ans = ans * 10 + 8;
if (z != '0')
ans = ans * 10 + 9;
int a = ans / 100 % 10;
int b = ans / 10 % 10;
int c = ans % 10;
cout << a << b << c << "\n";
cout.flush();
if (x == '2' && y == '2' && z == '2')
return 0;
cout << a << c << b << "\n";
cout.flush();
if (x == '2' && y == '2' && z == '2')
return 0;
cout << b << a << c << "\n";
cout.flush();
if (x == '2' && y == '2' && z == '2')
return 0;
cout << b << c << a << "\n";
cout.flush();
if (x == '2' && y == '2' && z == '2')
return 0;
cout << c << a << b << "\n";
cout.flush();
if (x == '2' && y == '2' && z == '2')
return 0;
cout << c << b << a << "\n";
cout.flush();
if (x == '2' && y == '2' && z == '2')
return 0;
return 0;
}
C. 子串取模
分析
- 难度:经典的考察怎么把一些数位组合成一个数。
- 子任务 1(30 分):输出
对应的数字除以 的余数即可。 - 子任务 2(30 分):模数为
时只要考虑最后三位的值即可。 - 子任务 3(40 分):
- 假设
,则 对应的数为 。预处理所有 的幂次模 ,就可以 算出答案了。 - 可以直接用秦九韶算法,把式子转换为
构成的数显然等于 。 - 如果
是一个定值的话。这题可以进一步扩展数据范围。用类似于前缀和的方式,算出 的值 。这样 就是 。这样在预处理完后就可以 求每个问题的答案了。这个方式在字符串哈希算法的求子串哈希值时也会用到。
- 假设
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
string s;
cin >> n;
cin >> s;
while (n--)
{
int l, r, m;
cin >> l >> r >> m;
long long now = 0;
for (int i = l; i <= r; i++)
{
now = now * 10 + (s[i - 1] - '0');
now = now % m;
}
cout << now << "\n";
}
return 0;
}
D. K 的倍数或个位是 K
分析
- 难度:60 分就是个分类讨论的暴力枚举。满分需要一些数学方式处理。
- 子任务 1(30 分):所有数都是
的倍数,输出 即可。 - 子任务 2(30 分):暴力枚举
的每个数检查即可。 - 子任务 3(40 分):
- 为了方便处理,可以首先把问题转换成
满足条件的数量减去 满足条件的数的数量。我们就可以专心考虑怎么算 满足条件的数的数量了。 - 显然
中 的倍数有 个。 - 个位是
的数就是固定个位为 ,考虑其他位置的情况,显然可能是 ,最大的那个需要看看是否超过了 。 - 这里重复计算了既是
的倍数,个位又是 的情况。即 中, 是 的倍数的情况。去掉这些重复计算的就是答案了。
- 为了方便处理,可以首先把问题转换成
满分参考代码
#include <bits/stdc++.h>
using namespace std;
int n, k, l, r;
// 1~x 的答案
int f(int x)
{
// k 的倍数
int a = x / k;
// 个位是 k 的数
int b = x / 10; // [0~(x/10-1)]k
if (x % 10 >= k)
b++; // [x/10]k
// 个位是 k 且是 k 的倍数
int kk = k;//记录去掉 10 的贡献后的内容
if (k % 2 == 0)
kk /= 2;
if (k % 5 == 0)
kk /= 5;
int c = max(0, (x / 10 - 1) / kk); //[1~x/10-1]k
if (x / 10 >= 1 && x % 10 >= k && x / 10 * 10 % k == 0)
c++; //[x/10]k
if (x >= k)
c++; //[0]k
return a + b - c;
}
int main()
{
cin >> n >> k;
while (n--)
{
cin >> l >> r;
cout << f(r) - f(l - 1) << '\n';
}
return 0;
}