小鲸鱼的梦境
0%

『洛谷』分治

发表于 更新于 分类于 ， Valine：
本文字数： 10k 阅读时长 ≈ 9 分钟

基础算法-分治

分治，即分而治之，将大问题分解为小问题，分别求解，最后合并结果。

P1226 【模板】快速幂||取余运算

题目描述

给你三个整数 \(a,b,p\)，求 \(a^b \bmod p\)。

输入格式

输入只有一行三个整数，分别代表 \(a,b,p\)。

输出格式

输出一行一个字符串 a^b mod p=s，其中 \(a,b,p\) 分别为题目给定的值， \(s\) 为运算结果。

样例 #1

样例输入 #1

1
2 10 9

样例输出 #1

1
2^10 mod 9=7

提示

样例解释

\(2^{10} = 1024\)，\(1024 \bmod 9 = 7\)。

数据规模与约定

对于 \(100\%\) 的数据，保证 \(0\le a,b < 2^{31}\)，\(a+b>0\)，\(2 \leq p \lt 2^{31}\)。

解题思路

模板题没什么好解释的，不确定的话可以把数据拉到极限测试一下 2147483647.

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
using namespace std;
#define ll long long
ll qmod(ll a, ll b, ll p) {
    // 快速幂 (a^b)%p
    ll ans = 1;
    for (ll cnt = a; b != 0ll; b >>= 1) {
        if ((b & 1) == 1) ans = (ans * cnt) % p;
        cnt = (cnt * cnt) % p;
    }
    return ans;
}

int main() {
    ll a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%lld^%lld mod %lld=%lld", a, b, p, qmod(a, b, p));
    return 0;
}

P1010 [NOIP1998 普及组] 幂次方

题目描述

任何一个正整数都可以用 \(2\) 的幂次方表示。例如 $137=27+23+2^0 $。

同时约定方次用括号来表示，即 \(a^b\) 可表示为 \(a(b)\)。

由此可知，\(137\) 可表示为 \(2(7)+2(3)+2(0)\)

进一步：

\(7= 2^2+2+2^0\) ( \(2^1\) 用 \(2\) 表示)，并且 \(3=2+2^0\)。

所以最后 \(137\) 可表示为 \(2(2(2)+2+2(0))+2(2+2(0))+2(0)\)。

又如 \(1315=2^{10} +2^8 +2^5 +2+1\)

所以 \(1315\) 最后可表示为 \(2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)\)。

输入格式

一行一个正整数 \(n\)。

输出格式

符合约定的 \(n\) 的 \(0, 2\) 表示（在表示中不能有空格）。

样例 #1

样例输入 #1

1
1315

样例输出 #1

1
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示

【数据范围】

对于 \(100\%\) 的数据，\(1 \le n \le 2 \times {10}^4\)。

解题思路

任何一个正整数都可以用 \(2\) 的幂次方表示，不难理解，因为这句话和“任何一个正整数都能用二进制表示”是完全等价的，所以不难推出对应的表达式，至于剩下的，递归即可。

不理解第一句话的可以将数字全部转为二进制表示看看：

\(137(1000\,1001)=2^7(1000\,0000)+2^3(1000)+2^0(1)\).

\(7, 3, 0\) 都是二进制表示中 \(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
#include <cstring>
#include <sstream>
#include <iostream>
using namespace std;

string get(int n) {
    stringstream ss;
    bool plus = false;
    for (int i = 30; i > 1; --i) {
        int x = 1 << i;
        if ((n & x) != 0) {
            if (plus) ss << "+";
            ss << "2(" << get(i) << ')';
            plus = true;
        }
    }
    if ((n & 2) != 0) {
        if (plus) ss << "+";
        ss << 2;
        plus = true;
    }
    if ((n & 1) != 0) {
        if (plus) ss << "+";
        ss << "2(0)";
    }
    return ss.str();
}


int main() {
    int n;
    cin >> n;
    cout << get(n);
    return 0;
}

P1257 平面上的最接近点对

题目描述

给定平面上 \(n\) 个点，找出其中的一对点的距离，使得在这 \(n\) 个点的所有点对中，该距离为所有点对中最小的。

输入格式

第一行一个整数 \(n\)，表示点的个数。

接下来 \(n\) 行，每行两个实数 \(x,y\) ，表示一个点的行坐标和列坐标。

输出格式

仅一行，一个实数，表示最短距离，四舍五入保留 \(4\) 位小数。

样例 #1

样例输入 #1

1
2
3
4
3
1 1
1 2
2 2

样例输出 #1

1
1.0000

提示

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^4\)，\(0 \leq x, y \leq 10^9\)，小数点后的数字个数不超过 \(6\)。

解题思路

其实接下来两题是一样的，只不过数据范围不同，这题范围暴力两两枚举即可

解答代码

时间复杂度 \(O(n^2)\).

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
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

void redir() {
    std::ios::sync_with_stdio(false);
//    std::cin.tie(0);
//    std::cout.tie(0);
//    freopen("luogu.in", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

const int N = 10007;
double x[N], y[N];

double pow(double x) {return x * x;}

int main() {

    redir();

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lf%lf", &x[i], &y[i]);
    }
    double ans = pow(x[0] - x[1]) + pow(y[0] - y[1]);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ans = min(ans, pow(x[i] - x[j]) + pow(y[i] - y[j]));
        }
    }
    printf("%.4lf", sqrt(ans));
    return 0;
}

P1429 平面最近点对（加强版）

题目背景

P7883 平面最近点对（加强加强版）

题目描述

给定平面上 \(n\) 个点，找出其中的一对点的距离，使得在这 \(n\) 个点的所有点对中，该距离为所有点对中最小的

输入格式

第一行：\(n\) ，保证 \(2\le n\le 200000\) 。(注：\(2e5\))

接下来 \(n\) 行：每行两个实数：\(x\ y\) ，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式

仅一行，一个实数，表示最短距离，精确到小数点后面 \(4\) 位。

样例 #1

样例输入 #1

1
2
3
4
3
1 1
1 2
2 2

样例输出 #1

1
1.0000

提示

数据保证 \(0\le x,y\le 10^9\)

解题思路

其实平面最近点对是数据结构和算法教科书上经典的分治算法例题了，先排序，然后一分为二，然后结果有三种可能

  • 最近两点都在左边
  • 最近两点都在右边
  • 最近两点一个在左一个在右

前两种情况递归可解，麻烦的是第三种情况，解决方法是划分条带

我们假设划分的两个区间是 \([a, b], [b, c] \; (a < b < c)\), 且前两种情况的最优解为 \(s\)，那么如果第三种情况比 \(s\) 更优，那么第三种情况的两个点横坐标应该在 \([b - s, b + s]\) 的范围内，纵坐标同理，可以证明该方法最坏情况下复杂度为 \(O(n)\)，不过如果每次都排序的话需要 \(O(n \log n)\) 最后总的时间复杂度为 \(O(n \log^2 n)\), 不过可以预处理出分别按 \(x, y\) 排序（或者对 \(y\) 的排序使用归并，那么每次内部排序都是 \(O(n)\)）的结果，此时总时间复杂度为 \(O(n \log n)\).

取巧了，正确做法看下一题加强加强版。

解答代码

暴力的时间复杂度 \(O(n^2)\), 能拿 55 分

一个取巧的写法，可以 100 分

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

void redir() {
    std::ios::sync_with_stdio(false);
//    std::cin.tie(0);
//    std::cout.tie(0);
    // freopen("luogu.in", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

const int N = 200007;
double x[N], y[N];
int sx[N], sy[N];

inline double pow(double x) {return x * x;}

double dist(int x1, int x2) {
    return sqrt(pow(x[x1] - x[x2]) + pow(y[x1] - y[x2]));
}

bool comp_x(int a, int b) {
    return x[a] < x[b];
}

bool comp_y(int a, int b) {
    return y[a] < y[b];
}

int main() {

    redir();

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lf%lf", &x[i], &y[i]);
        sx[i] = i; sy[i] = i;
    }
    sort(sx, sx + n, comp_x);
    sort(sy, sy + n, comp_y);
    double ans = dist(0, 1);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (x[sx[j]] - x[sx[i]] >= ans) break;
            ans = min(ans, dist(sx[i], sx[j]));
        }
        for (int j = i + 1; j < n; ++j) {
            if (y[sy[j]] - y[sy[i]] >= ans) break;
            ans = min(ans, dist(sy[i], sy[j]));
        }
    }
    printf("%.4lf", ans);
    return 0;
}

P7883 平面最近点对（加强加强版）

题目背景

P1429 平面最近点对（加强版）里最高赞题解写道：

我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 \(x\) 坐标排序
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 \(5\) 个点来计算答案
这样速度快得飞起，在 \(n=1000000\) 时都可以在 1 s 内卡过

当然，这是错的。

题目描述

给定 \(n\) 个二维欧几里得平面上的点 \(p_1, p_2, \dots, p_n\)，请输出距离最近的两个点的距离。

输入格式

输入第一行为一个正整数 \(n\)，表示点数。

接下来 \(n\) 行，第 \(i\) 行为用空格隔开的整数 \(x_i, y_i\)，表示 \(p_i = (x_i, y_i)\)。

输入保证：没有两个坐标完全相同的点。

输出格式

输出一行，包含一个整数 \(D^2\)，表示距离最近的两个点的距离的平方。

由于输入的点为整点，因此这个值一定是整数。

样例 #1

样例输入 #1

1
2
3
2
-10000000 -10000000
10000000 10000000

样例输出 #1

1
800000000000000

样例 #2

样例输入 #2

1
2
3
4
5
6
5
1 1
1 9
9 1
9 9
0 10

样例输出 #2

1
2

提示

对于第二组样例，\((1, 9)\)、\((0, 10)\) 两个点最近，距离为 \(\sqrt 2\)，因此你需要输出 \(2\)。

数据范围

对于 \(100 \%\) 的数据，\(2 \leq n \leq 4 \times 10^5\)，\(-10^7 \leq x_i, y_i \leq 10^7\)。

本题目标复杂度是 \(O(n \log ^2 n)\)。设置 350ms 时限的原因是：

  1. \(O(n \log ^2 n)\) 参考代码使用 cin 不会 TLE。最快的 std 能 \(<\) 100ms。
  2. @wlzhouzhuan 的程序能恰好在 350ms 内跑 \(1000n\) 次检查。
  3. 150 组测试数据，为了防止卡评测。

解题思路

看本文上一题的解题思路，是一样的

解答代码

上一题取巧的代码，这题还能拿 120 分

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

void redir() {
    std::ios::sync_with_stdio(false);
//    std::cin.tie(0);
//    std::cout.tie(0);
    // freopen("luogu.in", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

#define ll long long
const int N = 400007;
ll x[N], y[N];
int sx[N];

inline ll pow(ll x) {return x * x;}

ll dist(int x1, int x2) {
    return pow(x[x1] - x[x2]) + pow(y[x1] - y[x2]);
}

bool comp_x(int a, int b) {
    return x[a] < x[b];
}

int main() {

    redir();

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld%lld", &x[i], &y[i]);
        sx[i] = i; //sy[i] = i;
    }
    sort(sx, sx + n, comp_x);
    ll ans = dist(0, 1);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (pow(x[sx[j]] - x[sx[i]]) >= ans) break;
            ans = min(ans, dist(sx[i], sx[j]));
        }
    }
    printf("%lld", ans);
    return 0;
}

分治法：已经全部通过 150 个用例，但还有优化点 => 对 y 排序使用归并可以保证严格 \(O(nlogn)\). (PS: 建议去本题评论区看看“人类智慧”的好些做法🤣)

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 400007;
struct Point {
    ll x, y;
} p[N];
int n, temp[N];
ll INF = 1ll << 60;

void get_data() {
    scanf("%lld", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld%lld", &p[i].x, &p[i].y);
    }
}

bool comp_x(const Point &a, const Point &b) {
    return a.x < b.x;
}

bool comp_y(const int &a, const int &b) {
    return p[a].y < p[b].y;
}

ll sqrt(int a) {
    ll b = a;
    return b * b;
}

ll dist(int a, int b) {
    // 计算两点间的距离
    int dx = p[a].x - p[b].x, dy = p[a].y - p[b].y;
    return sqrt(dx) + sqrt(dy);
}

ll min_point(int left, int right) {
    // 计算 [left, right] 范围内最近两点距离
    if (left == right) return INF;
    if (left + 1 == right) return dist(left, right);
    int mid = left + right >> 1;
    ll d = min(min_point(left, mid), min_point(mid + 1, right));
    // 借助临时数组储存符合要求的点的下标
    int k = 0;
    for (int i = left; i <= right; ++i) {
        if (sqrt(p[i].x - p[mid].x) <= d) temp[k++] = i;
    }
    sort(temp, temp + k, comp_y);
    // 暴力计算两点间最近距离
    for (int i = 0; i < k; ++i) {
        for (int j = i + 1; j < k && sqrt(p[temp[j]].y - p[temp[i]].y) < d; ++j) {
            ll td = dist(temp[i], temp[j]);
            if (td < d) d = td;
        }
    }
    return d;
}

int main() {

    get_data();

    sort(p, p + n, comp_x);

    printf("%lld", min_point(0, n - 1));

    return 0;
}

P3612 [USACO17JAN]Secret Cow Code S

题面翻译

奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。

给定一个字符串，让后面的字符旋转一次（每一次正确的旋转，最后一个字符都会成为新的第一个字符）。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。

给定初始字符串和索引，请帮助奶牛计算无限字符串中位置 \(N\) 的字符。

第一行输入一个字符串。该字符串包含最多 \(30\) 个大写字母，数据保证 \(N \leq 10^{18}\) 。

第二行输入 \(N\)。请注意，数据可能很大，放进一个标准的 \(32\) 位整数可能不够，所以你可能要使用一个 \(64\) 位的整数类型（例如，在 C/C++ 中是 long long）。

请输出从初始字符串生成的无限字符串中的位置的字符。第一个字符是 \(N=1\).。

感谢@y_z_h 的翻译

题目描述

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string \(s\), let \(F(s)\) be \(s\) followed by \(s\) "rotated" one character to the right (in a right rotation, the last character of \(s\) rotates around and becomes the new first character). Given an initial string \(s\), the cows build their infinite-length code string by repeatedly applying \(F\); each step therefore doubles the length of the current string.

Given the initial string and an index \(N\), please help the cows compute the character at the \(N\)th position within the infinite code string.

输入格式

The input consists of a single line containing a string followed by \(N\). The string consists of at most 30 uppercase characters, and \(N \leq 10^{18}\).

Note that \(N\) may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a "long long" in C/C++).

输出格式

Please output the \(N\)th character of the infinite code built from the initial string. The first character is \(N=1\).

样例 #1

样例输入 #1

1
COW 8

样例输出 #1

1
C

提示

In this example, the initial string COW expands as follows:

COW -> COWWCO -> COW WCO OCO WWC

12345678

解题思路

每一次旋转字符串都会变长一倍，可以推导以下需要旋转几次，然后再逆向推导回去是原字符串的第几个字母

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

long long n;
string s;

int main() {

    cin >> s >> n;
    // 顺推字符串的长度
    long long b = s.size(), t = b;
    while (t < n) t *= 2;
    // 逆推在原字符串位置
    while (n > b) {
        // 如果在字符串的右半部分，就要推导其在左半部分的位置
        if (n > t / 2) if (--n > t / 2) n -= t / 2;
        t /= 2; // 下一轮字符串长度
    }

    cout << s[n - 1];
    return 0;
}
--- ♥ end ♥ ---

欢迎关注我呀~