洛谷分治题单

归并排序or逆序对

在这里插入图片描述
传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;
long long ans = 0;
int a[10000000], c[10000000];
void mergesort(int a[], int left, int right)
{
	if (left >= right)
		return;
	int mid = (right + left) / 2;
	mergesort(a, left, mid);
	mergesort(a, mid + 1, right);
	int k = 0;
	int i = left, j = mid + 1;
	while (i <= mid && j <= right)
	{
		if (a[i] <= a[j])
			c[k++] = a[i++];
		else
		{
			ans = ans + mid - i + 1; //归并排序就是把这句去了
			c[k++] = a[j++];
		}
	}
	while (j <= right)
		c[k++] = a[j++];
	while (i <= mid)
		c[k++] = a[i++];
	for (i = left, j = 0; i <= right; i++, j++)
		a[i] = c[j];
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	mergesort(a, 0, n - 1);
	cout << ans;
	return 0;
}

快速幂

在这里插入图片描述
水题
传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P1226
long long fast_power(long long a, long long b, long long c)
{
    a %= c;
    long long ans = 1;
    while (b)
    {
        if (b % 2)
        {
            ans *= a;
            ans %= c;
        }
        b /= 2;
        a = a * a % c;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    long long a, b, c;
    cin >> a >> b >> c;
    printf("%lld^%lld mod %lld=%lld", a, b, c, fast_power(a, b, c));
    return 0;
}

幂次方在这里插入图片描述在这里插入图片描述

传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P1010
// 分治递归
void search(int n)
{
    if (n == 0)
        return;
    printf("2");
    int cnt = 0, tar = 1;
    while (tar <= n)
    {
        cnt++;
        tar *= 2;
    }
    int gap = n - tar / 2;
    cnt--; //出来的时候已经比n大了，应该回退一位
    if (cnt == 0 || cnt == 2)
    {
        printf("(%d)", cnt);
    }
    else if (cnt == 1)
        ; //假如是1的话，不必输出2(1)
    else if (cnt > 2)
    {
        printf("("); //递归，用同样的方式表示cnt
        search(cnt);
        printf(")");
    }
    if (gap)
    {
        printf("+");
        search(gap);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    search(n);

    return 0;
}

平面最近点对（Pro）

在这里插入图片描述
传送门
这道题的思路其实很有意思，有点像之前的归并排序的模板，它的思路很好理解，将一个点集分割，当解决1个点集时，我们将其分割为俩，将各个子集的最短距离求出，但是这样还没完！关键我们之前只分别考虑了两个点集内的最短，假如两个点集之间的点有最短咋办捏？
我们的方法是创建隔离带，我们设之前两个内点集的最短距离是minf，取点集中沿x轴方向最中间的点，以这个点为中心，左右各延拓minf的区域，讨论这段区域的点之间的最短距离！
为什么只考虑这一段呢？因为超过这个隔离带，两点的距离必然大于minf，无需考虑！
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P1429
// 分治算法
struct node
{
    double x;
    double y;
} point[100000];
double min(double a, double b) { return a < b ? a : b; }
bool cmp1(node a, node b)
{
    if (a.x != b.x)
        return a.x < b.x;
    else
        return a.y < b.y;
}
bool cmp2(node a, node b)
{
    return a.y < b.y;
}
double dis(node a, node b)
{
    double x = (a.x - b.x) * (a.x - b.x);
    double y = (a.y - b.y) * (a.y - b.y);
    return sqrt(x + y);
}
double merge(int left, int right)
{
    double minf = 0x3f3f3f3f;
    if (left >= right)
        return minf;
    if (left + 1 == right)
        return dis(point[left], point[right]);
    int mid = (left + right) >> 1;
    double min1 = merge(left, mid);
    double min2 = merge(mid + 1, right);
    minf = min(min1, min2); //两个子点集的最短
    // 关键是求跨越两个点集之间的最短可能距离
    vector<node> gap; //创建隔离带，以平行y轴的中线为界，向左右延申长度为minf的隔离带
    for (int i = left; i <= right; i++)
    {
        if (fabs(point[mid].x - point[i].x) < minf)
            gap.push_back(point[i]);
    } //有资格进入备选范围
    sort(gap.begin(), gap.end(), cmp2);
    int l = gap.size();
    for (int i = 0; i < l; i++)
    {
        double remp;
        for (int j = i + 1; j < l && gap[j].y - gap[i].y < minf; j++)
        {
            double remp;
            remp = dis(gap[i], gap[j]);
            if (minf > remp)
                minf = remp;
        }
    }
    return minf;
}
// int temp[100000];
// bool cmps(const int &a, const int &b) { return point[a].y < point[b].y; }
// double merge(int left, int right)
// {
//     double d = 2 << 20;
//     if (left == right)
//         return d;
//     if (left + 1 == right)
//         return dis(point[left], point[right]);
//     int mid = left + right >> 1;
//     double d1 = merge(left, mid);
//     double d2 = merge(mid + 1, right);
//     d = min(d1, d2);
//     int i, j, k = 0;
//     for (i = left; i <= right; i++)
//         if (fabs(point[mid].x - point[i].x) < d) // 这里不太一样
//             temp[k++] = i;
//     sort(temp, temp + k, cmps);
//     for (i = 0; i < k; i++)
//         for (j = i + 1; j < k && point[temp[j]].y - point[temp[i]].y < d; j++)
//         {
//             double d3 = dis(point[temp[i]], point[temp[j]]);
//             if (d > d3)
//                 d = d3;
//         }
//     return d;
// }
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> point[i].x >> point[i].y;
    }
    sort(point + 1, point + 1 + n, cmp1);
    printf("%.4lf", merge(1, n));
    return 0;
}

奶牛选密码

在这里插入图片描述
在这里插入图片描述
传送门
超时代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3612
// 超限了T_T
string str;
long long N;
void ans(string tar, long long l)
{
    if (l < N)
    {
        tar += tar[l - 1];
        tar += tar.substr(0, l - 1);
        // cout << tar << endl;
        ans(tar, l * 2);
    }
    else
    {
        cout << tar[N - 1];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> str >> N;
    long long l = str.length();
    ans(str, l);
    return 0;
}

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P3612
// 分治 参考题解：https://www.luogu.com.cn/blog/issue-s/solution-p3612
string str;
long long N;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> str >> N;
    long long len = str.length();
    long long l;
    while (len < N) //等效于递归，由当前串不断向前回退
    {
        l = len;
        while (l < N)
            l *= 2;
        l /= 2; //得到目标长度的一半长
        N -= (l + 1);
        if (N == 0)
            N = l;
    }
    cout << str[N - 1];
    return 0;
}

地毯填铺

在这里插入图片描述

1
2
3
样例
3                          
3 3   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
输出
5 5 1
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
6 6 1
5 8 3
8 5 2
8 8 1

传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P1228
// 递归分治
#define lu ans(x + l - 1, y + l - 1, x, y, l) //左上
#define ru ans(x + l - 1, y + l, x, y + l, l) //右上
#define ld ans(x + l, y + l - 1, x + l, y, l) //左下
#define rd ans(x + l, y + l, x + l, y + l, l) //右下
// tarx,tary是(等效)公主的位置
// x,y是正在搜索的方格的左上顶角坐标
// len是正在搜索方格的边长
void ans(long long tarx, long long tary, long long x, long long y, long long len)
{
    if (len == 1)
        return;
    int l = len / 2;
    if (tarx < l + x && tary < l + y) //公主在左上
    {
        cout << x + l << " " << y + l << " "
             << "1" << endl;
        ans(tarx, tary, x, y, l);
        ru;
        ld;
        rd;
    }
    if (tarx < l + x && tary >= l + y) //右上角
    {
        cout << x + l << " " << y + l - 1 << " "
             << "2" << endl;
        ans(tarx, tary, x, y + l, l);
        lu;
        ld;
        rd;
    }
    if (tarx >= x + l && tary < l + y) //左下角
    {
        cout << x + l - 1 << " " << y + l << " "
             << "3" << endl;
        ans(tarx, tary, x + l, y, l);
        lu;
        ru;
        rd;
    }
    if (tarx >= x + l && tary >= l + y) //右下角
    {
        cout << x + l - 1 << " " << y + l - 1 << " "
             << "4" << endl;
        ans(tarx, tary, x + l, y + l, l);
        lu;
        ru;
        ld;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    long long k, tarx, tary;
    cin >> k >> tarx >> tary;
    ans(tarx, tary, 1, 1, pow(2, k));
    return 0;
}