# **A. 测试三位数**

## **分析**

- **难度**：简单三位数数位分解
- **子任务 1（30 分）**：此时所有数字都是完全正确的，输出 `222` 即可。
- **子任务 2（30 分）**：首先进行数位分解。因为没有 `0`，只要对应位置的数字相等就输出 `2`。不相等就输出 `1` 即可。
- **子任务 3（40 分）**：当对应位置不相等时，多检查一下和其它位置是否相等即可。

## **满分参考代码**

```cpp
#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 分）**：直接尝试 $100 \sim 999$ 的每个数字即可。
- **子任务 2（30 分）**：$a$ 的三个位置各不相同，所以可以过滤掉有相同的情况，剩下 $9 * 9 * 8 = 648$ 种情况。
- **子任务 3（40 分）**：
  - 做法 1：可以先猜 $123, 456, 789$ 三个数，就可以确定三个数位分别是哪三个数。然后枚举三个数字的所有排列（$6$ 种情况）。这样最多  $9$ 次就能完成了。
  - 做法 2：每次猜的时候三个数独立变化，每个数位都从 $0$ 尝试到 $9$。如果某个数位回答的是 $2$，那就不变了。最多 $10$ 次就猜完了。

## **满分参考代码**

```cpp
#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 分）**：输出 $s_l$ 对应的数字除以 $m$ 的余数即可。
- **子任务 2（30 分）**：模数为 $1000$ 时只要考虑最后三位的值即可。
- **子任务 3（40 分）**：
  - 假设 $n = r - l$，则 $s_l \sim s_r$ 对应的数为 $s_l \times 10^n + s_{l+1} \times 10^{n - 1} + ···+s_r \times 10^0$。预处理所有 $10$ 的幂次模 $m$，就可以算出答案了。
  - 可以直接用秦九韶算法，把式子转换为 $s_l \sim s_r$ 构成的数显然等于 $(...((s_l \times 10 + s_{l+1}) \times 10 + s_{l+2})...) \times 10 + s_r$。
  - 如果 $m$ 是一个定值的话。这题可以进一步扩展数据范围。用类似于前缀和的方式，算出 $s_l \sim s_r$ 的值 $pre_i$。这样 $s_l \sim s_r$ 就是 $pre_r - pre_{l-1} \times 10^{r-l}$。这样在预处理完后就可以求出每个问题的答案了。这个方式在字符串哈希算法的求子串哈希值时也会用到。

## **满分参考代码**

```cpp
#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 分）**：所有数都是 $1$ 的倍数，输出 $r - l + 1$ 即可。
- **子任务 2（30 分）**：暴力枚举 $l \sim r$ 的每个数检查即可。
- **子任务 3（40 分）**：
  - 为了方便处理，可以首先把问题转换成 $l \sim r$ 满足条件的数量减去 $1 \sim l - 1$ 满足条件的数的数量。我们就可以专心考虑怎么算 $1 \sim r$ 满足条件的数的数量了。
  - 显然 $1 \sim r$ 中 $k$ 的倍数有 $\lfloor \frac{i}{k} \rfloor$ 个。
  - 个位是 $k$ 的数就是固定个位为 $k$，考虑其他位置的情况，显然可能是 $(0 \sim \lfloor \frac{i}{10} \rfloor)(k)$，最大的那个需要看看是否超过了 $i$。
  - 这里重复计算了既是 $k$ 的倍数，个位又是 $k$ 的情况。即 $(0 \sim \lfloor \frac{i}{10} \rfloor)(k)$ 中，$(0 \sim \lfloor \frac{i}{10} \rfloor)(0)$ 是 $k$ 的倍数的情况。去掉这些重复计算的就是答案了。

## **满分参考代码**

```cpp
#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;
}
```