和各位说明：以后的题解（包括以前的）大部分都是用<mark>STL模板库来做（考试用的格式）</mark>，本章我只会用第一道题来做一个说明。
链接索引🔗：
第七章 分治算法
分治——分而治之
这一张将从分治（二分）一直延伸到<mark>二分查找、二分函数（lower_bound 以及 upper_bound 等）和二分答案</mark>，只要理解而且能用图来表示出来，那基本上就没有难题了！！！
Let’s go！！！
1325：【例7.4】 循环比赛日程表
正常版本
#include <bits/stdc++.h>
using namespace std;
int a[101][101], m, d;
int main(){
cin >> m;
a[1][1] = 1;
d = 1;
for (int k = 1; k <= m; k++){
for (int i = 1; i <= d; i++){
for (int j = d + 1; j <= 2 * d; j++){
a[i][j] = a[i][j - d] + d;
}
for (int i = d + 1; i <= 2 * d; i++){
for (int j = d + 1; j <= 2 * d; j++){
a[i][j] = a[i - d][j - d];
}
}
for (int i = d + 1; i <= 2 * d; i++){
for (int j = 1; j <= d; j++){
a[i][j] = a[i - d][j + d];
}
}
}
d *= 2;
}
for (int i = 1; i <= pow(2, m); i++){
for (int j = 1; j <= pow(2, m); j++){
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
STL模板库
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int m, d;
vector<vector<int> > a;
int main() {
cin >> m;
a.resize(pow(2, m) + 1, vector<int>(pow(2, m) + 1));
a[1][1] = 1;
d = 1;
for (int k = 1; k <= m; k++) {
for (int i = 1; i <= d; i++) {
for (int j = d + 1; j <= 2 * d; j++) {
a[i][j] = a[i][j - d] + d;
}
}
for (int i = d + 1; i <= 2 * d; i++) {
for (int j = d + 1; j <= 2 * d; j++) {
a[i][j] = a[i - d][j - d];
}
}
for (int i = d + 1; i <= 2 * d; i++) {
for (int j = 1; j <= d; j++) {
a[i][j] = a[i - d][j + d];
}
}
d *= 2;
}
for (int i = 1; i <= pow(2, m); i++) {
for (int j = 1; j <= pow(2, m); j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
1326：【例7.5】 取余运算（mod）
#include <bits/stdc++.h>
using namespace std;
int b, p, k, a;
int f(int p){
if (p == 0) return 1;
int tmp = f(p / 2) % k; //分治求b ^ p % k
tmp = (tmp * tmp) % k;
if (p % 2 == 1) tmp = (tmp * (b % k)) % k;
return tmp;
}
int main(){
cin >> b >> p >> k;
int tmpb = b;
b %= k;
cout << tmpb << "^" << p << " mod " << k << "=" << f(p) << endl;
return 0;
}
1327：【例7.6】黑白棋子的移动
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
int n, step, rt;
vector<char> a;
void print(){
printf("step%2d:",step);
for (int i = 1; i <= 2 * n + 2; i++) cout << a[i];
cout << endl;
step++;
}
//一般的移动
void mv(int k){
a[rt] = a[k];
a[rt + 1] = a[k + 1];
a[k] = '-';
a[k + 1] = '-';
rt = k;
print();
}
//特殊的移动（递归）
void move(int n){
if (n == 4){
mv(4);
mv(8);
mv(2);
mv(7);
mv(1);
} else {
mv(n);
mv(2 * n - 1);
move(n - 1);
}
}
int main(){
cin >> n;
//初始化
a.resize(n + 10);
step = 0, rt = 2 * n + 1;
for (int i = 1; i <= 2 * n + 2; i++){
if (i <= n) a[i] = 'o';
else if (i >= n + 1 && i <= 2 * n) a[i] = '*';
else a[i] = '-';
}
print();
move(n);
return 0;
}
1328：【例7.7】光荣的梦想
两个问题：
<mark>1、</mark> 查找左边界？右边界？
<mark>2、</mark> 采用哪一种排序？
大家自己好好的思考一下…
TIP：想好了看一下代码下面的解释和自己的想法是否一致
#include <iostream>
#include <vector>
using namespace std;
vector<int> a(10010), b(10010);
int ans, n;
//归并排序
void px(int l, int r){
if (l >= r) return;
int mid = (l + r) / 2;
px(l, mid);
px(mid + 1, r);
int i = l, j = mid + 1, k = 0; //k:长度
while (i <= mid && j <= r){
if (a[i] <= a[j]){
b[k++] = a[i++];
} else {
ans += mid - i + 1;
b[k++] = a[j++];
}
}
while (i <= mid){
b[k++] = a[i++];
}
while (j <= r){
b[k++] = a[j++];
}
for (int i = 0; i < k; i++){
a[l + i] = b[i];
}
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
px(1, n);
cout << ans << endl;
return 0;
}
这段代码实现的是<mark>归并排序</mark>，并在排序的过程中统计逆序对的数量。逆序对是指在一个数组中，如果存在两个元素 a[i] 和 a[j]，且满足 i < j 但是 a[i] > a[j]，则这两个元素构成一个逆序对。
在归并排序的过程中，当合并两个有序子数组时，如果发现右边数组中的某个元素 a[j] 小于左边数组中的某个元素 a[i]，那么说明右边数组中从 j 到 mid 这段范围内的元素与 a[i] 构成了逆序对，其中 mid 是左边数组的最后一个元素下标。
因此，这段代码是<mark>统计右边界的逆序对数量</mark>。
1234：2011
<mark>快速幂</mark>解决！！！
2 10 = 2 5 * 2 5 = ?
2 5 = 2 2 * 2 2 * 2 = ?
2 2 = 2 1 * 2 1 = 4
2 1 = 2 * 2 0 = 2
数太大怎么办？
注意分<mark>指数的奇偶</mark>！
2 10 = 2 5 * 2 5 = 1024 1024 % 10000
2 5 = 2 2 * 2 2 * 2 = 32 32 % 10000
2 2 = 2 1 * 2 1 = 4 4 % 10000
2 1 = 2 * 2 0 = 2 2 % 10000
#include <iostream>
#include <vector>
using namespace std;
vector<int> a;
int fun(int k) {
if (k == 0) return 1;
else if (k % 2 == 1) return fun(k - 1) * 2011 % 10000;
else {
int num = fun(k / 2) % 10000;
return num * num % 10000;
}
}
int main() {
int t, n, m;
cin >> t;
while (t--) {
a.clear();
string input;
cin >> input;
for (char c : input) {
a.push_back(c - '0');
}
n = a.size();
m = a[n - 1];
if (n >= 2) m += a[n - 2] * 10;
if (n >= 3) m += a[n - 3] * 100;
if (n >= 4) m += a[n - 4] * 1000;
cout << fun(m) << endl;
}
return 0;
}
1235：输出前k大的数
第一种：
使用了选择排序的思想，每次在未排序的部分中找到最大的元素，并将其放置在已排序部分的末尾。这样，只需要对前k个元素进行排序，而不必对整个数组进行排序
#include <iostream>
#include <vector>
using namespace std;
vector<int> a;
int main() {
int n, k;
cin >> n;
a.resize(n + 1); // 调整数组大小，因为原始代码中数组索引从1开始
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> k;
// 使用堆排序找到前k大的元素
for (int i = 1; i <= k; i++) {
int max_index = i;
for (int j = i + 1; j <= n; j++) {
if (a[j] > a[max_index]) {
max_index = j;
}
}
swap(a[i], a[max_index]);
}
// 输出前k大的元素
for (int i = 1; i <= k; i++) {
cout << a[i] << endl;
}
return 0;
}
不过，我发现了，以上的方***超时，所以我又想出了下面这种方法：
第二种：（用了STL模板库中的partial_sort函数）
使用了 algorithm 头文件中的partial_sort函数，它能够高效地找到前k大的元素，而无需对整个数组进行排序。greater()比较器确保降序排列。这个改变应该提高了代码的效率，有助于通过时间限制。
#include <iostream>
#include <vector>
#include <algorithm> // 为了使用 partial_sort
using namespace std;
vector<int> a;
int main() {
int n, k;
cin >> n;
a.resize(n + 1); // 调整数组大小，因为原始代码中数组索引从1开始
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> k;
// 使用 partial_sort 找到前k大的元素
partial_sort(a.begin() + 1, a.begin() + k + 1, a.begin() + n + 1, greater<int>());
// 输出前k大的元素
for (int i = 1; i <= k; i++) {
cout << a[i] << endl;
}
return 0;
}
不过，我尝试了之后，发现还是超时了三个测试点：
上面对三个，下面错三个，我真的崩溃啦！ 经过 （≈）210分钟后，我想出来了最后的办法：
基本上就是使用快排（quicksort）来解决，然后把cin和cout改成scanf和printf
#include <cstdio>
#include <vector>
using namespace std;
int n, m;
vector<int> a(100001);
void qs(vector<int>& a, int left, int right){
int i = left, j = right, tmp; //tmp：临时变量
int mid = a[(left + right) / 2];
while (i <= j){
while (a[i] > mid) i++;
while (a[j] < mid) j--;
if (i <= j){
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
if (left < j) qs(a, left, j);
if (i < right) qs(a, i, right);
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
qs(a, 1, n);
for (int i = 1; i <= m; i++){
printf("%d\n", a[i]);
}
return 0;
}
老铁，终于可以了！
1236：区间合并
注意：如果你用的是vector,那么sort排序时要把node + 1, node + n + 1改成<mark>node.begin()</mark> 和 <mark>node.end()</mark>！！！
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
int s, e;
int vis;
};
bool cmp(const Node& a, const Node& b) {
return a.s < b.s;
}
int main() {
int n;
cin >> n;
vector<Node> node(n);
for (int i = 0; i < n; i++) {
cin >> node[i].s >> node[i].e;
node[i].vis = 0;
}
sort(node.begin(), node.end(), cmp);
// 合并重叠区间
for (int i = 0; i < n - 1; i++) {
if (node[i + 1].s <= node[i].e) {
node[i + 1].s = node[i].s;
node[i + 1].e = max(node[i].e, node[i + 1].e);
node[i].vis = 1;
}
}
for (int i = 0; i < n - 1; i++) {
if (node[i].vis == 0) {
cout << "no" << endl;
return 0;
}
}
cout << node[n - 1].s << " " << node[n - 1].e << endl;
return 0;
}
1237：求排列的逆序数
2 6 3 4 5 1
一个一个比？冒泡排序？
实际上冒泡排序也是可以解的，但是本章是分治，所以采用<mark>分治</mark>的方法！！！
2 6 | 3 | 4 5 | 1 （二分——归并排序）
合并，逆序， 换数…
1、读入
2、归并排序 → 分左右
3、输出逆序
#include <iostream>
#include <vector>
using namespace std;
vector<int> a(100010), e(100010);
long long ans; // 使用 long long 类型来存储逆序数
void mer(int l, int r){
int m, i, j, k;
if (l == r) return; // 如果左指针和右指针在一起
m = (l + r) / 2;
mer(l, m);
mer(m + 1, r);
i = l;
j = m + 1;
k = l;
while (i <= m && j <= r){
if (a[i] <= a[j]){
e[k] = a[i];
i++;
k++;
} else {
ans += m - i + 1; // 更新逆序数
e[k] = a[j];
j++;
k++;
}
}
// 如果有剩余的
while (i <= m) {
e[k] = a[i];
i++;
k++;
}
while (j <= r){
e[k] = a[j];
j++;
k++;
}
for (int i = l; i <= r; i++){
a[i] = e[i];
}
}
int main(){
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// 归并排序
mer(1, n);
cout << ans << endl;
return 0;
}
1238：一元三次方程求解
这道题我是借鉴某谷中的题解从而写的
num用来记录解的个数 因为一元三次方程只有三个解 解达到三个以后就break掉 减少多余循环
#include <iostream>
#include <iomanip> //setprecision会用到
#include <vector>
using namespace std;
double a, b, c, d, a1, b1, c1, d1;
int num;
int main()
{
cin >> a >> b >> c >> d;
for(double i = -100.00; i <= 100.00; i += 0.001)
{
double l = i, r = i + 0.001;
if ((a * l * l * l + b * l * l + c * l + d) * (a * r * r * r + b * r * r + c * r + d) < 0)
{
cout << fixed << setprecision(2) << l << " ";
num++;
}
if(num==3) break;
}
return 0;
}
小提示：这段代码也可以解决 P1024 [NOIP2001 提高组] 一元三次方程求解 哦！
1239：统计数字
对于这道题目，我第一个想到的排序是快排！
#include <iostream>
#include <vector>
using namespace std;
vector<int> a(10010);
// 快排
void qsort(int l, int r) {
if (l >= r) return; // 结束递归的条件
int i = l, j = r, mid = a[(l + r) / 2];
while (i <= j) {
while (a[i] < mid) i++;
while (a[j] > mid) j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
qsort(l, j);
qsort(i, r);
}
int main() {
int n, ans = 1;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
qsort(1, n);
for (int i = 1; i <= n; i++) {
if (a[i] == a[i + 1])
ans++;
else {
cout << a[i] << " " << ans << endl;
ans = 1; // 一定要归位
}
}
return 0;
}
结果错了…
最后改正了一下（还看了一下不能用STL，不过也没太大关系）：
#include <iostream>
using namespace std;
int a[200001];
void qsort(int l, int r) {
// 快排
int i = l, j = r, mid = a[(l + r) / 2];
while (i <= j) {
while (a[i] < mid) i++;
while (a[j] > mid) j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
if (l < j) qsort(l, j);
if (i < r) qsort(i, r);
}
int main() {
int n, s = 1;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
qsort(1, n); // 从小到大快排
for (int i = 1; i <= n; i++) {
if (a[i] == a[i + 1] && i < n)
s++; // 统计相同数字出现次数
else {
cout << a[i] << " " << s << endl;
s = 1;
}
}
return 0;
}
AC了！！！！！
1240：查找最接近的元素
这道题比较简单，就不做介绍了，直接上AC代码：
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int n, m, x, l, r, mid;
vector<int> a(100001);
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
while (m--){
cin >> x;
l = 1;
r = n;
while (l < r - 1){
//二分
mid = (l + r) / 2;
if (a[mid] > x) r = mid;
else l = mid;
}
if (abs(a[l] - x) <= abs(a[r] - x)) cout << a[l] << endl;
else cout << a[r] << endl;
}
return 0;
}
1241：二分法求函数的零点
这不就是提交答案题吗?!
不过我还是写了代码：
#include <iostream>
#include <iomanip>
using namespace std;
double fun(double x){
//模拟式子
return x * x * x * x * x - 15.0 * x * x * x * x + 85.0 * x * x * x - 225.0 * x * x + 274.0 * x - 121.0;
}
int main(){
double l = 1.5, r = 2.4;
while (l < r - 0.000001){
//二分
double mid = (l + r) / 2.0;
if (fun(mid) > 0.0) l = mid;
if (fun(mid) < 0.0) r = mid;
}
if (fun(l) == 0.0) cout << fixed << setprecision(6) << l << endl;
else cout << fixed << setprecision(6) << r << endl;
return 0;
}
1242：网线主管
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
vector<int> a(10001);
int n, m, maxn;
bool check (int mid){
int sum = 0;
for (int i = 1; i <= n; i++) sum += a[i] / mid;
return sum >= m;
}
int main(){
double x;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> x;
a[i] = x * 100;
maxn = max(maxn, a[i]);
}
int l, r, mid;
l = 1, r = maxn;
while (l <= r){
mid = l + (r - l) / 2;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << fixed << setprecision(2) << (double)r / 100.0 << endl;
return 0;
}
1243：月度开销
<mark>TIP：如果一个题目有像下面这样子的提示 / 样例说明之类的框，一定要仔细去模拟！</mark>
注意：<mark>mid = (l + r) / 2;</mark> 这里要调整一下：<mark>mid = l + (r - l) / 2;</mark>，不然不能通过！！！
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> a(100005);
bool check(int mid){
int sum = 0, cnt = 1;
for (int i = 1; i <= n; i++){
if (a[i] > mid) return false;
if (sum + a[i] <= mid)
{
sum += a[i];
}
else {
sum = a[i];
cnt++;
}
}
if (cnt <= m) return true;
else return false;
}
int main(){
int sum = 0, maxn = -1, l, r, mid, ans;
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
maxn = max(maxn, a[i]);
}
l = maxn, r = sum;
while (l < r){
mid = l + (r - l) / 2;
if (check(mid))
{
ans = mid;
r = mid;
}else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}
1244：和为给定数
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> a(100001);
int main() {
long long n, m;
cin >> n;
for (long long i = 0; i < n; i++) cin >> a[i];
cin >> m;
sort(a.begin(), a.begin() + n); // 只对前n个元素进行排序
long long i = 0, j = n - 1;
while (i < j) {
if (a[i] + a[j] == m) {
cout << a[i] << " " << a[j] << endl;
return 0;
} else if (a[i] + a[j] < m) {
i++;
} else {
j--;
}
}
cout << "No" << endl;
return 0;
}
1245：不重复地输出数
悄悄告诉你们，这道题可以用set！！！因为是不重复地输出数！！！set可以去重！！！用了set，这道题就变简单了！！！
#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
//set会自动排序且去重
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << " ";
}
return 0;
}
1246：膨胀的木棍
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
const double PI = acos(-1);
using namespace std;
double l, c, n, l1;
double fun(double a)
{
return l * a / (2 * sin(a / 2));
}
int main()
{
cin >> l >> n >> c;
l1 = (1 + n * c) * l;
double l = 0, r = PI, mid;
while(r - l >= 1e-12)
{
mid = (l + r) / 2;
if(fun(mid) < l1) l = mid;
else r = mid;
}
cout << fixed << setprecision(3) << l1 / mid * (1 - cos(mid / 2));
return 0;
}
1247：河中跳房子
↓该说的都在注释里面了↓
//采取策略：贪心 + 二分(求右边界)
#include <iostream>
#include <vector>
using namespace std;
const int N = 50100;
vector<int> a(N);
int l, n, m;
bool check(int mid){
int c = 0, p = 0;
for (int i = 1; i <= n; i++){
if (a[i] - p < mid) c++;
else p = a[i];
}
if (l - p < mid) c++;
return c <= m;
}
int main(){
cin >> l >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
int left = 1, right = l, mid;
while (left <= right){
mid = left + (right - left) / 2;
//如果最短跳跃距离为mid的情况下，搬走的石块数量 <= m，放大距离
if (check(mid)) left = mid + 1;
else right = mid - 1;
}
cout << left - 1 << endl; //右边界
return 0;
}
京公网安备 11010502036488号