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