solution.txt

TFcis 2017_10_03 校內複選 簡單題解 by jd3

題意就不說了
code 和測資也在 github 上


A. Woody
	
	難易度：★
	
	每天邊長都會 *= sqrt(2)
	也就是說每天面積都會 /= 2
	反過來把 A 每次 *2 和 L*L 比較
	不需要 double 也不需要 LL 

	
B. MagicNumber
	
	難易度：★★ + 0.5顆★給實做難度
	
	( 大家都不寫我好難過 QAQ )
	
	經過一番觀察
	2^k 中出現 111
	表示在 2 進位底下是有三段 k 個 0 接 一個 1
	因為不會有重疊，所以可以線性的去判
	題目很仁慈的給了 16 進位輸入方便你轉 2 進位
	需要注意的點：
		# 最高位的 1 前面可以接任意多個 0 
		# 對於要判的 k ， "000...01" 要出現在 %k 餘 0 的位置
		  否則轉換成該進位制後不會是 1
		# 要由小到大輸出

		
C. OldTree
	
	難易度：★★★
	
	出題者們 debug 很久的題目 ( 為什麼大家都會啦 QAQ )
	
	簡化題序就是：拔掉一個點讓含有 0 的連通塊總權重最小
	大致上應該可以感受到跟割點很有關係
	要小心的點：
		# 不一定要是割點，某個點權重很大也可能拔他
		# DFS(或是說Tarjan) 時，某割點的子節點的總權重，要確實會被這個點割掉才加上去
	
	
D. Ena		
	
	難易度：★★★★★
	
	一個普通難的解法(48pt)是 N^3 的 DP
	對於狀態的假設有不同解讀方式
	我個人是這樣設的
		v[i][j] := 在 0 ~ j 當中使用了 i 直接連到 j 的最大價值(接觸的數量)
	轉移枚舉 v[k][i] 線性掃過去
	這樣是 2D 狀態 1D 轉移 => O(N^3)
	
	你可能會需要先預處理兩兩之間是否被擋住 ( O(N^2) )
	
	
	接下來是優化
	我們需要一些觀察
	首先，我們固定 i ，把 j 往右移
	會發現 i,j 之間有兩種狀況：
		(1) 被擋住無法直接連
		(2) 角度比 i 連到 (i,j) 之中的任意點都更高 (即逆時針轉)
	排除掉 (1) 之後，剩下的所有的 j 會形成角度遞增的樣子(畫出來是個上凹的折線)
	當 j 的角度是遞增的，能轉移過來的 v[k][i] 當中的 k 的角度也是逆時針轉的
	對於所有 k < i 排除掉被擋住的，剩下的也會形成角度遞增 (即逆時針轉)
	這樣我們就可以套個隊列優化
	把 k 塞進 deque 裡維護最大的和可能成為最大的
	在一連串 push 和 pop 之中，轉移就變成均攤 O(1) 了
	
	DP + 隊列優化 => O(N^2) => AC!
	
	
	
E. Candy
	
	預期難易度：★★★★
	賽中難易度：★★★
	
	中文標題提示了你這題是區間 mod XP
	
	還記得區間開根號嗎
	暴力做下去就會很快的收斂到 1 
	區間 mod 也很像
	對於需要的區間就直接做下去
	
	原本應該要紀錄區間的最大值
	當 max < v 時直接 return
	不過這次好像測資沒出好沒卡到這個(?)
	
	簡單的性質說明：
		每次 mod 至少會把需要 mod 的值減去一半 ( 如果 >= 2*v 只會砍去更多比例 )
		不管是原本的值還是單點加值都會再 log V 次以內被降到不需要再遞迴下去做 mod