UOJ#283. 直径拆除鸡
题意：
题目传送门
题解：
只能说是好妙的一个构造啊……（开花金字塔这名字真形象……）
考虑删除掉一条长度为\(d\)的直径之后，最长的直径是\((\lfloor \frac{d}{2} \rfloor - 1) * 2\)。这个还是比较容易证明的，发现由于这个式子中有一个下取整的部分，所以当直径为偶数的时候，利用率是最高的。这是其中的一个结论。
然后另一个容易得出的结论就是，当一个联通块删除直径之后被分成两个联通块时，每个点产生的贡献相比于一个联通块的时候会减小，所以我们希望删除直径之后，不会产生新的联通块。
那么我们就可以构造出这样的一个开花金字塔：先构造出一些长度为\(1, 3, 5, \dots\)的链，然后把这些链的中点连起来，这样每次删除的一定是按初始构造的链由大到小地删除的，而每次删除之后不会产生新的联通块。对于那些剩余的点，我们就加在长度为\(3\)的链的中点上。
考虑这样是否是最优的情况，我们构造出的链并不是越多越好，构造出的过长的链，有些时候长度为\(3\)的链上能够产生更多的贡献，所以这个答案函数大概是一个凸的函数，发现\(n\)并不大，于是我们枚举构造出多少条链，如果当前答案大于\(m\)就输出即可。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 50;
typedef pair<int, int> P;
#define fi first
#define se second
#define mk make_pair
typedef vector<P> VecP;
int n, m;
VecP Ans;
int Calc(int len) {
int tmp = n, res = 0;
for(int i = len; i >= 3; i -= 2) res += tmp, tmp -= i;
res += tmp;
return res;
}
void Out(int len) {
int nw = 0, lasmd = -1;
for(int i = len; i >= 3; i -= 2) {
int st = ++nw, las = st, md;
for(int j = 2; j <= i; j++) {
Ans.push_back( mk(las, ++nw) );
las = nw;
if(j == (i + 1) / 2) md = nw;
}
if(~lasmd) Ans.push_back( mk(lasmd, md));
lasmd = md;
}
while(nw < n) {
Ans.push_back( mk(++nw, lasmd) );
}
for(int i = 0; i < (int) Ans.size(); i++) printf("%d %d\n", Ans[i].fi, Ans[i].se);
exit(0);
}
int main() {
scanf("%d%d", &n, &m);
if(n == 1) return 0;
if(n == 2) return puts("1 2"), 0;
if(n == 3) return puts("1 2"), puts("2 3"), 0;
int up = floor( sqrt(n * 4) ) - 1;
for(int i = 3; i <= up; i += 2) {
if(Calc(i) >= m) Out(i);
}
assert(0);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10725595.html
相关资源：JAVA上百实例源码以及开源项目
