2019.08.17【NOIP提高組】模拟B組總結

總結

估分：100+100+0=200

總分：100+70=170

T1：

題意是給你N*M的格子，其中有一些格子上有污點，你可以每次塗掉連續的不超過R行的污點或連續的不超過C列的污點，求最少次數。

注意到n，m的範圍很小，我們可以先枚舉一行或一列選的狀态，同時一邊處理出最少所用的次數。

之後暴力處理出剩餘的沒有塗掉的污點，這些點要用列的操作來塗。

類比于行，我們隻要預處理出每個列的狀态所對應的最少次數即可。

T2:

題意是定義n!k=(n-1)!k*n!(k-1)，當k=0時n!k=n,當n=0時n!k=1,求n!k的約數的個數。

容易想到dp。

把整個過程看做一個矩陣。

設f[i][j][k]表示做到第i行第j列這個數的第k個質因子有多少個。

f[i][j][k]=f[i-1][j][k]+f[i][j-1][k]。

最後答案即為i=1~k(f[n][m][i]+1)的乘積。

但是我們發現如果n開大一些這樣的算法就通不過了。

我們可以想因為隻有(i,0)的點才會對答案有貢獻，是以我們可以算出從(i,0)推到(n,m)的方案數，再用1~n的質因子直接累加即可。

那麼(i,0)推到(n,m)的方案數是多少呢？

同樣抽象成一個二維平面，我們每次從(i,0)這個點出發，走到(n,m)的方案數，實際上就是C(n-i+m-0,n-i)。

至此我們可以求出每個質因子的倍數，此題得到解答。

比賽中因為數組開小了而失去了30分，真不應該。

但其實主要原因是時間配置設定不得當，先做了最後一題。

T3:

題意是給你n個點和P,Q，要你求兩個點構成的斜率最接近于P/Q，以“A/B”的形式輸出斜率。

相當于是然你求(y1-y2)/(x1-x2) 最接近于P/Q的值X和Y。

通分，得到:

Q(y1-y2)/Q (x1-x2)最接近于P(x1-x2)/Q(x1-x2)

将分母去掉:

Q(y1-y2)最接近于P(x1-x2)

拆項：

Qy1-Qy2最接近于Px1-Px2

移項：

Qy1-Px1最接近于Qy2-Px2

至此，我們隻用對每一個點的上式排一遍序，去相鄰的比較即可。

考慮另一種思路。

我們将式子拆成:

| Q(y1-y2) / Q(x1-x2)-P(x1-x2) / Q(x1-x2) |最小

| ((Q(y1-y2)-P(x1-x2)) / Q(x1-x2) |最小

| ((Qy1-Px1)-(Qy2-Px2)) / Qx1-Qx2 |最小

我們将這個式子看成斜率的形式，

即Q(y1-Px1)=Y1,Q(y2-Px2)=Y2,Qx1=X1,Qx2=X2,得：

| (Y1-Y2)/(X1-X2) | 最小

也就是我們将每個點用上式變成一個新點，再求兩個點所構成的斜率的絕對值最小值。

若兩個縱坐标直接有一個點，那麼這中間點于兩邊點構成的斜率總有一個會比兩邊點構成的斜率小。

是以我們将點按照縱坐标排序，

用兩兩相鄰的縱坐标更新答案即可。

注意資料範圍，檢查數組是否越界。

配置設定好時間，端正好心态。

馬上就要NOIP了，好好準備。