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