中英企业网站,该网站正在紧急升级维护中,淘宝官网首页版本,监控设备东莞网站建设Build Roads
题意:
n个点#xff0c;每个点的值为a[i],求最小生成树 a[i]是通过题目中给出的程序得到#xff08;即a[i]如何得到的我们并不需要很了解#xff09;
题解#xff1a;
肯定不能直接跑最小生成树#xff0c;因为数据太大了 银川也有个类似的题#xff0c;…Build Roads
题意:
n个点每个点的值为a[i],求最小生成树 a[i]是通过题目中给出的程序得到即a[i]如何得到的我们并不需要很了解
题解
肯定不能直接跑最小生成树因为数据太大了 银川也有个类似的题比赛时我直接打表发现当n很大时答案就是n-1通过我大量枚举我得到结论当n1000时我们就直接套结论当小于1000时就跑遍最小生成树 但是忘了一种情况导致一直wa题目给的L和R表示的是a[i]的范围如果L R时n很大说明每个点的值都是L那么gcd求出边长都是L,所以答案就是(n-1)*L 挺可惜比赛时一直没想到最后这一小点
代码
//蒟蒻三人行
#includebits/stdc.h
#includemap
#define random(a,b) ((a)rand()%((b-a1)))
typedef long long ll;
using namespace std;
const int maxn1e79;
int n,L,R,a[200001];
int tot0;
unsigned long long seed;
unsigned long long xorshift64()
{unsigned long long xseed;x^x13;x^x7;x^x17;return seedx;
}
int gen(){return xorshift64()%(R-L1)L;
}
int gcd(int a,int b)
{if(b)return gcd(b,a%b);return a;
}
int fa[maxn];
struct node{int u,v,w;
}edge[maxn];
bool cmp(node a,node b)
{return a.wb.w;
}
int find(int x)
{if(fa[x]-1)return x;else return fa[x]find(fa[x]);
}
ll kruskal(int n)
{memset(fa,-1,sizeof(fa));sort(edge1,edge1tot,cmp);int cnt0;ll ans0;//couttotendl;for(int i1;itot;i){int uedge[i].u;int vedge[i].v;int wedge[i].w;int fufind(u);int fvfind(v);if(fu!fv){answ;fa[fu]fv;cnt;}//coutn cntendl;if(cntn-1){//coutcntendl;break;}}//couttotendl;return ans;
}
void add(int u,int v,int w)
{edge[tot].uu;edge[tot].vv;edge[tot].ww;
}
int main()
{
// coutgcd(4,6);//srand(time(0));//int t1000;
// while(t--)// nrandom(1,100000);// Lrandom(1,19999);// Rrandom(L,200000);// seed(unsigned long long)random(1,10000000000000); scanf(%d%d%d%llu,n,L,R,seed);// printf(生成数据%d %d %d %llu\n,n,L,R,seed);memset(edge,0,sizeof(node));memset(a,0,sizeof(int));for(int i1;in;i){a[i]gen();//printf(a[%d]%d\n,i,a[i]);//2464638799566668449} tot0;if(LR){cout1ll*(n-1)*Lendl;return 0;} if(n1000){cout(n-1)endl;return 0;}for(int i1;in;i){//printf(a[%d]%d\n,i,a[i]);for(int ji1;jn;j){int wgcd(a[i],a[j]);// printf(i%d j%d w%d\n,i,j,w);// printf(w%d\n,w);add(i,j,w);add(j,i,w);}}//couttotendl;// coutedge[1].w;int wwkruskal(n);coutwwendl;
// if(ww!n-1)
// {
// cout错误endl;
// //printf(最终%d %d %d %llu\n,n,L,R,seed);
// //cout答案 wwendl;
//
// }
// else cout正确endl;//cout答案 wwendl;return 0;
}/*
50000 16199 18966 29398
*/
