首页 > 代码库 > hihoCoder挑战赛4 光棍节
hihoCoder挑战赛4 光棍节
题目3 : 光棍节
时间限制:30000ms
单点时限:1000ms
内存限制:256MB
描述
尽管付出了种种努力，jzp还是得过光棍节。
jzp非常不爽，但也无能为力，只能够哀叹起来他的命运。他想到了一位长者的人生经验：“人的一生，不光要靠自我奋斗，也要考虑历史的进程”。
他终于明白自己只是时运不济，所以又继续开始努力。终于在圣诞节当天把到了妹子。
jzp从此过上了快乐的现充生活，在圣诞节当天，他还和妹子玩起了有趣的游戏：
jzp的家里有一棵非常大的圣诞树，可以看成是一个n个点的无向联通无环图。每个点上都有一个正整数，JZP和妹子每次都会选择树上的一条路径，
这条路径的权值被定义为路径上所有点上数的最大公约数，JZP可以得到这个权值的分数。
JZP玩了一会儿有点腻了，他想知道对于每种可能的权值x，权值为x的不同路径的数量（a到b的路径和b到a的路径算作一种，a到a自身也算作一条路径。）
输入
第一行一个整数n(1<=n<=105)表示圣诞树的大小，点从1开始标号。
接下来一行n个整数用单个空格隔开，第i个表示第i个点上的数。（数都在1到105之间）。
接下来n-1行，每行两个数a和b，表示a和b之间有一条边。
输出
令C(x)表示权值为x的路径的个数。
从小到大输出对于所有C(x)>0的x，输出一行两个数x和C(x)，用空格隔开。
- 样例输入
202 4 2 4 2 4 2 20 20 12 12 12 2 12 2 4 4 2 12 21 21 31 42 53 61 76 82 96 105 114 1211 1310 143 159 167 174 184 1916 20
- 样例输出
2 1864 1612 620 2
思路：一看就是树分治的题，可是想想都会T 啊，可是实在没事可以做，所以只有去暴力了，加了一些优化，
交了wa，改了改，还是wa 。。。。 后面把优化全部去掉，终于T了，好像很兴奋的样子
后面看了代码，发现一个地方错了，可是只有几分钟了。。。。
改了交，然后有把优化加上，又交了一发。
然后结束了，心里想又挂0 了。。。
后面没加优化的过了。。。。。==
最后一分钟过的。。不容易呀
View Code#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define ll long long#define INF 0x3f3f3f3f#define maxn 200010#define eps 1e-6#define mod 1000000007using namespace std;int head[maxn] , to[maxn*2] ,next1[maxn*2] ;int top ,cnt[maxn] , f[maxn];int k ,ans ,n ;vector<int>vec;bool vi[maxn] ;void Unit(int x,int y){ to[top]=y;next1[top]=head[x] ; head[x]=top++;}void find1( int u ,int fa ){ f[u] = 0 ; cnt[u] = 1 ; int v ; for( int i = head[u] ; i != -1; i = next1[i]) { v = to[i] ; if(v==fa||vi[v]) continue ; find1(v,u) ; cnt[u] += cnt[v] ; f[u] = max(cnt[v],f[u]) ; }}int minn ;void find_root1( int u ,int fa,int &root,int sum){ int tmp = max(sum-cnt[u],f[u]) ; if(tmp < minn) { minn = tmp ; root = u ; } int v; for( int i = head[u] ; i != -1; i = next1[i]) { v = to[i] ; if(v==fa||vi[v]) continue ; find_root1(v,u,root,sum) ; }}int get_root( int u ){ find1(u,-1) ; int sum = cnt[u] ; int root = u ; minn = n ; find_root1(u,-1,root,sum) ; return root ;}int ret ,MAX,num[maxn],val[maxn] ;LL c[maxn];int gcd(int a,int b){ int c; while(b) { c = a%b ; a = b ; b = c ; } return a ;}int num1,num2;vector<int>q;void find(int d){ int x,n=q.size(); for(int i =0 ; i < n ;i++) { x = gcd(q[i],d) ; c[x] += num[q[i]] ; }}void dfs1(int u ,int fa,int root,int d ){ vec.push_back(d); c[d]++; /* if(d==1)c[1] += num1 ; else if(d==2) c[2] += num2 ;*/ find(d) ; int j,v ; for( int i = head[u] ; i != -1 ; i = next1[i]) { v = to[i] ; if(vi[v]||v==fa) continue ; dfs1(v,u,1,gcd(d,val[v])) ; }}int que[maxn],l;void count( int u ){ int j,v ; l=0; num1=num2=0; q.clear(); for( int i = head[u] ; i != -1 ; i = next1[i]) { v = to[i] ; if(vi[v]) continue ; vec.clear() ; dfs1(v,u,-1,gcd(val[u],val[v])); for( j = 0 ; j < vec.size();j++){ if(num[vec[j]]==0)q.push_back(vec[j]); num[vec[j]]++ ; num1++; if(vec[j]&1){} else num2++; que[l++]=vec[j]; } } for( int i = 0 ; i < l ;i++) num[que[i]] = 0;}void solve( int u ){ int root = get_root(u) ; vi[root] = 1 ; count(root) ; int v ; for( int i = head[root] ; i != -1 ; i = next1[i]) { v = to[i] ; if(vi[v]) continue ; solve(v) ; }}int main(){ int i , m ,k , j ; int x,y; while(scanf("%d",&n) != EOF) { MAX=0; memset(c,0,sizeof(c)) ; memset(num,0,sizeof(num)); for( i = 1 ; i <= n ;i++){ scanf("%d",&val[i]) ; c[val[i]]++; MAX=max(MAX,val[i]) ; } memset(head,-1,sizeof(head)) ; memset(vi,0,sizeof(vi)); top=0; for(i = 1 ; i < n ;i++) { scanf("%d%d",&x,&y) ; Unit(x,y) ; Unit(y,x) ; } solve(1) ; for( i =1 ; i <= MAX;i++)if(c[i]>0) { cout<<i<<" "<<c[i]<<endl; } } return 0 ;}
hihoCoder挑战赛4 光棍节
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。