标签:算法-分治

题意给出两组点,求两组点间的最近点对。每个组中点数 $N\le 1000$ ,坐标 $x,y\le 10^9$ 。题解按 $x$ 坐标分治,并且对分别属于左右块的点对单独处理。注意数组需要开两倍。#include<bits/stdc++.h> #define ll long long using namespace std; inline ll read() { c...
题解 算法-分治
昨天做了,为了抢夜宵就没写自己做了半天,感觉及其恶心,就去看了题解,发现了一种及其巧妙的写法。这种写法的原理就是按照2的整数幂次将一共 $2^{n}$ 行分成 $n$ 组来操作,操作就是把之前的图形左右各复制一个即可,只是要注意要在前后加上空格。int n,m; string ans[1100]; inline void work(int x) { int mx=x*2; ...
题解 算法-分治
普及/提高-
NOIp才考了(好吧是我把它做成了)分治,再加上我分治也不太熟悉,就先做下分治。虽然是一道普及-,但细节还是廷考验人的,再加上很久没打题了所以搞了很久。思路就是找到原数所能分出的最大的2的整数幂次方,然后将幂次数和剩下的分治处理即可。细节就是2(2(0))应该直接写成2int n; void work(int x) { if (x==0) { printf(...
题解 算法-分治
普及-