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

1525 阅读 2 评论 0 点赞

原题链接：蓝桥杯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分

12 人评分

本文分类：题解列表
浏览次数：1525 次浏览
发布日期：2022-02-10 17:34:03
本文链接：https://blog.dotcpp.com/a/83775

上一篇 > Hfifipsysta-2072-[STL训练]寻梦（C++代码）
下一篇 > 1471: 蓝桥杯基础练习VIP-矩形面积交(简单易理解C语言版)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 2 条评论

发表评论取消回复

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 2 条评论

发表评论 取消回复

评论列表共有 2 条评论

发表评论取消回复