做网站嘉兴wordpress插件ERP
题目大意和普通做法
省选模拟测试23 T1直径
题解
对于上文中有三个儿子的根节点的树，其直径数量为ab+bc+caab+bc+caab+bc+ca。那么对于上文中有nnn个儿子的根节点的树，其直径数量为多少呢？
每个儿子所在子树中的点与其他儿子所在子树中的点都能组成一次直径，而两个点都能组成一次直径，所以要除以2。设第iii个儿子的儿子数量为aia_iai，则直径数量为
(∑ai)2−∑ai22\dfrac{(\sum a_i)^2-\sum a_i^2}{2}2(∑ai)2−∑ai2
要让k=(∑ai)2−∑ai22k=\dfrac{(\sum a_i)^2-\sum a_i^2}{2}k=2(∑ai)2−∑ai2，即2k=(∑ai)2−∑ai22k=(\sum a_i)^2-\sum a_i^22k=(∑ai)2−∑ai2。
根据题意，1+∑(ai+1)≤1051+\sum (a_i+1)\leq 10^51+∑(ai+1)≤105，于是我们可以枚举∑ai\sum a_i∑ai。
令所有的ai=1a_i=1ai=1，那么最多能有n×n−nn\times n-nn×n−n条直径。5000×5000−5000>50000005000\times 5000-5000>50000005000×5000−5000>5000000，这些对于题目来说是绰绰有余的了。
枚举找到第一个v=∑aiv=\sum a_iv=∑ai，使得v∗v−v≥2kv*v-v\geq 2kv∗v−v≥2k。
对于多出的部分，我们可以将若干个aia_iai组合起来，达到减少更多的效果。
比如，将两个值为1的aia_iai合并为一个值为2的aia_iai，原来减少贡献为12+12=21^2+1^2=212+12=2，现在贡献为22=42^2=422=4，增加了222。
当然，如果合并三个或更多，则减少的也会更多。找到一种方法，使其减少到正好为2k2k2k即可。
code
#include<bits/stdc++.h>
using namespace std;
int n,v,now,hv,tot=0,w,vt,a[5005];
struct node{int x,y,z;
}ans[5005];
int main()
{scanf("%d",&n);for(int i=1;i<=5000;i++){if(i*i-i>=n*2){v=i;break;}}now=v*v-v-n*2;hv=v;for(int i=v;i>=2;i--){while(now>=i*i-i&&hv>=i){now-=i*i-i;hv-=i;a[++w]=i;}}for(int i=1;i<=w+hv;i++){ans[++vt]=(node){1,i+1,10000+(i>w)};}tot=w+hv+1;for(int i=1;i<=w;i++){for(int j=1;j<=a[i];j++){ans[++vt]=(node){i+1,++tot,1};}}printf("%d\n",tot);for(int i=1;i<=vt;i++){printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].z);}return 0;
}