算法日常练习6

2021年11月11日练习。

平面上最近点对问题

给定平面上\(n\)个点及其横纵坐标（保证横纵坐标都是 long long 范围内的整数），求这\(n\)个点中距离最小的一对点，要求输出最小距离，保留三位小数。

最直接的想法当然是暴力枚举。

#include <bits/stdc++.h>
#define square(x) ((x)*(x))
using namespace std;
using ll = long long;
int main() {
	int n;
	cin >> n;
	vector<vector<ll>> points(n, vector<int>(2));
	for (int i = 0; i < n; i++) {
		cin >> points[i][0] >> points[i][1];
	}
	double ans = 0.0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ans = max(ans, sqrt(square(points[i][0] - points[j][0]) + square(points[i][1] - points[j][1])));
		}
	}
	cout << setiosflags(ios::fixed) << setprecision(3);
	cout << ans << endl;
	return 0;
}

但是当点的数量太多的时候，暴力枚举会超时，所以需要进行求解的优化。

对于本题来讲可以采用分治的策略。那么什么是分治策略呢？

事实上，二分查找就是分治策略的一种应用。要在排序好的数组中查找目标值，先取中间值，然后根据情况取左、右区间中的一个进行查找。当数组较大时，数组中的很大一部分空间并没有被遍历，因此二分查找确实是将时间复杂度降低了（由\(O(n)\)到\(O(logn)\)）。

但是分治策略对于有些问题是无效的，例如矩阵乘法问题，矩阵进行分块后再相乘并没有减少乘法的次数。使用分治策略求解平面上最近点对的问题可以降低时间复杂度吗？

答案是可以。分治策略中很关键的一点是如何降低从小规模问题的解构成大规模问题的解的时间复杂度。对于矩阵乘法问题，不论如何划分，”合“的过程的复杂度是无法降低的。现证明分治策略对于求平面最近点对的距离问题有效，参考资料见文末。

图1 证明分治策略有效

如图1，设\(\delta_L\)和\(\delta_R\)分别是对平面的左右部分求出来的最小距离，取\(\delta = min(\delta_L,\delta_R)\)。考虑划分位置\(L\)左右\(\delta\)范围内的点，首先可以证明如果平面左右部分中各取一点，若所求得的距离\(d \leq \delta\)，那么这两点一定在虚线的区域，这是很显然的。然后证明，对于左侧任意一个点\(P_1\)，它若与右侧中的一点\(P_2 \in Right\)满足\(distance(P_1,P_2) \leq \delta\)，那么\(Right\)中的点一定在\(\delta * 2\delta\)的一个矩形内，如图2所示，这个同样是显然的。

图2 核心部分证明

图2所示的矩形部分之多有6个点。即将这个举行划分为6个\(\frac {2\delta}{3} * \frac {\delta}{2}\)的矩形，由鸽巢原理，若点的个数大于6，则这6个矩形中至少有一个中有超过2个点，而每个矩形中2个点最远的距离是\(\sqrt{\left(\frac{2\delta}{3}\right)^2 + \left(\frac{\delta}{2}\right)^2}=\frac{5\delta}{6}<\delta\)，而这是刚刚求解过的右半部分，显然这是不成立的，因此原假设不真。这也就证明了在进行局部解到整体解的合并的过程中需要枚举的点大大减少，时间复杂度确实降低了。

由这样的思路最终得出如下的代码。

#include <bits/stdc++.h>
#define square(x) ((x)*(x))
#define MAX_SIZE 200050

using db = double;
using ll = long long;
using namespace std;

int n;

struct point { 
    ll x, y; 
};

vector<point>input;

bool cmp1(point u, point v) { 
    return u.x == v.x ? u.y < v.y : u.x < v.x; 
}

bool cmp2(point u, point v) { 
    return u.y < v.y; 
}

db distance(point u, point v) { 
    return square(u.x - v.x) + square(u.y - v.y); 
}

db sol(int l, int r)
{
    if (l >= r) {
        return LLONG_MAX;
    }
    else if (r == l + 1) {
        return distance(input[l], input[r]);
    }
    else {
        int mid = (l + r) >> 1, midx = input[mid].x;
        db d = min(sol(l, mid), sol(mid + 1, r));
        vector<point> left_right;
        for (int i = l; i < r; i++) { 
            if (square(input[i].x - midx) <= d) {
                left_right.emplace_back(input[i]);
            }
        }
        int ct = left_right.size();
        sort(left_right.begin(), left_right.end(), cmp2);
        for (int i = 0; i < ct; i++) {
            for(int j = i + 1; j < ct; j++){
                if (square(left_right[i].y - left_right[j].y) > d) {
                    break;
                }
                d = min(d, distance(left_right[i],left_right[j]));
            }
        }
        return d;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    input.resize(n);
    for (int i = 0; i < n; i++) { 
        cin >> input[i].x >> input[i].y; 
    }
    sort(input.begin(), input.end(), cmp1);
    cout << setiosflags(ios::fixed) << setprecision(3);
    cout << sqrt(sol(0, n - 1)) << endl;
    return 0;
}

生日纪念日

输入某个人的生日，他想知道自己的一万天纪念日是哪一天。输入为三个整数，分别为年、月、日并且保证日期绝对合法，输出格式为 年-月-日 。

最暴力的想法就是直接写一个日期的类，自加\(10^4\)次。

#include <bits/stdc++.h>
using namespace std;
int days_in_months[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
struct date {
	int YY;
	int MM;
	int DD;
	void operator++(int){
		DD++;
		if (DD > days_in_months[MM]) {
			MM++;
			DD = 1;
			if (MM > 12) {
				YY++;
				MM = 1;
			}
		}
	}
};

bool leap_year(int YY) {
	return ((YY % 4 == 0 && YY % 100 !=0) || (YY % 400 == 0));
}

int main() {
	date t;
	cin >> t.YY >> t.MM >> t.DD;
	for (int i = 1; i <= 10000; i++) {
		if (leap_year(t.YY)) {
			days_in_months[2] = 29;
		}
		else {
			days_in_months[2] = 28;
		}
		t++;
	}
	cout << t.YY << '-' << t.MM << '-' << t.DD << endl;
	return 0;
}

然而，当天数过大时时间复杂度会爆掉，因此优化代码如下。

#include <iostream>
using namespace std;

int days_in_month[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int y) {
    return (y % 400 == 0) || (y % 100 != 0 && y % 4 == 0);
}

//格式化输出
void display(int y, int m, int d) {
    if(y < 10) cout << "000";
    else if(y < 100) cout << "00";
    else if(y < 1000) cout << 0;
    cout << y << '-';
    if(m < 10) cout << 0;
    cout << m << '-';
    if(d < 10) cout << 0;
    cout << d << endl;
}

int main() {
	//数据组数
    int t;
    cin >> t;
	//年，月，日及增加的天数
    int y, m, d, inc;
    while(t--) {
        cin >> y >> m >> d >> inc;
        d += inc;
        while(1) {
            if(isLeap(y)) days_in_month[2] = 29;
            else days_in_month[2] = 28;
            if(d <= days_in_month[m]) break;
            d -= days_in_month[m];
            if(++m > 12) m = 1, y++;
        }
        display(y, m, d);
    }
    return 0;
}

事实上，还可以使用ctime库来做。

#include <bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;

int main() {
	struct tm d, * nd;
	int year, month, day;

	cin >> year >> month >> day;
	d.tm_year = year - 1900; //tm_year等于实际年份减去1900 
	d.tm_mon = month - 1; //tm_mon中0代表一月
	d.tm_mday = day;//tm_mday取值范围是[1,31]
	d.tm_hour = 0;
	d.tm_min = 0;
	d.tm_sec = 0;

	time_t tt = mktime(&d) + 10000 * 24 * 60 * 60;//将时间转换为自1970年1月1日以来持续时间的秒数，发生错误时返回-1
	nd = gmtime(&tt);//返回tm结构的格林尼治时间

	cout << nd->tm_year + 1900 << '-' << nd->tm_mon + 1 << '-' << nd->tm_mday << endl;
	return 0;
}

清帝之惑之乾隆

实际上就是高精度计算问题，只不过输出有各种的坑。

#include <bits/stdc++.h>
using namespace std;
class big_int {
private:
	vector<int> num;
public:
	big_int(unsigned int _init) :num(vector<int>()) {
		while (_init) {
			num.emplace_back(_init % 10);
			_init /= 10;
		}
	}
	big_int(const string& _init):num(vector<int>()) {
		int n = _init.size();
		for (int i = _init.size() - 1; i >= 0; i--) {
			num.emplace_back(_init[i] - '0');
		}
	}
	big_int(const big_int & ano):num(ano.num) {}
	big_int(const vector<int>& ano) :num(ano) {}
	int operator[](size_t idx) {
		if (idx >= num.size()) {
			exit(-1);
		}
		else {
			return num[idx];
		}
	}
	big_int operator*(const big_int& ano) const{
		int n = num.size(), m = ano.num.size();
		vector<int> ans(m + n, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				ans[i + j] += num[i] * ano.num[j];
			}
		}
		for (int i = m + n - 1; i >= 0; i--) {
			if (ans[i] == 0) {
				ans.pop_back();
			}
			else {
				break;
			}
		}
		int c = 0;
		for (size_t i = 0; i < ans.size(); i++) {
			ans[i] += c;
			c = ans[i] / 10;
			ans[i] %= 10;
		}
		if (c > 0) {
			ans.emplace_back(c);
		}
		return big_int(ans);
	}
	big_int pow(int n) const{
		big_int ans(1);
		for (int i = 1; i <= n; i++) {
			ans = ans * num;
		}
		return ans;
	}
	const size_t size() const{
		return num.size();
	}
};

int main() {
	string R, processed_R;
	int n;
	size_t dot_pos = 0;
	while (cin >> R >> n) {
		processed_R.clear();
		for (int i = R.size() - 1; i >= 0; i--) {
			if (R[i] == '0') {
				R.pop_back();
			}
			else {
				break;
			}
		}
		for (size_t i = 0; i < R.size(); i++) {
			if (R[i] != '.') {
				processed_R.push_back(R[i]);
			}
			else {
				dot_pos = i;
			}
		}
		big_int ans = big_int(processed_R).pow(n);
		dot_pos = n * (R.size() - dot_pos - 1);
		if (dot_pos >= ans.size()) {
			cout << '.';
			for (int i = dot_pos - 1; i >= 0; i--) {
				if (i >= ans.size()) {
					cout << 0;
				}
				else {
					cout << ans[i];
				}
			}
		}
		else{
			for (int i = ans.size() - 1; i >= 0; i--) {
				if (i == dot_pos) {
					cout << ans[i];
					if (i != 0) {
						cout << '.';
					}
				}
				else {
					cout << ans[i];
				}
			}
		}
		cout << endl;
	}
	return 0;
}

最小非负值

输入一个自然数\(n(n< 10^{1000})\)，表示\(1\)到\(n\)共\(n\)个自然数排成一列，你要在每一个数前添上 + 或 - ,要使得添加符号后这个代数式的值最小且非负。

任意四个连续的自然数我们都可以让其和为\(0\)，因此题设要求的数列其实是一个周期数列。

#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	int a;
	if (s.length() == 1) {
		a = s[0] - '0';
	}
	else {
		a = (s[s.length() - 1] - '0') * 10 + s[s.length() - 2] - '0';
	}
	if (a % 4 == 1 || a % 4 == 2) {
		cout << 1 << endl;
	}
	else {
		cout << 0 << endl;
	}
	return 0;
}

求二叉树的先序序列

已知中序和后序序列，求先序序列，数据结构基本题目。

#include<bits/stdc++.h>
using namespace std;
string in_order, post_order;
void pre_order(int in_order_left, int in_order_right, int post_order_left, int post_order_right){
    if (in_order_left == in_order_right) {
        return;
    }
    int cur_root = -1;
    for (int i = 0; i < in_order_right; i++) {
        if (in_order[i] == post_order[post_order_right - 1]) {
            cur_root = i;//中序遍历序列里根的位置
            cout << in_order[cur_root];
            break;
        }
    }
    pre_order(in_order_left, cur_root, post_order_left, post_order_left + cur_root - in_order_left);
    pre_order(cur_root + 1, in_order_right, post_order_left + cur_root - in_order_left, post_order_right - 1);
}

int main(){
    cin >> in_order >> post_order;
    pre_order(0, in_order.size(), 0, post_order.size());
    return 0;
}

最小差距

给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。例如：给定\(6\)个数字为\(\{0,1,2,4,6,7\}\)，你可以用它们组成一对数\(10\)和\(2467\)，当然，还可以组成其他的很多对数，\(204\)和\(176\)。这些对数中两个数差的绝对值最小的是\(204\)和\(176\)，为\(28\)。那么给定\(N\)个不同的\(0\)~\(9\)之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？

输入包括\((2T+1)\)行，第一行包括一个数 \(T(T≤1000)\)，为测试数据的组数；接下来每组数据包括两行，第一行为一个数\(N(2≤N≤10)\)，表示数字的个数。下面一行为\(N\)个不同的一位数字。

一道贪心算法的题目，分奇数和偶数两种情况进行讨论即可。

#include<bits/stdc++.h>
using namespace std;

int minDiff(vector<int>& nums) {
	int n = nums.size();
	if (nums.size() == 2) {
		return nums[1] - nums[0];
	}
	else {
		if (n % 2 == 0) {
			int last = (nums[0] == 0 ? nums[2] - nums[1] : nums[1] - nums[0]);
			int ans = INT_MAX;
			for (int i = (nums[0] == 0 ? 2 : 1); i < n; i++) {
				if (nums[i] - nums[i - 1] <= last) {//进行枚举
					last = nums[i] - nums[i - 1];
					int big = nums[i], small = nums[i - 1];
					vector<bool> visited(n, false);
					visited[i] = visited[i - 1] = true;
					int r = n / 2 - 1;
					int j = n - 1;
					while (r) {
						if (!visited[j]) {
							small = small * 10 + nums[j];
							r--;
							visited[j] = true;
						}
						j--;
					}
					for (j = 0; j < n; j++) {
						if (!visited[j]) {
							big = big * 10 + nums[j];
						}
					}
					ans = min(ans, big - small);
				}
			}
			return ans;
		}
		else {
			int big = (nums[0] == 0 ? nums[1] : nums[0]), small = 0;
			vector<bool> visited(n, false);
			visited[nums[0] == 0 ? 1 : 0] = true;
			int r = (n - 1) / 2;
			int j = 0;
			while (r) {
				if (!visited[j]) {
					r--;
					visited[j] = true;
					big = big * 10 + nums[j];
				}
				j++;
			}
			for (j = n - 1; j >= 0; j--) {
				if (!visited[j]) {
					small = small * 10 + nums[j];
				}
			}
			return big - small;
		}
	}
}

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int N;
		cin >> N;
		vector<int> nums(N);
		for (auto& i : nums) {
			cin >> i;
		}
		sort(nums.begin(), nums.end(), less<int>());
		cout << minDiff(nums) << endl;
	}
	return 0;
}

密码破解

已知数列数列\(12345678910111213...\)，输入是一个数\(n\)，表示求数列的第\(n\)位。

核心为：\(i\)位数共有\(9*10^{i-1}\)个。

#include<bits/stdc++.h>
using ll = long long;
using namespace std;

int main() {
	int n;
	cin >> n;
	if (n <= 9) {
		cout << n << endl;
		return 0;
	}
	else {
		ll left = 1, right = 10, base = 9;//base不是10
		int digit = 2;
		for (int i = 2; i <= 10; i++) {
			base *= 10;
			left = right;
			right = left + base * i;
			if (left <= n && n < right) {
				digit = i;
				break;
			}
		}
		int num = base / 10 + (n - left) / digit;
		int c = (n - left) / digit + 1;
		int k = (digit - 1) - (n - (left + (c - 1) * digit));
		if (k == 0) {
			k = digit - 1;
		}
		while (k) {
			num /= 10;
			k--;
		}
		cout << num % 10 << endl;
	}
	return 0;
}

参考资料

求平面内最近点对