竹園論壇

標題: LTIME21 [打印本頁]

作者: Sylveon 時間: 2015-2-23 19:09
標題: LTIME21
http://www.codechef.com/LTIME21/

Name	Successful Submission	Accuracy
Lucky Four	1349	82.46
The Warehouse	107	21.54
Heavy-light Decompositions	25	9.28
The First Cube	24	1.33

看到FB動態有人PO出了first ac才發現到這比賽XD，來湊一腳。寫到一半Forum就爆炸了跑去修理ORZ。這次題目Heavy-light Decompositions沒中文一開始也沒什麼人動所以跳過，結果最後AC數超過Cube... 晚點來研究
Lucky Four
放水無腦過... (看Code就知道為何了)

The Warehouse
最後的可能只有RGB的全排列共3!種組合，在此採取枚舉所有組合最佳解。題目所述的三個移動規則可以簡化成：與相鄰交換就得花費1代價。不難發現當RGB順序大小給定時，最小花費代價就是逆述對個數。反正數字只有三種，就不用做什麼BIT，直接暴力加一加就好了。

The First Cube
對於單一一個數字，如果存在 X^3 的因子，那X<10^6，如果存在 X^2，那可以找到 Y*X^2 ，使Y或X小於10^6。
建一張10^6的質數表就可以判斷出是否有2次方以上因子。多變數狀況下，做gcd就可以找出兩數公共因子，處理重複的因數。
(轉述linnil1)

Heavy-light Decompositions
??

作者: domen111 時間: 2015-2-28 12:10
本帖最後由 domen111 於 2015-2-28 12:11 編輯

Heavy-light Decompositions AC code:
http://www.codechef.com/viewsolution/6361466
英文的官方詳解: http://discuss.codechef.com/questions/64883/hldots-editorial

題意:
求有幾種樹練剖分方法數，一個合法的樹練剖分定義為從根節點到任意節點所經過的輕邊不得超過log2(N)，N為節點總數。

比賽時本來以為這題是應該照樹練剖分的方法去做，後來發覺就算不是依照樹練剖分的方法(重邊連到重兒子)也可能符合題目要求(log2)的性質。

這題其實DP一下就行了
dp[i ][j], i:節點編號, j:連到此節點前的輕邊數量, dp[i ][j]=方法數
轉移時枚舉連接子節點的邊作為重邊，乘一乘計算方法數在加起來就行了
計算連乘的時候不要太暴力直接乘，否則複雜度變成O(C[sup]2[/sup])(C為子節點數)就只能解出小測資，記得先預處理一下，轉移複雜度為O(C)、總複雜度為O(NlgN)就能完全AC。

歡迎光臨竹園論壇 (http://forum.tfcis.org/)