hdu5329(2015多校4)–Question for the Leader
分类：——–数据结构——–树的乱搞题目
题目链接：点击打开链接
题目大意：给出一个图，有n条点，n条边，如果要将这个图分为相同点数的k份，要求每一份内部都可以相互链接，那么一共会有几个k符合条件。
1、有一个定理，如果一颗树要分成k个节点一份的子树，那么有n/k个节点所对应子树的节点数是k的倍数。
根据上面这个定理，那么我们就可以计算一颗树能不能被分成n/k份，题目中给出了是一棵树+一条边，所以最终应该是一个环和以环上节点为根的子树，如果环上消除一条边，那么就变成了一颗树，就可以使用定理来判断了。
首先找出环上的节点，和以节点为根的子树大小。子树中节点数是不会变得可以直接使用。但是环中的节点数是会随着删除的边而变化的，所以要枚举删除的边，找到节点数是k的倍数的节点，如果是n/k个，那么证明k是可以的。
#include <cstdio>#include <cstring>#include <cmath>#include <vector>#include <algorithm>using namespace std ;#pragma comment(linker,"/STACK:102400000,102400000") ;#define maxn 100000+10struct node{int v , next ;}edge[maxn<<1] ;int head[maxn] , h_cnt ;int vis[maxn] ;int a[maxn] , c[maxn] , n ;int s[maxn] , m ;int dp[maxn] ;int cnt[maxn] , sum[maxn] ;void add(int u,int v) {edge[h_cnt].v = v ;edge[h_cnt].next = head[u] ; head[u] = h_cnt++ ;}int f(int x) {return c[x] == x ? x : c[x] = f(c[x]) ;}int find1(int x,int y) {if( f(x) == f(y) ) return 1 ;c[ f(x) ] = f(y) ;return 0 ;}void dfs(int u) {dp[u] = 1 ;int i, v ;for(i = head[u] ; i != -1 ; i = edge[i].next) {v = edge[i].v ;if( vis[v] ) continue ;dfs(v) ;dp[u] += dp[v] ;}return ;}int solve(int k) {int i , max1 , temp = 0 ;memset(cnt,0,sizeof(cnt)) ;for(i = 1 ; i <= n ; i++) {if( vis[i] ) continue ;if( dp[i]%k == 0 ) temp++ ;}sum[0] = 0 ;for(i = 1 ; i<= m ; i++) {sum[i] = (sum[i-1] + dp[ s[i] ])%k ;cnt[ sum[i] ]++ ;}max1 = cnt[ sum[m] ] + temp ;for(i = 1 ; i < m ; i++) {cnt[ sum[i] ]– ;cnt[ (sum[m]+sum[i])%k ]++ ;max1 = max(max1,cnt[ (sum[m]+sum[i])%k ]+temp) ;}if( max1 == n/k ) return 1 ;return 0 ;}int main() {int i , j , x , k ,ans ;//freopen("1003.in","r",stdin) ;//freopen("1111.out","w",stdout) ;while( scanf("%d", &n) != EOF ) {memset(head,-1,sizeof(head)) ;h_cnt = 0 ;memset(vis,0,sizeof(vis)) ;for(i = 1 ; i <= n ; i++) {scanf("%d", &a[i]) ;add(a[i],i) ;c[i] = i ;}for(i = 1 ; i <= n ; i++) {if( find1(i,a[i]) )break ;}m = 0 ;s[ ++m ] = i ;vis[i] = 1 ;x = a[i] ;while( x != s[1] ) {s[++m] = x ;vis[x] = 1 ;x = a[x] ;}for(i = 1 ; i <= m ; i++)dfs(s[i]) ;ans = 0 ;for(k = 1 ; k <= n ; k++) {if( n%k ) continue ;ans += solve(k) ;}printf("%d\n", ans) ;}return 0 ;}/*127 9 12 2 3 4 8 6 10 5 8 1*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇hdu5338(2015多校4)–ZZX and Permutations（置换群）下一篇hdu5340–Three Palindromes（Mannacer算法）
顶0踩0
，只有他的好身体，没有地方可去，只想到处流浪、人生就像一场旅行，
