# 题目大意
给定 a 和 n，请问 1→n 中，有多少个数，在十进制和 a 进制下同时都是回文数
# 数据范围
- 2≤a≤9
- 1 \le n \le 10^
# 题解
这题显然不能暴力枚举 1→n，可以发现，1012 内的回文数大概有 106 数量级的回文数，不妨考虑预处理好，然后遍历判断其是否是 a 进制
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| int n, a;
vector<int> hw;
int to_num(string s) {
int res = 0;
for (int i = 0; i < s.size(); i++)
res *= 10, res += (s[i] - '0');
return res;
}
void solve () {
cin >> a >> n;
int ans = 0;
for (auto num : hw) {
if (num > n)
break;
int t = num;
string res = "";
while (num >= a)
res += to_string(num % a), num /= a;
if (num)
res += to_string(num);
string res1 = res;
reverse(res1.begin(), res1.end());
if (res1 == res)
ans += t;
}
cout << ans << '\n';
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _ = 1;
for (int i = 1; i <= 999999; i++) {
string s = to_string(i), rs = s;
reverse(rs.begin(), rs.end());
hw.push_back(to_num(s + rs));
if (rs.size() > 1)
hw.push_back(to_num(s + rs.substr(1)));
else
hw.push_back(to_num(s));
}
sort(hw.begin(), hw.end());
while (_--)
solve();
return 0;
}
|
如果要预处理 N 以内的回文数，可以遍历 1→N，通过奇数、偶数长度的反转来实现预处理回文数
# 题目大意
现在有 n 座房子，分别位于 x1→xn，你需要在数轴上任意放置 m 所基站，基站的信号强度如果是 t 的话，那它只能影响到左右距离不超过 2t 的房子，请问，信号强度和的最小值是多少
# 数据范围
- 1≤M≤N≤5×105
- 1 \le x_i \le 10^
# 题解
显然，在最优情况下，基站的两个边界是都有房子的，那么题目要安排 m 个基站，也就是说，会把 i=1mini=nai→i=1maxnai，以 ai 为分割，分成了 m 个块
我们的需求是使得 ∑t 最小，也就是我们可以让剩余的 m−1 个空的长度尽可能大，这样减出来的 ∑t 就一定会更小
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void solve () {
cin >> n >> m, a = vector<int>(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
if (m >= n) {
cout << 0 << '\n';
return;
}
sort(a.begin() + 1, a.end());
int res = 0;
vector<int> dis;
for (int i = 2; i <= n; i++)
dis.push_back(a[i] - a[i - 1]);
sort(dis.begin(), dis.end());
for (int i = 0; i < n - m; i++)
res += dis[i];
cout << res << '\n';
}
|
# 题目大意
计算满足以下条件的整数三元组 (a,b,c) 的个数对 998244353 取模的结果
- 1≤a,b,c≤N
- a,b,c 互不相同
- a%b=c
# 数据范围
# 题解
# 1. 确定 b 的范围
题目要求 a,b,c 两两不相同，我们可以讨论一下他们的大小关系
- a<b 时，
a % b = a ，不满足三者不相同 - a>b 时，
a % b = c ，此时 N≥a>b，只要满足 b>c，则三者必然两两不相同
由 N≥a>b>c≥1 有，b∈[2,N−1]
# 2. 计算 a 的个数
由 N≥a>b>c≥1,b∈[2,N−1] 有，a∈[b+1,N]
因为 a%b=c≥1，所以要排除 a 是 b 的倍数
也就是
a=kb,k∈[2,⌊bN⌋]
所以，a 的个数是
(N−(b+1)+1)−(⌊bN⌋−2+1)=N−b−⌊bN⌋+1
# 3. 求答案
也就是说，答案是求
b=2∑N−1N−b−⌊bN⌋+1
显然，这样的话复杂度就爆炸了
b=2∑N−1(N−b+1)−b=2∑N−1(⌊bN⌋)
左侧可以用等差数列计算和，右侧可以用整除分块
# 整除分块
⌊bN⌋ 在 b 的某些连续区间内的取值是相同的，我们可以按照 ⌊bN⌋ 的值来对 b 进行分块，贡献是 长度 * 值
对于一个分块的起点 li 而言，其下一个分块的起点应该满足
li+1=min{x∣x>li,⌊N/x⌋<k}
⌊N/x⌋<k 有 L>⌊N/k⌋，所以 l[i+1] = min(n / k + 1, N)
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res = res * a % MOD;
a = a * a % MOD, b >>= 1;
}
return res;
}
void solve() {
cin >> n;
int inv2 = qmi(2, MOD - 2);
res = (((n - 2) % MOD) * ((n + 1) % MOD) % MOD) * inv2 % MOD;
int l = 2;
while (l < n) {
int k = n / l;
int ll = min(n / k + 1, n);
int cnt = ll - l;
res = (res + MOD - ((k % MOD) * (cnt % MOD) % MOD)) % MOD;
l = ll;
}
cout << res << "\n";
}
|
遇到 i=1∑n⌊i常数⌋ 时，可以考虑用整数分块的思想，整数分块求和的时间复杂度是 O(n) 的
