wordpress建站吗,wordpress年会员,百度信息流,移动版wordpress打的很顺的一场
复盘
7:40 开题#xff0c;看到题目名很interesting
T1 看起来很典#xff0c;中位数显然考虑二分#xff0c;然后就是最大子段和#xff1b;T2 构造#xff1f;一看数据范围这么小#xff0c;感觉不是很难做#xff1b;T3 神秘数据结构#xff1b;T…打的很顺的一场
复盘
7:40 开题看到题目名很interesting
T1 看起来很典中位数显然考虑二分然后就是最大子段和T2 构造一看数据范围这么小感觉不是很难做T3 神秘数据结构T4 看到数据范围这不是我们广义串并联图吗不过感觉应该有别的做法
7:50 开写T1 很快过了大样例感觉不是很能挂
8:00 看 T2显然有 2 n m 2^{nm} 2nm 的暴搜然后先枚举行每一列的值就定了然后就是个背包显然折半搜索。没什么细节8:40 交了
看 T3删除操作显然倒过来变成加边 2 2 2 操作显然是问是否在一个边双里可以先把最终状态下边双缩点然后开始手玩发现加一条边可以看作把树上两点间路径缩成一个点这个过程有点抽象啊
上个厕所冷静一下发现这个其实是能做的直接从两端点暴力往上跳每次合并给当前点的父亲改编号的操作可以启发式来维护。这样就有 O ( n log n n α ( n ) ) O(n\log nn\alpha (n)) O(nlognnα(n)) 的做法了 8 × 1 0 5 8\times 10^5 8×105 应该不会卡 log \log log 吧
9:10 开写了写完了困难的 tarjan 后猛然意识到图不连通发现这就有点难做了合并两棵树是不好做的树的形态不固定没法找 LCA
再冷静一会其实我可以把这些树边都保留下来应该不影响答案太对了啊
过程中发现启发式根本没必要并查集直接维护即可
写写写到最后一步 两个点往上跳 先写了个暴力的做法验了验有没有写挂发现确实挂了
改过后发现满数据竟然只跑 2.4 s 2.4s 2.4s可是我这最坏复杂度 n 2 n^2 n2
还是改成复杂度正确的做法了交了此时 10:10
本地大样例跑 2.1 s 2.1s 2.1s不是吧我都没 log \log log 了还这么慢考虑卡常
加上了手写快读本地变成 1.3 s 1.3s 1.3s 了可是时限 1 s 1s 1s
尝试输出运行时间发现光读入就用了 0.6 s 0.6s 0.6s 于是立刻申请超级快读
拿到了超级快读的我发现读入只用 0.06 s 0.06s 0.06s跑大样例只用 0.7 s 0.7s 0.7s
此时 10:30开 T4
发现很唐的 B ( n ) B(n) B(n) 做法给了 50pts然后是树上似乎也不是很难
很快写完了暴搜发现 B ( n ) B(n) B(n) 不仅能跑过 n 12 n12 n12 n 13 , 14 n13,14 n13,14 也可以
于是启发我们广义串并联图缩完点后直接暴力发现可以获得比树的做法多整整 10pts 的好成绩
中间又去想了想正解怎么做类似毒瘤那个题大概两个方向要么就是广义串并联图但缩完点后的暴力得优化一下要么考虑生成树然后加边
前者想了很久到最后最快只能得到 3 n 3^n 3n 的做法后者往容斥去想发现信息根本没法维护就算按 dfs 序全是返祖边感觉也记录不了
决定写更简单的树显然直接 d p dp dp11:40 交了
剩下 20min 写广义串并联也写不完了就又想了想正解怎么做无果
结果是
100 100 100 70 370
差点挂分
看了赛时提交T2 同一个做法用 scanf 的得了 60用 read 的得了 90用 超级快读 的得了 100逆
发现 T3 其实没必要写 tarjan直接建最终的那棵最大生成树然后正常的去缩环就行。( 没事复习了 tarjan 显然不亏啊
T4 还是没想到正解啊最后还是有点理不清哪些信息是重要的需要维护的
题解
T3 T4 n ≤ 12 n\leq 12 n≤12注意要用集合划分的方式去搜不会 TLE
从树上做法和暴力我们可以拓展
考虑往树上加边不妨认为加的都是返祖边(后来发现这个没什么用)那么该边的权值与相连两个点的颜色有关
设 N m − n 1 Nm-n1 Nm−n1发现这样的点只有 2 N 2N 2N 个也就是说我们关注颜色的点只有这么多剩下的可以在 dp 里算贡献
那么考虑对于这 2 N 2N 2N 个点集合划分接下来效仿树上做法设状态 f i , c f_{i,c} fi,c 表示 i i i 为 c c c 颜色时子树地贡献特别地若 c 0 c0 c0代表 i i i 的颜色与划分出的集合都不相同
转移小分讨一下。对于这 2 N 2N 2N 个点的限制实际上只需把 f f f 数组的初值特殊赋即可
这个做法的复杂度加上前缀和优化就是 B ( 2 N ) N n B(2N)Nn B(2N)Nn
进一步优化是否真的需要 2 N 2N 2N 个点的颜色信息呢其实不用对于每条边只要有一个点的颜色枚举即可另一个点可以在 d p dp dp 到这个点时根据颜色直接算贡献乘到答案里
就 ok 了
int n , m , K ;
struct nn
{int x , y , A , B ;
}e[N] ;
LL ksm( LL a , LL b )
{LL res 1 , t a % mod ;while( b ) {if( b1 ) res res * t % mod ;b b 1 ;t t * t % mod ;}return res ;
}
namespace subtask1
{const int N1 15 ;int w[N1] ;LL ans , g[N] ;void calc( int cnt ){LL res g[cnt] ;for(int i 1 ; i m ; i ) {if( w[e[i].x]!w[e[i].y] ) res res * e[i].A % mod ;else res res * e[i].B % mod ;}ans ( ans res ) % mod ;}void dfs( int x , int nw ){if( x n1 ) {calc(nw) ;return ;}// 新开w[x] nw1 ;dfs( x1 , nw1 ) ;// for(int i 1 ; i nw ; i ) {w[x] i ;dfs(x1,nw) ;}}void solve(){g[0] 1 ;ans 0 ;for(int i 1 ; i n ; i ) g[i] g[i-1]*(K-i1)%mod ;dfs(1,0) ;printf(%lld\n , ans ) ;}
}
struct edg
{int lst , to , id ;
}E[2*N] ;
int head[N] , tot 1 ;
inline void add( int x , int y , int id )
{E[tot] (edg){head[x],y,id} ;head[x] tot ;
}
namespace subtask2
{const int M 5010 ;LL f[N][M] , Sum[N] ;void dfs( int x , int fa ){for(int i 1 ; i K ; i ) f[x][i] 1 ;Sum[x] 0 ;for(int i head[x] ; i ; i E[i].lst ) {int t E[i].to ;if( t fa ) continue ;dfs( t , x ) ;for(int j 1 ; j K ; j ) {f[x][j] f[x][j] * (((Sum[t]-f[t][j])*e[E[i].id].Af[t][j]*e[E[i].id].B)%mod) % mod ;}}for(int i 1 ; i K ; i ) Sum[x] ( Sum[x] f[x][i] ) % mod ;}void solve(){for(int i 1 ; i m ; i ) {add( e[i].x , e[i].y , i ) ;add( e[i].y , e[i].x , i ) ;}dfs( 1 , 0 ) ;printf(%lld\n , (Sum[1]mod)%mod ) ;tot 0 ;memset( head , 0 , sizeof head ) ;}
}
namespace subtask3
{// emmm 似乎并不依赖返祖边的性质 const int M 15 ;int dfn[N] , tim , Y[M] , R , nam[N] ;bool tree[N1] ;void dfs1( int x , int inE ){dfn[x] tim ;for(int i head[x] ; i ; i E[i].lst ) {if( i(inE^1) ) continue ;int t E[i].to ;if( !dfn[t] ) tree[i] 1 , dfs1(t,i) ;else {if( dfn[t]dfn[x] ) Y[R] t ;//返祖边 }}}int w[M] , col ;LL ans , f[N][M] , Sum[N] ;// 1~col 表示划分出的这几种颜色0 表示与这些都不同 void dfs3( int x , int inE ){for(int i 1 ; i col ; i ) {if( nam[x] ) f[x][i] 0 ;else f[x][i] 1 ;}if( nam[x] ) f[x][w[nam[x]]] 1 , f[x][0] 0 ;else f[x][0] 1 ;Sum[x] 0 ;for(int i head[x] ; i ; i E[i].lst ) {if( i(inE^1) ) continue ;int t E[i].to ;if( tree[i] ) {dfs3( t , i ) ;for(int j 1 ; j col ; j ) {f[x][j] ((f[t][0]*(K-col)%modSum[t]-f[t][j])*e[E[i].id].Af[t][j]*e[E[i].id].B) % mod * f[x][j] % mod ;}f[x][0] ((Sum[t]f[t][0]*max(0,(K-col-1)))%mod*e[E[i].id].Af[t][0]*e[E[i].id].B)%mod*f[x][0]%mod ;}else {if( dfn[t]dfn[x] ) {int c w[nam[t]] ;for(int j 1 ; j col ; j ) {if( j c ) f[x][j] f[x][j]*e[E[i].id].B%mod ;else f[x][j] f[x][j]*e[E[i].id].A%mod ;}f[x][0] f[x][0]*e[E[i].id].A%mod ;}}}for(int j 1 ; j col ; j ) {Sum[x] ( Sum[x] f[x][j] ) % mod ;}}LL g[N] ;void calc( int cnt ) // cnt 个集合 {col cnt ;dfs3( 1 , 0 ) ;for(int j 1 ; j col ; j ) {ans ( ans f[1][j]*g[col] ) % mod ;}ans ( ans f[1][0]*(K-col)%mod*g[col] ) % mod ;}void dfs2( int x , int nw ){if( x R1 ) {if( nw K ) calc(nw) ;return ;}w[x] nw1 ;dfs2( x1 , nw1 ) ;for(int i 1 ; i nw ; i ) {w[x] i ;dfs2(x1,nw) ;}}void solve(){for(int i 1 ; i m ; i ) {add( e[i].x , e[i].y , i ) ;add( e[i].y , e[i].x , i ) ;}dfs1( 1 , 0 ) ;sort( Y1 , YR1 ) ;R unique( Y1 , YR1 ) - (Y1) ;for(int i 1 ; i R ; i ) nam[Y[i]] i ;g[0] 1 ;for(int i 1 ; i n ; i ) g[i] g[i-1]*(K-i1)%mod ;dfs2( 1 , 0 ) ;printf(%lld\n , (ansmod)%mod ) ;tot 1 ; tim 0 ; R 0 ; ans 0 ;memset( head , 0 , sizeof head ) ; memset( dfn , 0 , sizeof dfn ) ;memset( nam , 0 , sizeof nam ) ;memset( tree , 0 , sizeof tree ) ;}
}
void solve()
{scanf(%d%d%d , n , m , K ) ;for(int i 1 ; i m ; i ) {scanf(%d%d%d%d , e[i].x , e[i].y , e[i].A , e[i].B ) ;}if( n12 ) {subtask1::solve() ;return ;}if( m n-1 ) {subtask2::solve() ;return ;}subtask3::solve() ;
}int main()
{freopen(color.in,r,stdin) ;freopen(color.out,w,stdout) ;int t ;scanf(%d , t ) ;while( t -- ) solve() ;return 0 ;
}
