NOIP2011解題報告

馬鞍山第二中學 鄭逸寧

DAY1.

1.1carpet

題目簡述：

求最后一次覆蓋某一點的矩形的序號.

分析:

對于點（x,y）和矩形（a,b,g,k）,若滿足a<=x<=a+g && b<=y<=b+k,則稱該矩形覆蓋該點.

實現(xiàn)1：

從前向后查找,一邊讀一邊更新.T=O(n),S=O(1);

實現(xiàn)2：

先存儲下來,從后往前查找,查找到即輸出.T=O(n),S=O(n);

總結：

一般來說,實現(xiàn)2在數(shù)據(jù)已經儲存好的情況下比1要快,但就本題來說比1花費了更多的空間,這體現(xiàn)了時間和空間的辯證關系.

1.2hotel

題目簡述：

求一段有A,B兩種屬性的序列中,滿足A_i=A_j,并且存在B_{k（i<=k<=j）}<=W的無序二元組的組數(shù).

分析1：

這是一個靜態(tài)統(tǒng)計問題.先不妨設i<j,防止統(tǒng)計時重復,也能很快的想到按屬性A分開處理,我們可以利用動態(tài)規(guī)劃的思想來解決.

實現(xiàn)1：

T[i]表示第i個元素前最近的滿足B_k<=W元素的位置；

G[i][j]表示在前j 元素中屬性A為i的元素的個數(shù).

首先計算出G[i][j]:

若A_j=i,則G[i][j]=G[i][j-1]+1;

否則G[i][j]=G[i][j-1];

然后一邊計算T[i],一邊統(tǒng)計總數(shù)ans：

若i本身滿足B_i<=W則T[i]=i,ans+=G[A_i][T[i]]-1（自己不能和自己成組）；

否T[i]=T[i-1], ans+=G[A_i][T[i]].

最后時間復雜度T=O(kn),空間復雜度S=O(kn) .

分析2：

本題還有不同的思路.如:使用ST算法的O(nlog₂n)的算法,和同樣是DP預處理但構造得比較精妙的O(n)的算法。具體實現(xiàn),以后再寫.

總結：

O(kn)的算法很容易想到,但更快的算法比較困難,畢竟我在考場上還想錯了.如果題目可以用O(kn)的方法解決,那么在考試時最好不要想O(n)或O(nlog₂n)的算法.

1.3mayan

題目簡述：

有一個游戲,通過交換左右兩個方塊,使三個或三個以上的同色方塊連成一線而消除掉,當下方方塊消除后,上面的方塊會掉落.求在規(guī)定步數(shù)時,方塊剛好全部消除的字典序最小方案.

分析：

搜索.

實現(xiàn)：

這道題很復雜,編寫的內容非常的多,由于我水平不高,只是寫了在一層中平移互換的部分.

總結：

要多練習搜索題.

Day2：

2.1factor

題目簡述：

求(ax+by)ⁿ中xⁿy^m項的次數(shù).

分析：

利用二項式展開定理,系數(shù)為C(n,n+m) aⁿb^m

實現(xiàn)：

遞推求出組合數(shù)C[i][j]=C[i-1][j-1]+C[i-1][j],一邊加一邊取模.再一邊乘一邊取模,乘上aⁿb^m即可.

T=O((n+m)²),S=O((n+m)²).

總結：

取模的運算遵循乘法和加法的結合律,但不支持除法.如果要用公式法算組合數(shù),需要先分解質因數(shù),

約分后再乘才行.相比之下使用遞推法算組合數(shù)就更好一些

題目簡述：

 

給定n個含有w, v兩種屬性的元素和m個區(qū)間,選一個W,使公式：

Y_i=∑1*∑v_j,j∈[Li,Ri]且w_j≥W

計算出的∑Y_i與給定的值Y之間的差的絕對值最小。

分析:

這是一道動態(tài)統(tǒng)計的問題,但仔細分析,∑Y_i隨W增大而單調不增,所以我們可以先二分答案,讓后把它改為靜態(tài)的統(tǒng)計問題.對于多區(qū)間的統(tǒng)計,有不同的解決方法,所以同樣使用二分答案,本題的得分也在50～100之間.

實現(xiàn)1：

單獨處理每個區(qū)間,按照公式計算即可.

T=O(n²log₂maxw),S=O(n).

實現(xiàn)2：

使用線段樹.這是一個錯誤的想法,是在錯誤預估 O(nlog₂nlog₂maxw)的時間可以通過的前提下做出的選擇,其實一開使想到O(n)的掃描線算法(其實這已經是一個錯誤的想法了,因為掃描線是用于對于多區(qū)間覆蓋,無關聯(lián)的點的簡單統(tǒng)計用的,而對于有重疊的區(qū)間統(tǒng)計和較復雜的公式就無能為了力了),也聯(lián)想到樹狀數(shù)組,覺得功能不足以完成較復雜的公式計算.其實沒有想到正確的統(tǒng)計方法,要不然不僅是樹狀數(shù)組,連什么數(shù)據(jù)結構都不用也可以解決.

具體實現(xiàn)方式就是每次插入m條線段,并遞歸同時計算出∑1和∑v_j,最后求和計算.

T=O(nlog₂nlog₂maxw),S=O(n).

實現(xiàn)3：

其實類似的統(tǒng)計題是做過的,但看到復雜的公式就沒有想到改進.我們可以用動態(tài)規(guī)劃的思想來解決這個問題：用t[i]表示前i個元素中符合條件的元素的個數(shù),用sum[i]表示前i個元素中符合條件元素的v的值的和,那么對于區(qū)間[l,r],最后的值就是(sum[r]-sum[l-1])*(t[r]-t[l-1]).我們預處理出t[i]和sum[i]的值,然后對每個區(qū)間操作一次即可。

T=O((n+m)log₂maxw),S=O(n).

總結：

好多人沒有得滿分的原因是二分查找沒有注意邊界,但也有像我一樣腦殘的人想到了高級的線段樹,而忽視了簡單的預處理,還浪費了不少的時間。

2.3bus

題目簡述：

有序的n個點組成一個序列,有m個單位在時間T_i出現(xiàn)在其中的一點A_i要移動到比A_i大的一點B_i,只有所有要到A_i點以后的單位都到了A_i點,才可以出發(fā)到下一個點,每兩個相鄰的點之間有一定權值的距離.可以通過k次調整,每次使相鄰點之間的距離-1,可以重復調整.求所有點移動的最小時間和.

分析1：

題目不是很好懂,大略讀懂題目后,觀察數(shù)據(jù)中有k<=1的30%的數(shù)據(jù),于是枚舉即可.

實現(xiàn)1：

d[i]表示第i個點到第i+1個點的權值,a[i],b[i],t[i]如題目簡述所示.latest[i]表示到第i個點的元素最晚的到達值,arrive[i]表示集體到第i個點的時間.當k=0時:

arrive[i]=max(arrive[i-1],latest[i-1])+d[i-1],

ans=∑(arrive[b[i]]-t[i])

當k=1時,枚舉出一個d[i],減去1,計算出最優(yōu)的ans即可.T=O(n²),S=O(n).

分析2：

我們考慮怎樣使用調整.顯然對于latest[i]>=arrive[i],對于i點以后的單位所需的時間沒有任何影響,感覺這里的許多操作應該是獨立的,大概可以用貪心的方法來解題,然而需要一個衡量標準,這正是在考場上沒想到的.

實現(xiàn)2：

用next[i]表示在第i個點后離i最近的滿足latest[i]>=arrive[i]的點,sum[i]表示前i個點的單位數(shù).

我們可以用sum[next[i]]-sum[i]來衡量在第i-1到第i個點之間調整的效果,每次選擇該值最大的邊,把d的值-1,然后重新計算arrive[i]的值,再做相同操作.此時時間復雜度O(kn),還不足以通過全部的數(shù)據(jù).其實很簡單的想一想,如果把d[i]的值-1后仍然有所有滿足latest[i]>=arrive[i]的點的狀態(tài)不會改變并且d[i]仍然可以-1,那么下次調整的還是i-1到i的這條邊.我們不妨一次性把它做到位,讓d[i]減去一個恰好的數(shù)(我是拿KM算法的松弛量類比的)最終T=O(n²),S=O(n).

總結：

本來想在后面70%中隨便貪心做做的,但時間不夠了,當時想的貪心法已經很接近這個解法了,如果第二題能節(jié)約更多的時間的話,就可以給這題留出更大的希望.

注：本文用T 表示時間復雜度,S表示空間復雜度.復雜度只表示數(shù)量級,不考慮常數(shù).

還需思考的問題：

1.2的O（nlogn）和O（n）的解法

2.1的數(shù)學方法優(yōu)化？

1.3怎樣爆搜？