【BZOJ】2152: 聪聪可可 点分治

2024-09-05 14:32
文章标签 分治 bzoj 可可 聪聪 2152

本文主要是介绍【BZOJ】2152: 聪聪可可 点分治,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:【BZOJ】2152: 聪聪可可


题目分析:记录权值和%3的路径的个数。。。然后去重。。没了。。


代码如下:


#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;
const int MAXE = 200005 ;struct Edge {int v , c , n ;Edge () {}Edge ( int v , int c , int n ) : v ( v ) , c ( c ) , n ( n ) {}
} ;Edge E[MAXE] ;
int H[MAXN] , cntE ;
int dis[MAXN] ;
int vis[MAXN] , Time ;
int pre[MAXN] ;
int siz[MAXN] ;
int dp[MAXN] ;
int d[3] ;
int Q[MAXN] , head , tail ;
int ans ;
int n ;void clear () {cntE = 0 ;clr ( H , -1 ) ;Time ++ ;ans = 0 ;
}void addedge ( int u , int v , int c ) {E[cntE] = Edge ( v , c , H[u] ) ;H[u] = cntE ++ ;
}int gcd ( int a , int b ) {return b ? gcd ( b , a % b ) : a ;
}int get_root ( int s ) {head = tail = 0 ;Q[tail ++] = s ;pre[s] = 0 ;while ( head != tail ) {int u = Q[head ++] ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( v != pre[u] && vis[v] != Time ) {pre[v] = u ;Q[tail ++] = v ;}}}int tot_size = tail ;int root = s , max_size = tail ;while ( tail ) {int u = Q[-- tail] ;siz[u] = 1 ;int cnt = 0 ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( v != pre[u] && vis[v] != Time ) {siz[u] += siz[v] ;cnt = max ( cnt , siz[v] ) ;}}cnt = max ( cnt , tot_size - siz[u] ) ;if ( cnt < max_size ) {max_size = cnt ;root = u ;}}return root ;
}int get_ans ( int s , int init_dis ) {head = tail = 0 ;Q[tail ++] = s ;pre[s] = 0 ;dis[s] = init_dis % 3 ;d[0] = d[1] = d[2] = 0 ;while ( head != tail ) {int u = Q[head ++] ;d[dis[u]] ++ ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( v != pre[u] && vis[v] != Time ) {pre[v] = u ;Q[tail ++] = v ;dis[v] = ( dis[u] + E[i].c ) % 3 ;}}}return d[1] * d[2] * 2 + d[0] * d[0] ;
}void divide ( int u ) {int root = get_root ( u ) ;vis[root] = Time ;ans += get_ans ( root , 0 ) ;for ( int i = H[root] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( vis[v] != Time ) {ans -= get_ans ( v , E[i].c ) ;divide ( v ) ;}}vis[root] = 0 ;
}void scanf ( int& x , char c = 0 ) {while ( ( c = getchar () ) < '0' || c > '9' ) ;x = c - '0' ;while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}void solve () {int u , v , c ;clear () ;rep ( i , 1 , n ) {scanf ( u ) ;scanf ( v ) ;scanf ( c ) ;addedge ( u , v , c % 3 ) ;addedge ( v , u , c % 3 ) ;}divide ( 1 ) ;//printf ( "%lld %lld\n" , ans , ( LL ) n * n ) ;int __gcd = gcd ( n * n , ans ) ;printf ( "%d/%d\n" , ans / __gcd , n * n / __gcd ) ;
}int main () {clr ( vis , 0 ) ;Time = 0 ;while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}


这篇关于【BZOJ】2152: 聪聪可可 点分治的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139222

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

分治算法与凸包问题

1. 什么是凸包问题? 凸包问题是计算几何中的经典问题。给定二维平面上的点集,凸包是一个最小的凸多边形,它包含了点集中所有的点。你可以把凸包想象成一根松紧带将所有点紧紧包裹住的样子,凸包的边缘仅沿着最外面的点延伸。 2. 分治法简介 分治算法是解决复杂问题的强大策略,它的思想是将问题分解为多个子问题,分别解决这些子问题后再合并得到最终解。凸包问题可以通过分治算法高效地解决,时间复杂度可以达到

【COGS】577 蝗灾 cdq分治

传送门:【COGS】577 蝗灾 题目分析:cdq分治入门题= =。。。。用差分思想将矩阵分成四块来计算。。排序一维,另一维用树状数组解决。 代码如下: #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP(

【BZOJ】1324 Exca王者之剑 最大权独立集

传送门:【BZOJ】1324  Exca王者之剑 题目分析:赤裸裸的最大权独立集。。。最小割解决 代码如下: #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP( i , a , b ) for ( int

【ACdream】1157 Segments cdq分治

传送门:【ACdream】1157 Segments 题目分析:第一题cdq(陈丹琦)分治!cdq_____Orz! 听说cdq分治可以写,就去学了cdq分治了。。 在我们平常使用的分治中,每一个子问题只解决它本身(可以说是封闭的)。 而在cdq分治中,对于划分出来的两个子问题,前一个子问题用来解决后一个子问题而不是它本身。 具体算法流程如下: 1.将整个操作序列分为两个长

【HDU】4871 Shortest-path tree 最短路+点分治

传送门:【HDU】4871 Shortest-path tree 题目分析: 学了点分治后来看这道题,简直就是水题。。。 但是我竟然花了将近一个晚上才写出来。。。就因为一个地方写漏了T U T。。 首先根据题意求一棵树,最短路一下,然后最小字典序就按照编号顺序遍历邻接表给节点标记。 剩下的就是树分治的事了。 在以重心X为根的子树中,按照X的子节点v的子树中最长路径包含节点数升序遍

【HDU】4812 D Tree 点分治

传送门:【HDU】4812 D Tree 题目分析:点分治搞之。乘积等于K的路径。 首先我们定义一个path[ i ]用以记录从根结点x在子树x内的第 i 条路径的值(乘积)。然后每次我们搞完当前重心rt的一棵子树以后,我们用判断K*逆元[ path[ i ] * val[ rt ] %MOD ] % MOD 是否存在来确定乘积为K的路径是否存在,然后再用这个path[ i ]去更

【SPOJ】1825 Free tour II 点分治

传送门:【SPOJ】1825 Free tour II 题目分析:敲了两遍。。。 本题是论文题,具体见漆子超论文《分治算法在树的路径问题中的应用》。 在以root为根的第 i 棵子树上,我们用G[ i ,j ]表示root的第 i 棵子树的路径上严格有 j 个黑点的路径的最长长度。用F[ i ,j ]表示在root为根的第 i 棵子树的路径上不超过 j 个黑点的路径的最长长度。因

【BZOJ】1026: [SCOI2009]windy数 数位DP

传送门:【BZOJ】1026: [SCOI2009]windy数 题目分析:数位DP水题。 代码如下: #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,