Catshao

用户名：Catshao

访问量：28828

签　名：

stO KHIN Orz

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

　　自我简介：

TA的其他文章

【小灰】树状数组动画详解
浏览：176

vector、deque、list的速度和内存的比较
浏览：555

Dotcpp编程2021年七月月赛题面
浏览：740

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

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

　　作者: Catshao　　　　发表时间：2022-02-10 17:34:03 浏览：1472　|　评论：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的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

【作业调度方案】（C语言代码）

C二级辅导-阶乘数列（C++代码）

点我有惊喜！你懂得！

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

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

评论区

精彩推荐

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

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

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

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

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

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

P1044 （C++代码）

明明的随机数（C语言代码）

P1001 （Java代码）

test 4不要直接粘贴，修改内容

Catshao

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

【作业调度方案】 （C语言代码）

C二级辅导-阶乘数列 （C++代码）

点我有惊喜！你懂得！

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

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

评论区

精彩推荐

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

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

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

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

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

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

P1044 （C++代码）

明明的随机数 （C语言代码）

P1001 （Java代码）

test 4不要直接粘贴，修改内容

【作业调度方案】（C语言代码）

C二级辅导-阶乘数列（C++代码）

　　评论区

明明的随机数（C语言代码）