題目
終于知道JLOI為什么是5題4h了 因?yàn)镴SOI也是 而JS給JL出題 風(fēng)格當(dāng)然一樣
而且也會(huì)有一些比較偏的題目 還有一點(diǎn)是數(shù)據(jù)弱他還不告訴你 比如最后一題樸素快排就能90分 如果是NOI的會(huì) 一定會(huì)說90%的數(shù)據(jù)n<=?的而且不會(huì)是90%的 最多是40% 沒辦法省選又沒人贊助誰(shuí)給你好好出題(好像今年NOI就沒有所以WC的題目所有'<='都打成了‘=’)
言歸正傳
這套題目好題還是有的
比如第一題 雖然我至今沒搞明白 但是我知道他要求的是：從A中選取最少的點(diǎn) 使得B中所有點(diǎn)都在A中選取點(diǎn)的凸包內(nèi)? 這個(gè)變化十分巧妙
第二題 枚舉和牌和對(duì)子是必然的趨勢(shì) 那么剩下的判斷是否為和就只能在線性時(shí)間內(nèi)解決了
也就是說題目只給了我們掃一次(或常數(shù)次)的機(jī)會(huì) 而且是能按n掃
這么近的時(shí)間不得讓我們想到貪心 如果對(duì)于一張牌 可以組成順子 也可以組成刻牌 這個(gè)時(shí)候一定要有一種固定的選擇
假設(shè)選擇順子 很顯然若是111234 本來可以和的牌 就不胡了
那如果是刻字呢 經(jīng)反復(fù)試驗(yàn)沒有找到反例 在時(shí)間緊張的比賽中 不一定一定要證明 于是我寫了一下
AC
看來我的感覺還可以 但光靠感覺是不行的 證明如下
若經(jīng)過上訴貪心方法的到的答案是和牌則 這副牌一定是和牌
所以只需證明經(jīng)上述算法得到的答案為非和時(shí) 這副牌一定非和 下面的證明均在經(jīng)上述算法得到的答案為非和前提下進(jìn)行
假設(shè)有一種方案能使這副牌和
則一定有至少一處 原方案為刻字而新方案為順子
將每個(gè)組合按最小、較小、最大3個(gè)關(guān)鍵字順次按有小到大排序
找到第一次這樣的地方
顯然之前的牌組合的方式兩種方案是一樣的
所以當(dāng)將原方案中的刻字轉(zhuǎn)化為順子后 如果該方案為和牌則另兩張?jiān)谠桨笧榭套值呐埔才c其后面兩張組成順子 與組成3個(gè)刻字等效 所以假設(shè)不成立(這樣和在我們吉林打法還大呢)
第3題 我認(rèn)為是一道比較偏的題目 看了解題報(bào)告仍覺得比較偏
一個(gè)被逼無奈的貪心 結(jié)果竟是AC 在這里我不想多說了 有興趣的同學(xué)看這里吧
第4題 比較常見的DP 好像在URAL上做過 就是搞一個(gè)f[i][j]表示前i個(gè)字符 后綴為前綴j(這里的j只在我們預(yù)先搞好的trie里的編號(hào))不含有可識(shí)別單詞的個(gè)數(shù) 重點(diǎn)維護(hù)f 總之很麻煩 但好想 我就不想說了(我的表達(dá)能力容易把自己說糊涂了)
第5題 赤裸裸的后綴數(shù)組 只要將原串加倍即可 我的倍增可以AC而解題報(bào)告說這么做會(huì)超時(shí) 是不是他用string了 不超時(shí)才怪呢