2021牛客暑期多校训练营1 F题 Find 3-friendly Integers
A positive integer is 3-friendly if and only if we can find a continuous substring in its decimal representation, and the decimal integer represented by the substring is a multiple of $3$.
For instance:
- ${104}$ is 3-friendly because "0" is a substring of "104" and 0mod $0\mod3=0$.
- ${124}$ is 3-friendly because "12" is a substring of "124" and $12\mod3=0$ . "24" is also a valid substring.
- ${17}$ is not 3-friendly because $1\mod 3≠0, 7\mod 3≠0, 17\mod 3≠0$ .
Note that the substring with leading zeros is also considered legal.
Given two integers ${L}$ and ${R}$ , you are asked to tell the number of positive integers ${x}$ such that $L≤x≤R$ and ${x}$ is 3-friendly.
输入描述:
There are multiple test cases. The first line of the input contains an integer $T(1 \le T \le 10000)$ , indicating the number of test cases. For each test case:
The only line contains two integers $L,R(1 \le L \le R \le 10^{18})$, indicating the query.
输出描述:
For each test case output one line containing an integer, indicating the number of valid ${x}$ .
示例1
输入
3
4 10
1 20
1 100
输出
3
11
76
题解
这道题是一道规律题(呜呜一开始看成了数位dp,被自己蠢到),问你 $l-r$ 之间有多少个数满足至少有一个字串是3的倍数(注意0也是)。
核心规律就是:
- 当数字大于100时,所有数一定满足条件(任意三个10以内数字,一定满足数字之间有某种相加方式得到的结果是3的倍数)。
- 100以内,打表或者暴力判断均可。
这道题可以打一个表看看规律,也可以直接推理得到(去推数位dp的我是真的傻)。
代码
代码如下:
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn = 2e3 + 10;
typedef long long ll;
int T;
ll l, r;
int a[100] = {
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1,
0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};
int main() {
cin >> T;
while (T--) {
cin >> l >> r;
ll sum = 0;
if (l >= 100) {
sum = r - l + 1;
} else {
if (r < 100) {
for (int i = l; i <= r; i++) {
if (a[i]) sum++;
}
} else {
sum += r - 100 + 1;
for (int i = l; i <= 99; i++) {
if (a[i]) sum++;
}
}
}
cout << sum << endl;
}
return 0;
}