題目
這套題做的很囧
第一題 題目沒什么說的就是模擬 不過很麻煩
但是題目里的游戲很好玩 真的很好玩
第二題 一開始看像04年 ACM上海賽區的H題 田忌賽馬 記得集訓隊資料里的解法是O(n^2)
但是發現 n<=
100000 后來發現這題與田忌賽馬是不一樣的
田忌賽馬 是求最大|小分差 那么怎么貪心呢
以求最高分為例 提出一個策略：
設我方的選手集為A? 對方為B
若Amax>Bmax
則A-=Amax,B-=Bmax? ans+=2
否則 A-=Amin,B-=Bmax 如果Amin==Bmax? ans+=1
下面是證明
若Amax>Bmax
假設有一種方案 使得Bmax不與Amax交戰&得分>當前方案
設于Bmax、Amax交戰的分別為a,b
則將Bmax與Amax交戰 a與b交戰? 其余與該方案相同 易證此方案不亞于 該方案&此方案得分=原方案
若Amax<=Bmax 同上述方法可證 這里就不多說了
值得一說的是第4題 我想了2天 實在沒有思路將一些想法記在下面并將它添加到未解決問題中
首先想到的是將它想LCA->RMQ一樣搞出一個歐拉序列 通過維護這個序列解題
那么借助什么數據結構好呢 線段樹？
這好像不可能 倒不是得到答案的問題
關鍵是每次更改都要不止更改一個或常數個
看來 搞成一個序列是沒戲 那么仍保持樹狀結構呢
這回 更改時好辦了 但怎么得到答案哪
我又標程 不過我這個人最不擅長就是讀程序 但可以看出標程用到平衡樹
實在是不會 等oibh好了到哪頂上問問應該會有結果幻燈片 20
posted on 2009-03-14 23:21
250 閱讀(774)
評論(4) 編輯 收藏 引用 所屬分類:
oi