AcWing 2874. 整数小拼接
原题链接
中等
作者:
炽热的
,
2022-02-22 15:54:38
,
所有人可见
,
阅读 628
与B组题目类似,更简单一些
- 考虑拼接, 假如
1
和 23
拼接, 应该先让 1 * 100
然后+ 23
- 如果$A_j$和 $A_i$ 拼接, 则 $A_jA_i$ = $ Aj * 10^{k_i} + Ai $ (其中 $k_i$为 $A_i$ 的数位)
- 若使得 $ A_j * 10 ^ {k_i} + A_i <= k $
即为
$ A_j * 10^{k_i} <= k - A_i $
- 开11个哈希表, 预处理每个 $ A_j $
*
$ 10 ^ {0-10} $
- 然后枚举每个 $A_i$, 判断在第 $k_i$ 个哈希表中, 有多少个 $A_j$ 满足 $ A_j * 10^{k_i} <= k - A_i $
- 最后注意 $A_i$ 是否也在里面, 如果在里面,则答案减 $1$
可以先对数组排序, 查找用二分来做
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5 + 10;
int n;
LL k;
int a[N];
ULL s[11][N];
int find(ULL b[], LL d, int p) {
int l = -1, r = n - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if (b[mid] <= d) l = mid;
else r = mid - 1;
}
if (r >= p) r -- ;
return r + 1;
}
int main()
{
scanf("%d%lld", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n);
for (int i = 0; i < n; i ++ ) {
LL t = a[i];
for (int j = 0; j < 11; j ++ ) {
s[j][i] = t;
t = t * 10;
}
}
LL res = 0;
for (int i = 0; i < n; i ++ ) {
int len = to_string(a[i]).size();
res += find(s[len], k - a[i], i);
}
printf("%lld\n", res);
return 0;
}
牛牛
又来