Catshao

用户名：Catshao

访问量：25578

签　名：

stO KHIN Orz

等　　级
排　　名	172
经　　验	6748
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

8月月赛总结（附题解）
浏览：86

Dotcpp国庆Div.2题解
浏览：156

[ω] 最大子段乘积
浏览：95

你可能喜欢

蓝桥杯2020年第十一届省赛真题-整数小拼接

　　作者: Catshao　　　　发表时间：2022-02-10 17:34:03 浏览：1376　|　评论：2　

原题链接：蓝桥杯2020年第十一届省赛真题-整数小拼接

题面太炸，修了一下。

网上代码都是暴力，于是我自己写了下，并卡掉了暴力。

管理看到了这篇题解后，记得把这道题解掉隐藏。

-----------------

#### 暴力 30pts

两两暴力，并判断连在一起是否小于 $$K$$ 。时间复杂度为 $$O(n^2)$$ 期望得分 30 pts 。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100100;

int n;
long long k, a[MAX_N], ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) {
                continue;
            }
            if (a[i] * (long long)pow(10, int(log10(a[j]) + 1)) + a[j] <= k) {
                ans ++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
```

### 二分 100pts

将原序列排序，枚举每一个 $A_i$ ，二分找出能和它配对的 $A_j$ ，时间复杂度为 $$O(n \log n)$$ ，期望得分 100 pts。

拼接两个整数可以用 `log10(x) + 1` 计算整数 $$x$$ 的位数。

二分没必要自己写，可以用 `lower_bound` 。

不要忘记开 `long long` 。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100100;

int n;
long long k, a[MAX_N], ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        if (a[i] > k % (long long)pow(10, int(log10(a[i]) + 1))) {
            ans += upper_bound(a + i + 1, a + n + 1, k / (long long)pow(10, int(log10(a[i]) + 1)) - 1) - 1 - a - i;
            ans += upper_bound(a + 1, a + i, k / (long long)pow(10, int(log10(a[i]) + 1)) - 1) - 1 - a;
        } else {
            ans += upper_bound(a + i + 1, a + n + 1, k / (long long)pow(10, int(log10(a[i]) + 1))) - 1 - a - i;
            ans += upper_bound(a + 1, a + i, k / (long long)pow(10, int(log10(a[i]) + 1))) - 1 - a;
        }
    }
    cout << ans << endl;
    return 0;
}
```

0.0分

15 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

玉玊

请问这个a[i] > k % (long long)pow(10, int(log10(a[i]) + 1))为什么要这样判断，还有
ans += upper_bound(a + i + 1, a + n + 1, k / (long long)pow(10, int(log10(a[i]) + 1)) - 1) - 1 - a - i;
ans += upper_bound(a + 1, a + i, k / (long long)pow(10, int(log10(a[i]) + 1)) - 1) - 1 - a;
ans += upper_bound(a + i + 1, a + n + 1, k / (long long)pow(10, int(log10(a[i]) + 1))) - 1 - a - i;
ans += upper_bound(a + 1, a + i, k / (long long)pow(10, int(log10(a[i]) + 1))) - 1 - a;为什么一个是k / (long long)pow(10, int(log10(a[i]) + 1)) - 1，一个是k / (long long)pow(10, int(log10(a[i]) + 1)) + 1

2024-01-18 15:24:03

Catshao

mathjax 用习惯后忘记写四个 $$$$ 了。。。

2022-02-10 17:34:45

Catshao

TA的其他文章

你可能喜欢

【矩阵】（C语言代码）

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯2020年第十一届省赛真题-整数小拼接

评论区

精彩推荐

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

妹子杀手的故事（C语言代码）

哥德巴赫曾猜测（C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【金明的预算方案】（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

最小公倍数（C语言代码）

Catshao

TA的其他文章

你可能喜欢

【矩阵】 （C语言代码）

人见人爱A+B （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯2020年第十一届省赛真题-整数小拼接

评论区

精彩推荐

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

妹子杀手的故事 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【金明的预算方案】 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

最小公倍数 （C语言代码）

【矩阵】（C语言代码）

　　评论区

C二级辅导-统计字符（C语言代码）

妹子杀手的故事（C语言代码）

哥德巴赫曾猜测（C语言代码）

大神老白（C语言代码）

【金明的预算方案】（C++代码）

最小公倍数（C语言代码）