B4075 [NOIP-X2018 山东] 11 的倍数

· · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考查字符串的使用。

根据题意，x_i 的位数可以达到 100 位，使用 int 类型、long long 类型等都无法存下它们。因此考虑使用字符串作为存储容器，因为字符串的好处就是可以无限延伸，位数不限。

接下来介绍一种做法直观，但是不好编写代码的做法：

根据 s_1 和 s_2 的含义，计算 s_1 和 s_2。以计算 s_1 为例。假设 x_i 的长度是 l，那么 x_i 的个位、百位、万位……应当是：x_i[l-1],x_i[l-3],x_i[l-5],\dots（需要注意，字符串的下标是从 0 到 l-1）。例如对于一个正整数 \red{6}\blue{5}\red{4}\blue{7}\red{2} 来说，它的长度是 5，那么应当分别取 x_i[4],x_i[2],x_i[0]，即分别是 2,4,6 加进 s_1，答案是 12。

重点： 虽然这些字符看起来是数字，但是做运算的时候，数值与看起来的数字完全不同！例如，字符 2，它看起来是 2，其实在做运算中它是 50，因为字符 2 的 ASCII 码是 50。因此，对于取出的字符 x[i]，我们需要使用 s1 += x[i] - '0'（或者是 s1 += x[i] - 48）的方式让它变为这个字符的面值。（例如：2 被视作是 50，而 50-48 是 2，即可让 s1 加上 2，而不是 s1 加上 50）

对于 s_2，同理应当为 x_i[l-2],x_i[l-4],x_i[l-6],\dots。对于 \red{6}\blue{5}\red{4}\blue{7}\red{2} 来说，分别是 x_i[3] 和 x_i[1]，分别是 7,5 加进 s_2，答案是 12。

接下来只需判断 s_1\div 11 和 s_2\div 11 的余数是否相等了。

但是，这样的做法虽然直观，但是在编写代码上存在问题。对于字符串 x，可以调用 x.length() 得到字符串 x 的长度。但是长度的类型默认是无符号整型。如果字符串的长度为 1（即：是个一位数），那么调用 x.length()-2，会出现无符号整型的向下溢出，变为一个非常大的数字，可能会导致计算问题。为此，可以定义 int 类型的变量 len 预先以 int 类型存储下字符串的长度，再做 -2 的操作，是安全的。

参考代码（部分）：

int s1 = 0, s2 = 0, len = x.length();
for (int i = len - 1; i >= 0; i -= 2)
    s1 += x[i] - '0';
for (int i = len - 2; i >= 0; i -= 2)
    s2 += x[i] - '0';

因此，这里介绍一个更好的做法：我们不必纠结于 s_1 和 s_2 的实际意义！在 \red{6}\blue{5}\red{4}\blue{7}\red{2} 这一个例子中，s_1=6+4+2 还是 s_1=5+7 其实都是一样的，关键在于 s_1 和 s_2 是错开来交替地选数字的。因此可以将两个 for 循环并作一个，交替将数字加入 s_1 或 s_2。

参考代码（部分）：

for (int i = 0; i < x.length(); i++) {
    if (i % 2 == 0)
        s1 += x[i] - '0';
    else
        s2 += x[i] - '0';
}

当然，可以使用数组，省略这一个 if 结构：

for (int i = 0; i < x.length(); i++)
    s[i % 2 + 1] += x[i] - '0';
// 比较 s[1] % 11 和 s[2] % 11 即可